The First Cheeger Constant of a Simplex

Kozlov, Dmitry
November 2017
Graphs & Combinatorics;Nov2017, Vol. 33 Issue 6, p1543
Academic Journal
The coboundary expansion generalizes the classical graph expansion to the case of the general simplicial complexes, and allows the definition of the higher-dimensional Cheeger constants $$h_k(X)$$ for an arbitrary simplicial complex X, and any $$k\ge 0$$ . In this paper we investigate the value of $$h_1(\Delta ^{[n]})$$ -the first Cheeger constant of a simplex with n vertices. It is known, due to the pioneering work of Meshulam and Wallach [12], that and that the equality $$h_1(\Delta ^{[n]})=n/3$$ is achieved when n is divisible by 3. Here we expand on these results. First, we show that So the sharp equality holds on a set whose density goes to 1. Second, we show that In other words, as n goes to infinity, the value $$h_1(\Delta ^{[n]})-n/3$$ is either 0 or goes to 0 very rapidly. Our methods include recasting the original question in purely graph-theoretic language, followed by a detailed investigation of a specific graph family, the so-called staircase graphs. These are defined by associating a graph to every partition, and appear to be especially suited to gain information about the first Cheeger constant of a simplex.


Related Articles

  • Reduced constants for simple cycle graph separation. Djidjev, Hristo N.; Venkatesan, Shankar M. // Acta Informatica;1997, Vol. 34 Issue 3, p231 

    If G is an n vertex maximal planar graph and d=1 3, then the vertex set of G can be partitioned into three sets A, B, C such that neither A nor B contains more than (1-d)n vertices, no edge from G connects a vertex in A to a vertex in B, and C is a cycle in G containing no more than...

  • Higher Generation Subgroup Sets and the Virtual Cohomological Dimension of Graph Products of Finite Groups. Harlander, Jens; Meinert, Holger // Journal of the London Mathematical Society;1996, Vol. 53 Issue 1, p99 

    We introduce panels of stabilizer schemes (K, G*) associated with finite intersection-closed subgroup sets â„‹ of a given group G, generalizing in some sense Davis' notion of a panel structure on a triangulated manifold for Coxeter groups. Given (K, G*), we construct a G-complex X with K as...

  • Reduction Theorem for Lattice Cohomology. László, Tamás; Némethi, András // IMRN: International Mathematics Research Notices;2015, Vol. 2015 Issue 11, p2938 

    The lattice cohomology of a plumbed 3-manifold M associated with a connected negative definite plumbing graph is an important tool in the study of topological properties of M and in the comparison of the topological properties with analytic ones, whenever M is realized as complex analytic...

  • Properties analysis of continuous Petri net based on decomposition. LU Jian-bo; LIAO Wei-zhi // Application Research of Computers / Jisuanji Yingyong Yanjiu;Nov2014, Vol. 31 Issue 11, p3295 

    This paper presented a decomposition method for constant speed continuous Petri net (CCPN) based on belonging of places, and it proved that the original CCPN could be obtained by the communion composition of the decomposed subnets. Also, it proved the relationship of the properties between the...

  • An Upper Bound for the Total Domination Subdivision Number of a Graph. Karami, H.; Khoeilar, R.; Sheikholeslami, S.; Khodkar, A. // Graphs & Combinatorics;Nov2009, Vol. 25 Issue 5, p727 

    A set S of vertices of a graph G = ( V, E) without isolated vertex is a total dominating set if every vertex of V( G) is adjacent to some vertex in S. The total domination number ? t( G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number $${{\rm...

  • Edge-disjoint Open Trails in Complete Bipartite Multigraphs. Cichacz, Sylwia; G�rlich, Agnieszka // Graphs & Combinatorics;Mar2010, Vol. 26 Issue 2, p207 

    Let r Ka,b be a complete bipartite multigraph. We show a necessary and sufficient condition for a multigraph r Ka,b to be arbitrarily decomposable into open trails. We extend the results obtained by Balister for complete graphs (Balister in Probab Comput 10:463-499, 2001). Moreover we show that...

  • A TOTALLY MAGIC CORDIAL LABELING OF ONE-POINT UNION OF n COPIES OF A GRAPH. Jeyanthi, P.; Benseera, N. Angel // Opuscula Mathematica;2014, Vol. 34 Issue 1, p115 

    A graph G is said to have a totally magic cordial (TMC) labeling with constant C if there exists a mapping f : V(G)∪ E(G) → {0,1} such that f (a) + f (b) + f (ab) ≡ C(mod 2) for all ab € E(G) and |nf(0) - nf(1)| ≤ 1, where nf (i) (i = 0,1) is the sum of the number...

  • Graphs with Average Degree Smaller Than $${\frac {30}{11}}$$ Burn Slowly. Prałat, Paweł // Graphs & Combinatorics;Mar2014, Vol. 30 Issue 2, p455 

    In this paper, we consider the following firefighter problem on a finite graph G = ( V, E). Suppose that a fire breaks out at a given vertex $${v \in V}$$ . In each subsequent time unit, a firefighter protects one vertex which is not yet on fire, and then the fire spreads to all unprotected...

  • Families of Rotationally-Symmetric Plane Graphs with Constant Metric Dimension. Imran, Muhammad; Bokhary, Syed Ahtsham Ul Haq; Baig, A. Q. // Southeast Asian Bulletin of Mathematics;2012, Vol. 36 Issue 5, p663 

    A family É¡ of connected graphs is a family with constant metric dimension if dim(G) is finite and does not depend upon the choice of G in É¡. The metric dimension of some classes of plane graphs has been determined in [1, 2, 3, 4, 11, 12, 13, 16, 23]. In this paper, we extend this study by...

  • On N-Graphs. Akram, Muhammad; Dar, Karamat H. // Southeast Asian Bulletin of Mathematics;2012, Vol. 36 Issue 6, p787 

    The concepts of complete N-graphs, N-bridge, N-cut vertex, N-block, constant N-graphs, totally constant N-graphs are introduced and investigated. Some of their properties are studied. We also introduce the concepts of neighbourly irregular N-graphs, neighbourly totally irregular N-graphs, highly...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics