1. Wonderful subjects that I will not discuss
Here are nice features of the combinatorics if graphs that should extend to higher dimensions:
1.1. Structural combinatorics: the Robertson-Seymour forbidden minor theorem
It is a hard theorem (proof spread over 20 papers, proof completed in the mid ’90s, unsuccessful attempts to simplify it), solving Wagner’s conjecture.
Definition 1 Say is a minor of graph if can be obtained by contraction and deletion of edges in .
Theorem 2 (Kuratowski-Wagner). A graph is planar iff it does not have or as minors.
In particular, planar graphs is a minor-closed family of graphs.
Theorem 3 (Robertson-Seymour). Every minor-closed family of graphs has a finite list of obstructions, i.e. there exists a finite family of graphs such that iff no is a minor of .
1.2. Extremal combinatorics: 1. Turán’s theorem
Question: What is the largest number of edges in an -vertex graph with no -clique ?
Goes back to the 1930s. Mantel solved .
Definition 4 Let be the largest number of edges in an -vertex graph with no subgraph isomorphic to . Similarly, if is a family of graphs, let be the largest number of edges in an -vertex graph with no subgraph isomorphic to an element of .
Theorem 5 (Turán). .
Proof: Construct a graph by connecting clouds of size . Every vertex of a cloud is connected to exactly one vertex in all other clouds. gives .
Conversely, Assume that does not contain . We show that there is a graph on the same vertex set such that the chromatic number and for every vertex , . This gives a This is proven by induction . Let be the vertex of of highest degree. For each which is not a neighborhood of , kill all edges emanating from and instead, connect to all neighbors of .
Theorem 6 (Erdös and Stone). For every integers , , for every , if , every -vertex graph with edges contains a copy of .
(Erdös and Simonovitz). For every finite collection of graphs ,
where is the minimum of chromatic numbers of elements of .
In other words, general minor-free families of graphs behave as planar graphs, as soon as the minimum chromatic number of excluded minors are . Note that when the minimal chromatic number is , the theorem leaves a big gap.
Here is one of the rare cases where one knows exactly . Let denote the -cycle.
Theorem 7 .
Proof: The projective plane over a finite field of order does not contain . It has vertices and edges.
Conversely, let be a graph containing no -cycles. Claim:
By convexity, since the average degree in is ,
and this gives const. .
1.3. Extremal combinatorics: 2. the girth
Definition 8 Define shortest cycle length in . Let
The following bound follows from our discussion of .
Example 1 .
Current world record is held by Xavier Dahan and Jean-Pierre Tillich (a few weeks ago).
they improve on Lubotzky, Philipps and Sarnak’s .
It one of the rare case where deterministic methods beat probabilistic methods.
Conjecture: There exists such that the upper bound (known as the Moore bound) can be replaced by .
Evidence ? This bound is straightforward. Indeed, up to scale , the graph is a tree, so -balls contain exactly vertices.
The Moore bound is sharp for the Petersen graph, girth , -vertices, for projective planes. Such examples play against my conjecture. For other values of parameters, the Moore bound has been improved by , but not . This indicates that we hardly understand what is going on.
Here is an analogy with coding theory suggested to me by Shlomo Hoory.
Definition 9 Let be a binary code. Its rate is . Its distance (see ‘s talk last week) is , where Hamming distance is used.
The rate The distance tells us which fraction of erroneous bits is tolerated by the code, i.e.
Definition 10 Let
There is an easy lower bound, the Gilbert-Varshamov bound, and an easy upper bound, provided by sphere packing. It is sometimes sharp, for perfect codes. These perfect codes have been classified. There is a sharper LP based upper bound, which, like the Gilbert-Varshamov lower bound, vanishes at and higher. The Moore bound is an analogue of the rough sphere packing bound. This is why I expect that it can be improved, in spite of existence of small families of examples where it is sharp.
Let be the universal covering based a some vertex . If is -regular, so is . View as a coloring of vertices of . Then is the minimal distance of points with the same color. This is similar to the coding problem. However, there exist colorings of the tree which make the analogue of Moore bound sharp. Indeed, there is enough room (non amenability) in the tree to do that. But these colorings are not periodic.
1.4. Probabilistic combinatorics: Ramsey numbers
Definition 11 Let , be integers. Let be the minimal such that the following holds: in every coloring of the vertices of , there is either a blue or a red .
Example 2 .
Theorem 12 (Ramsey). .
This is asymptotically sharp if . This is our first illustration of the probabilistic method. The method is like a telescope for the astronomer or a microscope for the bioogist. It allows to immerse oneself in the world of graphs without looking at any graph individually.
Theorem 13 Every -vertex graph contains either a clique or an anti-clique (aka independent set) of size . Conversely, there exits graphs whedre no clique nor anti-clique can have size .
Proof: Let denote the set of all -vertex graphs on vertex set . The measure on consists in putting an edge between a pair of vertices independantly at random with probability . Here, is sufficient. Let be the “number of size cliques in ” random variable. Let be the “number of size anti-cliques in ” random variable. We compute . For every subset of size , let if is a clique, otherwise. Then
Choose . This makes . In the same manner, , so . So there exists a graph with , i.e. no -clique, no -anticlique.
Guy Kindler: Deterministic constructions do not reach these bounds. The best, up to date, are due to Barak, Rao, Shaltiel, Wigderson, elaborating on [BKSSW].
Theorem 14 .
This has a beautiful proof. For , with do not even know the right exponent is . Ramsey’s theorem gives . To get a lower bound, it seems that the model does not help. I believe that an other model of random graph should be used.
Big graphs arise in biology. On my T-shirt, you can see a protein-protein interaction graph (a present of my wife, who is bio-informatician). There is hope to extract from such graph biological information. It is not clear that models of random graphs that mathelaticians like will be adapted to the needs of biology. Nevertheless, let us continue with .
Theorem 15 (Erdös). For all and , there exist graphs with and .
This is something one cannot see with naked eye. Locally, a graph with large girth is nothing but a tree, which has low chromatic number.
2. Threshold phenomena
Early 1960s : Erdös and Rényi. Start throwing edges at random, and look how the graph evolves.
- When does the graph contains a cycle ?
- When does it become connected ?
It is equivalent to studying with depending on .
Theorem 16 The critical probability of graph connectivity is . I.e.,
Proof: Coupon collector argument. We show that with positive probability, there exist isolated vertices. Let “number of isolated vertices” random variables. Then . Then
tends to zero if .
One observes what physicists would call phase transitions (E. Friedgut, G. Kalai). For every monotone graph property , as a function of , the property that an -vertex random graph satisfies increases brutally from nearly to nearly . This sharp threshold follow from the KKL theorem.
2.1. Towards higher dimensions
Given a set of vertices, a simplicial complex is a subset of which is closed under taking subsets. The elements of are called faces of the simplicial complex. Dimension is the maximal dimension (i.e. ) of faces.
Here is a sample extremal problem in higher dimensions.
Theorem 17 (Brown, Erdös, Sós). The largest number of -faces a -dimensional simplicial complex can have without containing a subcomplex homeomorphic to the -sphere is .
Conjecture. The same is true when the sphere is replaced with a torus.
R. Meshulam and I can prove the upper bound. If there are faces, typical links have edges, so for some pair of adjacent vertices, links have edges in common, so at least a cycle un common.