BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
The d-dimensional algebraic connectivity ad(G) of a graph G=(V,E), introduced by Jordán and Tanigawa, is a quantitative measure of the d-dimensional rigidity of G that is defined in terms of the eigenvalues of stiffness matrices (which are analogues of the graph Laplacian) associated to mappings of the vertex set V into Rd. Here, we analyze the d-dimensional algebraic connectivity of complete graphs. In particular, we show that, for d≥3, ad(Kd+1)=1, and for n≥2d, ⌈2dn⌉−2d+1≤ad(Kn)≤3(d−1)2n+31.
We consider the Erdős-Rényi evolution of random graphs, where a new uniformly distributed edge is added to the graph in every step. For every fixed d≥1, we show that with high probability, the graph becomes rigid in Rd at the very moment its minimum degree becomes d, and it becomes globally rigid in Rd at the very moment its minimum degree becomes d+1.
We provide lower and upper bounds on the minimum size of a maximum stable set over graphs of flag spheres, as a function of the dimension of the sphere and the number of vertices. Further, we use stable sets to obtain an improved Lower Bound Theorem for the face numbers of flag spheres.
We analyze the asymptotic extremal growth rate of the Betti numbers of clique complexes of graphs on n vertices not containing a fixed forbidden induced subgraph H. In particular, we prove a theorem of the alternative: for any H the growth rate achieves exactly one of five possible exponentials, that is, independent of the field of coefficients, the nth root of the maximal total Betti number over n-vertex graphs with no induced copy of H has a limit, as n tends to infinity, and, ranging over all H, exactly five different limits are attained. For the interesting case where H is the 4-cycle, the above limit is 1, and we prove a slightly superpolynomial upper bound.
We resolve a conjecture of Kalai relating approximation theory of convex bodies by simplicial polytopes to the face numbers and primitive Betti numbers of these polytopes and their toric varieties. The proof uses higher notions of chordality. Further, for C^2-convex bodies, asymptotically tight lower bounds on the g-numbers of the approximating polytopes are given, in terms of their Hausdorff distance from the convex body.
In this paper, we study Lefschetz properties of Artinian reductions of Stanley-Reisner rings of balanced simplicial 3-polytopes. A (d−1)-dimensional simplicial complex is said to be balanced if its graph is d-colorable. If a simplicial complex is balanced, then its Stanley-Reisner ring has a special system of parameters induced by the coloring. We prove that the Artinian reduction of the Stanley-Reisner ring of a balanced simplicial 3-polytope with respect to this special system of parameters has the strong Lefschetz property if the characteristic of the base field is not two or three. Moreover, we characterize (2,1)-balanced simplicial polytopes, i.e., polytopes with exactly one red vertex and two blue vertices in each facet, such that an analogous property holds. In fact, we show that this is the case if and only if the induced graph on the blue vertices satisfies a Laman-type combinatorial condition.
We consider two problems regarding vanishing patterns in the Betti table of edge ideals I in polynomial algebra S. First, we show that the j-strand is connected if j=3 (for j=2 this is easy and known), and give examples where the j-strand is not connected for any j>3. Next, we apply our result on strand connectivity to establish the subadditivity conjecture for edge ideals, ta+b≤ta+tb, in case b=2,3 (the case b=1 is known). Here ti stands for the maximal shifts in the minimal free S-resolution of S/I
After fixing a triangulation L of a k-dimensional simplex that has no new vertices on the boundary, we introduce a triangulation operation on all simplicial complexes that replaces every k-face with a copy of L, via a sequence of induced subdivisions. The operation may be performed in many ways, but we show that the face numbers of the subdivided complex depend only on the face numbers of the original complex, in a linear fashion. We use this linear map to define a sequence of polynomials generalizing the Tchebyshev polynomials of the first kind and show, that in many cases, but not all, the resulting polynomials have only real roots, located in the interval (−1,1). Some analogous results are shown also for generalized Tchebyshev polynomials of the higher kind, defined using summing over links of all original faces of a given dimension in our generalized Tchebyshev triangulations. Generalized Tchebyshev triangulations of the boundary complex of a cross-polytope play a central role in our calculations, and for some of these we verify the validity of a generalized lower bound conjecture by the second author.
We generalize the fundamental graph-theoretic notion of chordality for higher dimensional simplicial complexes by putting it into a proper context within homology theory. We generalize some of the classical results of graph chordality to this generality, including the fundamental relation to the Leray property and chordality theorems of Dirac.
We generalize the notion of graph minors to all (finite) simplicial complexes. For every two simplicial complexes H and K and every nonnegative integer m, we prove that if H is a minor of K then the non vanishing of Van Kampen's obstruction in dimension m (a characteristic class indicating non embeddability in the (m-1)-sphere) for H implies its non vanishing for K. As a corollary, based on results by Van Kampen and Flores, if K has the d-skeleton of the (2d+2)-simplex as a minor, then K is not embeddable in the 2d-sphere. We answer affirmatively a problem asked by Dey et. al. concerning topology-preserving edge contractions, and conclude from it the validity of the generalized lower bound inequalities for a special class of triangulated spheres.
The maximum number of vertices in a graph of maximum degree Δ≥3 and fixed diameter k≥2 is upper bounded by (1+o(1))(Δ−1)k. If we restrict our graphs to certain classes, better upper bounds are known. For instance, for the class of trees there is an upper bound of (2+o(1))(Δ−1)⌊k/2⌋ for a fixed k. The main result of this paper is that graphs embedded in surfaces of bounded Euler genus g behave like trees, in the sense that, for large Δ, such graphs have orders bounded from above by \[begin{cases} c(g+1)(Δ-1)^{\lfloor k/2\rfloor} & \text{if $k$ is even} c(g^{3/2}+1)(Δ-1)^{\lfloor k/2\rfloor} & \text{if $k$ is odd}, \{cases}\] where c is an absolute constant. This result represents a qualitative improvement over all previous results, even for planar graphs of odd diameter k. With respect to lower bounds, we construct graphs of Euler genus g, odd diameter k, and order c(g+1)(Δ−1)⌊k/2⌋ for some absolute constant c>0. Our results answer in the negative a question of Miller and Širáň (2005).
By taking quotients of a certain tiling of hyperbolic plane / space by certain group actions, we obtain geometric polyhedra / cellulations with interesting symmetries and incidence structure.
We develop a bipartite rigidity theory for bipartite graphs parallel to the classical rigidity theory for general graphs, and define for two positive integers k,l the notions of (k,l)-rigid and (k,l)-stress free bipartite graphs. This theory coincides with the study of Babson--Novik's balanced shifting restricted to graphs. We establish bipartite analogs of the cone, contraction, deletion, and gluing lemmas, and apply these results to derive a bipartite analog of the rigidity criterion for planar graphs. Our result asserts that for a planar bipartite graph G its balanced shifting, Gb, does not contain K3,3; equivalently, planar bipartite graphs are generically (2,2)-stress free. We also discuss potential applications of this theory to Jockusch's cubical lower bound conjecture and to upper bound conjectures for embedded simplicial complexes.
It is known that the (2k−1)-sphere has at most 2O(nklogn) combinatorially distinct triangulations with n vertices, for every k≥2. Here we construct at least 2Ω(nk) such triangulations, improving on the previous constructions which gave 2Ω(nk−1) in the general case (Kalai) and 2Ω(n5/4) for k=2 (Pfeifle-Ziegler). We also construct 2Ω(nk−1+k1) geodesic (a.k.a. star-convex) n-vertex triangualtions of the (2k−1)-sphere. As a step for this (in the case k=2) we construct n-vertex 4-polytopes containing Ω(n3/2) facets that are not simplices, or with Ω(n3/2) edges of degree three.
Refining a basic result of Alexander, we show that two flag simplicial complexes are piecewise linearly homeomorphic if and only if they can be connected by a sequence of flag complexes, each obtained from the previous one by either an edge subdivision or its inverse. For flag spheres we pose new conjectures on their combinatorial structure forced by their face numbers, analogous to the extremal examples in the upper and lower bound theorems for simplicial spheres. Furthermore, we show that our algorithm to test the conjectures searches through the entire space of flag PL spheres of any given dimension.
We introduce a notion of bipartite minors and prove a bipartite analog of Wagner's theorem: a bipartite graph is planar if and only if it does not contain K3,3 as a bipartite minor. Similarly, we provide a forbidden minor characterization for outerplanar graphs and forests. We then establish a recursive characterization of bipartite (2,2)-Laman graphs --- a certain family of graphs that contains all maximal bipartite planar graphs.
It is known that the 3-sphere has at most 2O(n2logn) combinatorially distinct triangulations with n vertices. Here we construct at least 2Ω(n2) such triangulations.
We construct many nonpolytopal nonsimplicial Gorenstein* meet semi-lattices with nonnegative toric g-vector, supporting a conjecture of Stanley. These are formed as Bier spheres over the face posets of multiplexes, polytopes constructed by Bisztriczky as generalizations of simplices.
The notion of r-stackedness for simplicial polytopes was introduced by McMullen and Walkup in 1971 as a generalization of stacked polytopes. In this paper, we define the r-stackedness for triangulated homology manifolds and study their basic properties. In addition, we find a new necessary condition for face vectors of triangulated manifolds when all the vertex links are polytopal.
In 1971, McMullen and Walkup posed the following conjecture, which is called the generalized lower bound conjecture: If P is a simplicial d-polytope then its h-vector (h0,h1,...,hd) satisfies h0≤h1≤...≤h⌊2d⌋. Moreover, if hr−1=hr for some r≤2d then P can be triangulated without introducing simplices of dimension ≤d−r. The first part of the conjecture was solved by Stanley in 1980 using the hard Lefschetz theorem for projective toric varieties. In this paper, we give a proof of the remaining part of the conjecture. In addition, we generalize this property to a certain class of simplicial spheres, namely those admitting the weak Lefschetz property.
We present examples of flag homology spheres whose γ-vectors satisfy the Kruskal-Katona inequalities. This includes several families of well-studied simplicial complexes, including Coxeter complexes and the simplicial complexes dual to the associahedron and to the cyclohedron. In these cases, we construct explicit simplicial complexes whose f-vectors are the γ-vectors in question. In another direction, we show that if a flag (d−1)-sphere has at most 2d+2 vertices its γ-vector satisfies the Kruskal-Katona inequalities. We conjecture that if Δ is a flag homology sphere then γ(Δ) satisfies the Kruskal-Katona inequalities. This conjecture is a significant refinement of Gal's conjecture, which asserts that such γ-vectors are nonnegative.
We show that the γ-vector of the order complex of any polytope is the f-vector of a balanced simplicial complex. This is done by proving this statement for a subclass of Stanley's S-shellable spheres which includes all polytopes. The proof shows that certain parts of the cd-index, when specializing c=1 and considering the resulted polynomial in d, are the f-polynomials of simplicial complexes that can be colored with "few" colors. We conjecture that the cd-index of a regular CW-sphere is itself the flag f-vector of a colored simplicial complex in a certain sense.
We characterize the cd-indices of Gorenstein* posets of rank 5, equivalently the flag f-vectors of Gorenstein* order complexes of dimension 3. As a corollary, we characterize the f-vectors of Gorenstein* order complexes in dimensions 3 and 4. This characterization rise a speculated intimate connection between the f-vectors of flag homology spheres and the f-vectors of Gorenstein* order complexes.
We prove that the γ-vector of the barycentric subdivision of a simplicial sphere is the f-vector of a balanced simplicial complex. The combinatorial basis for this work is the study of certain refinements of Eulerian numbers used by Brenti and Welker to describe the h-vector of the barycentric subdivision of a boolean complex.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.