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}$

so

$\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}$

$\Box$

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 ${ 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}}$.

References

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