Perfect sparsity characterizes infinite trees.
For a finite graph, sparsity is closely related to girth. Girth equals the minimum for which the graph contains a -configuration, i.e. a subgraph with vertices et edges.
Question. How large can the girth of an -vertex -regular graph be ? Denote this number by .
The upper bound is easy. The lower bound is due to Lubotzky-Philipps-Sarnak. An improvement from to was announced in 2010 but drawn back. I explain a weaker lower bound.
Proposition 1 For all , tends to infinity with .
Proof. Start with a girth -regular graph, double it. For each edge, decide to leave it un changed in both copies, or to open both copies and join edges. Let denote the random variable “number of -cycles of new graph”. We estimate the expectation . There are only a few configurations where the new graph has more -cycles. Remove them from the probability space. The resulting expectation is , so there are configurations with girth .
1.2. Higher dimensional girth
What should be a higher dimensional generalization of girth ? There are several such, depending on context.
Question. How large can the girth be for a -Steiner triple system ?
For each new face, a new vertex comes in. This suggests
Definition 2 The girth of a 2-dimensional simplicial complex is the smallest such that contains a -configuration, i.e. un subcomplex with vertices and faces.
Conjecture (Erdös, early 70’s). There exist Steiner triple systems with arbitrarily high girth.
Known: there are infinitely many Steiner triple systems with girth 6. There are exactly 2 Steiner triple systems with girth 7. That’s all. Hard.
Steiner triple systems are special cases of latin squares (view triples as coordinates of 1 entries in a array).
Question. What does a random latin square look like ?
On latin squares, there is a natural transitive Markov chain. Its mixing properties are unknown.
Easy fact: For all , there exists a constant and 2-dimensional complexes with faces and girth . Probabilistic method. However tends to 0.
Question. Does there exist an absolute constant and 2-dimensional complexes with faces and arbitrarily large girth ?
Erdös’ conjecture would imply that works.
Theorem 3 (Ruzsa-Szemeredi) If a simplicial 2-complex has no -configuration, then its size is .
This uses the same technology as Szemeredi’s theorem on arithmetic progressions.
2. Random complexes
2.1. Random regular graphs
Erdös and Renyi’s model does not provide regular graphs. In the 1980’s, a new model, the configuration model, was proposed.
Definition 4 Start with vertices and -semi-edges per vertex. Then pick at random a pairing between semi-edges. If loops or double edged are formed, discard.
The last step has little impact since such accidents occur with exponentially small probability.
2.2. Random graphs according to Erdös and Renyi
One can view the model sequentially. Add edges one by one.
Early in the process, connected components are small (logarithmic size) and have a simple shape: either a tree or a tree plus an edge. The probability that is a forest is positive and .
Around step , a major change takes place: a giant (linear size) component shows up. The probability that is a forest tends to 0.
Around step , becomes connected. Up to that time, there existed isolated vertices.
All these features are 0-dimensional and suggest higher dimensional generalizations.
2.3. Random simplicial complexes
Definition 5 (Linial-Meshulam) has a full -skeleton and every -face is added independently with probability .
Theorem 6 (Linial-Meshulam) The threshold for non vanishing of is .