Notes of Nati Linial’s Lille lecture nr 3

1. Sparsity

Perfect sparsity characterizes infinite trees.

1.1. Girth

For a finite graph, sparsity is closely related to girth. Girth equals the minimum {v} for which the graph contains a {(v,v)}-configuration, i.e. a subgraph with {v} vertices et {v} edges.

Question. How large can the girth of an {n}-vertex {d}-regular graph be ? Denote this number by {g(d,n)}.


\displaystyle  \begin{array}{rcl}  \frac{4}{3}\frac{\log n}{\log(d-1)}\leq g(d,n) \leq 2\frac{\log n}{\log(d-1)}. \end{array}

The upper bound is easy. The lower bound is due to Lubotzky-Philipps-Sarnak. An improvement from {\frac{4}{3}} to {\frac{?}{7}} was announced in 2010 but drawn back. I explain a weaker lower bound.

Proposition 1 For all {d}, {g(d,n)} tends to infinity with {n}.

Proof. Start with a girth {t} {d}-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 {X} denote the random variable “number of {t}-cycles of new graph”. We estimate the expectation {\mathop{\mathbb E}(X)}. There are only a few configurations where the new graph has more {t}-cycles. Remove them from the probability space. The resulting expectation is {<1}, so there are configurations with girth {>t}.

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 {1}-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 {v} such that {X} contains a {(v,v-2)}-configuration, i.e. un subcomplex with {v} vertices and {v-2} 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 {3\times 3\times 3} 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 {g}, there exists a constant {c_g} and 2-dimensional complexes with {\geq c_g\, n^2} faces and girth {\geq 6}. Probabilistic method. However {c_g} tends to 0.

Question. Does there exist an absolute constant {C^*} and 2-dimensional complexes with {\geq c^*\, n^2} faces and arbitrarily large girth ?

Erdös’ conjecture would imply that {c^* =\frac{1}{6}} works.

Theorem 3 (Ruzsa-Szemeredi) If a simplicial 2-complex has no {(6,3)}-configuration, then its size is {o(n^2)}.

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 {G(n,p)} model does not provide regular graphs. In the 1980’s, a new model, the configuration model, was proposed.

Definition 4 Start with {n} vertices and {d}-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 {G} is a forest is positive and {<1}.

Around step {\frac{n}{2}}, a major change takes place: a giant (linear size) component shows up. The probability that {G} is a forest tends to 0.

Around step {\frac{n\log n}{2}}, {G} 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) {X_d(n,p)} has a full {d-1}-skeleton and every {d}-face is added independently with probability {p}.

Theorem 6 (Linial-Meshulam) The threshold for non vanishing of {H_d(X,{\mathbb Z})} is {p=\frac{d\log n}{n}}.


About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
This entry was posted in Course and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s