Notes of Nati Linial’s lecture nr 2

Last time, I went through fundamental results in extremal graph theory and explained the {G(n,p)} model. Today, I will go more into results of mine. But let me finish the proof of a theorem I quoted last time.

1. Back to thresholds for graphs

Theorem 1 (Erdös, Rényi) The threshold for graph connectivity in {G(n,p)} is {p=\frac{\log n}{n}}, i.e.

\displaystyle  \begin{array}{rcl}  \forall\epsilon>0,&&\lim_{n\rightarrow \infty}\mathop{\mathbb P}(F\in G(n,(1+\epsilon)\frac{\log n}{n})\textrm{ is connected})=1,\\ &&\lim_{n\rightarrow \infty}\mathop{\mathbb P}(F\in G(n,(1-\epsilon)\frac{\log n}{n})\textrm{ is connected})=0. \end{array}

Last time, I explained the proof of the second sentence. Now I explain the first, which is a bit harder. At the time, it was revolutionary. Nowadays, it looks easy. Erdös and Rényi prove a sharper result: almost surely, when one throws edges one at a time, the graph becomes connected when the last isolated vertex disappears.

Proof: Let us estimate the expectation of the number of connected components. It is sufficient to consider connected components of size {\leq n/2}. Fix {k\leq n/2} and count connected components of size exactly {k}.

\displaystyle  \begin{array}{rcl}  \mathop{\mathbb E}(\textrm{number if connected components of size }k) &\leq& \begin{pmatrix}n\\ k \end{pmatrix}(1-p)^{k(n-k)}\\ &\leq&(\frac{ne}{k})^k e^{-k(n-k)p} \end{array}

which tends to {0} since {e^{-np}=O(n^{-1-\epsilon})}. And the sum from {k=1} to {k=n/2} also tends to {0}. Note that the largest term is for {k=1}. \Box

Note that {G} is connected iff the left kernel of its adjacency matrix is trivial (i.e. generated by the all one’s vector {1}).

2. Random simplicial complexes

With Roy Meshulam. What is the analogue of {G(n,p)} ? Here is a first model, denoted by {X_d (n,p)}. Start with a complete {(d-1)}-dimensional simplicial complex on {n} vertices (i.e., the {d-1}-skeleton of the {n-1} simplex). Then throw each {d}-face independently with probability {p}.

2.1. (Co-)homology

Form the following matrix: {\begin{pmatrix}n\\ d\end{pmatrix}} rows, roughly {p\begin{pmatrix}n\\ d+1\end{pmatrix}} columns, entry {0} or {1} according to incidence of a {d-1}-face with a selected {d}-face.

This is the matrix of the boundary operator {\partial_d} on {{\mathbb Z}/2{\mathbb Z}}-valued {d}-chains, expressed in the natural basis of simplices. For us, the analogue of graph connectivity is the vanishing of {(d-1)}-cohomology. I.e. triviality of the left kernel of {\partial}. There is a trivial kernel, the image of {\partial^{\top}} from {(d-1)}-cochains so the point is whether the left kernel is larger than this image or not.

Theorem 2 (Linial, Meshulam) The threshold for the vanishing of {(d-1)}-cohomology with {{\mathbb Z}/2{\mathbb Z}} coefficients in {X_d (n,p)} is {p=d\frac{\log n}{n}}.

There is a generalization for other finite coefficient fields (Linial, Meshulam, Wallach). We don’t know about {{\mathbb Z}} coefficients.

Proof: For {d=2}, for simplicity.

Easy: if {p\leq(1-\epsilon)\frac{\log n}{n}}, then {H^1 \not=0}. Indeed, the same coupon collector argument gives a vanishing line in the {\partial} matrix.

Conversely, assume that {p\geq(1+\epsilon)\frac{\log n}{n}}. There will be a union bound. Before, one must reduce the number of bad events, by getting rid of the trivial kernel. Each cut {S} of the complete graph {K_n} determines a vector {u_S} in the left kernel of the {\partial} matrix. As a chain, {u_S} is the sum of edges joining {S} to {\bar{S}}. These generate a {2^{\begin{pmatrix}n\\2\end{pmatrix}}}-dimensional subspace {U} of the kernel. So we need only argue on a complement of {U}. For every {z} in the kernel, pick {S} such that {z+u_S} is closest to {z} in Hamming distance. The resulting vector {z'} has the following property: For every cut {W}, {z'} has {\leq \frac{1}{2}|W||\bar{W}|} edges. Call such vectors special.

We are going to estimate (and later sum over) for all special vectors {z} the probability that {z} belongs in the left kernel. Let {z} be a special {1}-cochain. Think of it as a collection of edges. Let {B(z)} be the set of {2}-faces which have odd incidence with {z}, i.e. which contain either {1} or {3} edges of {z}. Note that {z} is in the left kernel of {\partial} iff for every selected {2}-face {P}, the incidence of {z} and {P} is even. In other words, {z} is in the left kernel iff no face from {B(z)} is chosen. So

\displaystyle  \begin{array}{rcl}  \mathop{\mathbb P}(z\textrm{in left kernel})\leq (1-p)^{|B(z)|}. \end{array}

Lemma 3 If {z} is special, then

\displaystyle  \begin{array}{rcl}  |B(z)|\geq \frac{1}{6}n|z|, \end{array}

where {|z|} is the number of edges of {z}.

For instance, if {z=u_S} is the set of edges across a cut, {B(z)=0}.

Proof: of Lemma. View {z} as a subgraph. Let {x} be a vertex of {z}. Then degree {d(x)\leq \frac{n-1}{2}} (use specialness for the cut {W=\{x\}}). Let {\Gamma(x)} be the set of neighbors of {x} in {z}. Consider {W=\{x\}\cup\Gamma(x)}. The number of edges joining {W} to {\bar{W}} is

\displaystyle  \begin{array}{rcl}  e(W,\bar{W})\leq\frac{1}{2}d(x)(n-d(x)+1). \end{array}

Let {B_x (z)} be the set of faces containing {x} with an odd intersection with {z}. Then

\displaystyle  \begin{array}{rcl}  |B_x (z)|\geq e(W,\bar{W}) \end{array}


\displaystyle  \begin{array}{rcl}  3|B(z)|=\sum_{x}|B_x (z)|\geq\sum_{x}\frac{1}{2}d(x)(n-d(x)+1)\geq\frac{n}{2}\sum_{x}d(x)=n|z|. \end{array}


Proof of Theorem 2 is easy to complete now. \Box

Remark 1 Connection with recent work of Gromov related to old work of Boros and Furedi, Matousek and Wagner ?

2.2. Cycles

Remark 2 The right kernel of {\partial}, in the case of graphs, is the cycle space. What is the critical {p} for a nonzero right kernel ?

For graphs, it is the first appearance of a cycle. Assume {p=\frac{\alpha}{n}}. Let {k\geq 3}. Then

\displaystyle  \begin{array}{rcl}  \mathop{\mathbb E}(\textrm{number of }k-\textrm{cycles in }G(n,\frac{\alpha}{n})=n(n+1)\cdots(n-k+1)(\frac{\alpha}{n})^k =\Theta(1). \end{array}

So the answer is {1/n} for graphs.

In fact, a more drastic transition occurs at {p=n^{-1}}. Initially, all connected components have cardinality {O(\log n)}, and are either trees or unicyclic. Beyond, there is almost surely a giant component, i.e. of size {\Omega(n)}, [ER].

2.3. Collapsibility

Alternatively, a graph contains no cycles iff it is collapsible, i.e. can be reduced to isolated vertices by a sequence of elementary collapses. Collapsibility extends to higher dimensions as follows.

Definition 4 In a simplicial complex {X}, an elementary collapse is possible when a {(d-1)}-face is covered by a unique {d}-face. The collapse consists in removing the {d}-face.

Say {X} is collapsible if by a sequence of elementary collapses, all {d}-faces can be removed.

Matrixwise, this amounts to removing a row and a column.

Example 1 The standard triangulation of the real projective plane.

Every edge is covered twice. So no place to start collapsing. In fact, {H_2 (X,{\mathbb Z}/2{\mathbb Z})\not=0}, whereas {H_2 (X,{\mathbb Q})=0}.

Remark 3 Certain things do not generalize easily to higher dimensions. For instance, the matrix of a connected graph has rank {n-1}. Subsets of column vectors forming a basis the the range of the matrix are in {1-1} correspondence with spanning trees. Spanning trees can easily be counted.

The following conjecture expresses a sharp contrast between graphs and higher dimensional complexes.

Conjecture: The threshold for collapsibility in {X_d (n,p)} is {p=\Theta(\frac{\log d}{n})}.

The threshold for vanishing of {d}-homology in {X_d (n,p)} is {p=\Theta(\frac{d}{n})}.

3. Other models of random graphs

3.1. Random {d}-regular graphs

In {G(n,p)}, a typical graph is unlikely to be {d}-regular.

The configuration model. Each vertex comes with {d} half-edges, and we randomly pair the half-edges. We do not like loops or parallel edges. Since {\mathop{\mathbb P}(\textrm{no loops nor parallel edges})\geq exp(-O(d^2))}, so one can condition on this event.

The random permutation model. Pick at random {d/2} permutations {\pi_1 ,\ldots,\pi_d}.

The two models gives different probability distributions, but they have the same sets of small probability (Wormald, Kim).

3.2. Random lifts of graphs

A lift is a covering map {H\rightarrow G} between graphs. For finite graphs, covering=local homeomorphism. Above vertices, fibers have the same number of elements, called the degree of the covering. Above edges, edges of the lift form a perfect matching between fibers of vertices.

Let {L_n (G)} denote the set of degree {n} lifts of graph {G}.

Question: What are the typical properties of graphs in {L_n (G)} ?

Remark 4 Are they connected ? If {e(G)=v(G)-1} (i.e. {G} is a tree), then all lifts are disconnected.

If {e(G)=v(G)} (i.e. {G} is a cycle), then {\mathop{\mathbb P}(H\textrm{ is connected})=\frac{1}{n}}. Indeed, the lift depends on one single permutation, and the question is wether this permutation is a cycle or not.

Otherwise, lifts are typicly connected.

Definition 5 Say {H} is {k}-connected if it remains connected when {<k} vertices are removed.

Theorem 6 (Amit, Linial) If the smallest vertex degree {\delta(G)\geq 3}, then asymptotically almost surely every {n}-lift of {G} is {\delta}-connected.

Theorem 7 (Linial, Rozenman) For every connected graph {G}, one of the two following holds.

  1. Almost every {n}-lift of {G} has a perfect matching.
  2. Almost no {n}-lift of {G} has a perfect matching.

Question: Does having a Hamiltonian cycle satisfy a {0-1} law in {L_n (G)} ?

Question: Are graphs in {L_n (K_5)} asymptotically almost surely Hamiltonian ?

Question: Is there a typical chromatic number for graphs in {L_n (K_5)} ?

We can show that graphs in {L_n (K_5} minus an edge{)} typically are {3}-colorable.

Many algorithmic problems turn out to be easy for random graphs. Lifts of a given graph have a mixed personality: they have some random behaviour, but also remember where they are coming from.

Guy Kindler: The isomorphism problem is built into lifts. Indeed,

I would like to have a better understanding of the following old

Theorem 8 (Tom Leighton) Two graphs have a common covering space iff there have a finite common cover.

Question: How does the spectrum behave under lift ? Note that {\sigma(G)\subset \sigma(H)}.

Yonatan Bilu and I tried to construct explicit Ramanujan graphs, i.e. graphs with low second eigenvalue. A {2}-lift of {G} can be encoded in a signing of the adjacency matrix {A_G} of {G}. I.e. symmetrically replacing a few {1}‘s by {-1}.

Theorem 9 (Y. Bilu, Linial) For every {d}-regular graph {G}, there is a signing of {A_G} with spectral radius {\leq O((\log d)^{3/2}\sqrt{d-1}}.

Conjecture: Can one improve this to {\leq 2\sqrt{d-1}} ?

Example 2 Let {G} be a circular train track (degree {d=3}), change signs of traverses. This gives a lift with spectral radius {\sqrt{5}}, even smaller than {\sqrt{8}}.


[ER] Erdös, P.; Rényi, A; On the evolution of random graphs. Bull. Inst. Internat. Statist. 38 (1961), 343–347.


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