Last time, I went through fundamental results in extremal graph theory and explained the 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 is , i.e.
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 . Fix and count connected components of size exactly .
which tends to since . And the sum from to also tends to . Note that the largest term is for .
Note that is connected iff the left kernel of its adjacency matrix is trivial (i.e. generated by the all one’s vector ).
2. Random simplicial complexes
With Roy Meshulam. What is the analogue of ? Here is a first model, denoted by . Start with a complete -dimensional simplicial complex on vertices (i.e., the -skeleton of the simplex). Then throw each -face independently with probability .
Form the following matrix: rows, roughly columns, entry or according to incidence of a -face with a selected -face.
This is the matrix of the boundary operator on -valued -chains, expressed in the natural basis of simplices. For us, the analogue of graph connectivity is the vanishing of -cohomology. I.e. triviality of the left kernel of . There is a trivial kernel, the image of from -cochains so the point is whether the left kernel is larger than this image or not.
There is a generalization for other finite coefficient fields (Linial, Meshulam, Wallach). We don’t know about coefficients.
Proof: For , for simplicity.
Easy: if , then . Indeed, the same coupon collector argument gives a vanishing line in the matrix.
Conversely, assume that . There will be a union bound. Before, one must reduce the number of bad events, by getting rid of the trivial kernel. Each cut of the complete graph determines a vector in the left kernel of the matrix. As a chain, is the sum of edges joining to . These generate a -dimensional subspace of the kernel. So we need only argue on a complement of . For every in the kernel, pick such that is closest to in Hamming distance. The resulting vector has the following property: For every cut , has edges. Call such vectors special.
We are going to estimate (and later sum over) for all special vectors the probability that belongs in the left kernel. Let be a special -cochain. Think of it as a collection of edges. Let be the set of -faces which have odd incidence with , i.e. which contain either or edges of . Note that is in the left kernel of iff for every selected -face , the incidence of and is even. In other words, is in the left kernel iff no face from is chosen. So
Lemma 3 If is special, then
where is the number of edges of .
For instance, if is the set of edges across a cut, .
Proof: of Lemma. View as a subgraph. Let be a vertex of . Then degree (use specialness for the cut ). Let be the set of neighbors of in . Consider . The number of edges joining to is
Let be the set of faces containing with an odd intersection with . Then
Proof of Theorem 2 is easy to complete now.
Remark 1 Connection with recent work of Gromov related to old work of Boros and Furedi, Matousek and Wagner ?
Remark 2 The right kernel of , in the case of graphs, is the cycle space. What is the critical for a nonzero right kernel ?
For graphs, it is the first appearance of a cycle. Assume . Let . Then
So the answer is for graphs.
In fact, a more drastic transition occurs at . Initially, all connected components have cardinality , and are either trees or unicyclic. Beyond, there is almost surely a giant component, i.e. of size , [ER].
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 , an elementary collapse is possible when a -face is covered by a unique -face. The collapse consists in removing the -face.
Say is collapsible if by a sequence of elementary collapses, all -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, , whereas .
Remark 3 Certain things do not generalize easily to higher dimensions. For instance, the matrix of a connected graph has rank . Subsets of column vectors forming a basis the the range of the matrix are in 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 is .
The threshold for vanishing of -homology in is .
3. Other models of random graphs
3.1. Random -regular graphs
In , a typical graph is unlikely to be -regular.
The configuration model. Each vertex comes with half-edges, and we randomly pair the half-edges. We do not like loops or parallel edges. Since , so one can condition on this event.
The random permutation model. Pick at random permutations .
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 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 denote the set of degree lifts of graph .
Question: What are the typical properties of graphs in ?
Remark 4 Are they connected ? If (i.e. is a tree), then all lifts are disconnected.
If (i.e. is a cycle), then . 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 is -connected if it remains connected when vertices are removed.
Theorem 6 (Amit, Linial) If the smallest vertex degree , then asymptotically almost surely every -lift of is -connected.
Theorem 7 (Linial, Rozenman) For every connected graph , one of the two following holds.
- Almost every -lift of has a perfect matching.
- Almost no -lift of has a perfect matching.
Question: Does having a Hamiltonian cycle satisfy a law in ?
Question: Are graphs in asymptotically almost surely Hamiltonian ?
Question: Is there a typical chromatic number for graphs in ?
We can show that graphs in minus an edge typically are -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 .
Yonatan Bilu and I tried to construct explicit Ramanujan graphs, i.e. graphs with low second eigenvalue. A -lift of can be encoded in a signing of the adjacency matrix of . I.e. symmetrically replacing a few ‘s by .
Theorem 9 (Y. Bilu, Linial) For every -regular graph , there is a signing of with spectral radius .
Conjecture: Can one improve this to ?
Example 2 Let be a circular train track (degree ), change signs of traverses. This gives a lift with spectral radius , even smaller than .