Notes of Nati Linial’s lecture nr 1


1. Wonderful subjects that I will not discuss


Here are nice features of the combinatorics if graphs that should extend to higher dimensions:

  • Structural.
  • Extremal.
  • Probabilistic.


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 {H} is a minor of graph {G} if {H} can be obtained by contraction and deletion of edges in {G}.


Theorem 2 (Kuratowski-Wagner). A graph is planar iff it does not have {K_5} or {K_{3,3}} as minors.


In particular, planar graphs is a minor-closed family of graphs.

Theorem 3 (Robertson-Seymour). Every minor-closed family {\mathcal{F}} of graphs has a finite list of obstructions, i.e. there exists a finite family of graphs {G_1 ,\ldots,G_k} such that {G\in\mathcal{F}} iff no {G_i} is a minor of {G}.


1.2. Extremal combinatorics: 1. Turán’s theorem


Question: What is the largest number of edges in an {n}-vertex graph with no {r}-clique ?

Goes back to the 1930s. Mantel solved {r=3}.

More generally

Definition 4 Let {ex(n,H)} be the largest number of edges in an {n}-vertex graph with no subgraph isomorphic to {H}. Similarly, if {\mathcal{F}} is a family of graphs, let {ex(n,\mathcal{F})} be the largest number of edges in an {n}-vertex graph with no subgraph isomorphic to an element of {\mathcal{F}}.


Theorem 5 (Turán). {ex(n,K_r)=\begin{pmatrix} n\\ 2 \end{pmatrix}(\frac{r-2}{r-1}+o(1))}.


Proof: Construct a graph {K_r (t)} by connecting {r-1} clouds of size {t}. Every vertex of a cloud is connected to exactly one vertex in all other clouds. {t=\frac{n}{r-1}} gives {ex(n,K_r)\geq\begin{pmatrix} n\\ 2 \end{pmatrix}\frac{r-2}{r-1}}.

Conversely, Assume that {G} does not contain {K_r}. We show that there is a graph {H} on the same vertex set such that the chromatic number {\chi(H)\leq r-1} and for every vertex {x}, {degree_{H}(x)\geq degree_{G}(x)}. This gives a This is proven by induction {r}. Let {x^*} be the vertex of {G} of highest degree. For each {y} which is not a neighborhood of {x^*}, kill all edges emanating from {y} and instead, connect {y} to all neighbors of {x^*}. \Box

Theorem 6 (Erdös and Stone). For every integers {t}, {r}, for every {\epsilon>0}, if {n>n_0 (r,t,\epsilon)}, every {n}-vertex graph {G} with {\geq \begin{pmatrix} n\\ 2 \end{pmatrix}(\frac{r-2}{r-1}+\epsilon)} edges contains a copy of {K_r (t)}.

(Erdös and Simonovitz). For every finite collection of graphs {\mathcal{F}},

\displaystyle  \begin{array}{rcl}  ex(n,\mathcal{F})=\begin{pmatrix}n\\ 2\end{pmatrix}(\frac{r-2}{r-1}+o(1)), \end{array}

where {r} is the minimum of chromatic numbers of elements of {\mathcal{F}}.


In other words, general minor-free families of graphs behave as planar graphs, as soon as the minimum chromatic number of excluded minors are {\geq 3}. Note that when the minimal chromatic number is {2}, the theorem leaves a big gap.

Here is one of the rare cases where one knows exactly {ex}. Let {C_4} denote the {4}-cycle.

Theorem 7 {ex(n,C_4)=\Theta(n^{3/2})}.


Proof: The projective plane over a finite field of order {q} does not contain {C_4}. It has {n=2(q^{2}+q+1)} vertices and {(q+1)(q^{2}+q+1)} edges.

Conversely, let {G} be a graph containing no {4}-cycles. Claim:

\displaystyle  \begin{array}{rcl}  \sum_{x\in V}\begin{pmatrix}degree(x)\\ 2\end{pmatrix}\leq \begin{pmatrix} n\\ 2\end{pmatrix}. \end{array}

By convexity, since the average degree in {G} is {2e/n},

\displaystyle  \begin{array}{rcl}  \sum_{x\in V}\begin{pmatrix}degree(x)\\ 2\end{pmatrix}\geq \begin{pmatrix} 2e/n\\ 2\end{pmatrix}, \end{array}

and this gives {e\geq} const. {n^{3/2}}. \Box


1.3. Extremal combinatorics: 2. the girth


Definition 8 Define {girth(G)=} shortest cycle length in {G}. Let

\displaystyle  \begin{array}{rcl}  g(d,n)=\max\{girth(G)\,;\,G\textrm{ a }d\textrm{-regular }n\textrm{-vertex graph}\}. \end{array}


The following bound follows from our discussion of {C_4}.

Example 1 {g(\Theta(\sqrt{n}),n)=6}.


Current world record is held by Xavier Dahan and Jean-Pierre Tillich (a few weeks ago).

\displaystyle  \begin{array}{rcl}  (2+o(1))\frac{\log n}{\log (d-1)}\geq g(d,n)\geq (\frac{12}{7}-o(1))\frac{\log n}{\log (d-1)}, \end{array}

they improve on Lubotzky, Philipps and Sarnak’s {\frac{4}{3}}.

It one of the rare case where deterministic methods beat probabilistic methods.

Conjecture: There exists {\epsilon_0 >0} such that the upper bound (known as the Moore bound) can be replaced by {(2-\epsilon_0 +o(1))\frac{\log n}{\log (d-1)}}.

Evidence ? This bound is straightforward. Indeed, up to scale {g/2}, the graph is a tree, so {g/2}-balls contain exactly {d(d-1)^{g/2}} vertices.

The Moore bound is sharp for the Petersen graph, girth {5}, {10}-vertices, for projective planes. Such examples play against my conjecture. For other values of parameters, the Moore bound has been improved by {1}, but not {2}. 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 {C\subset\{ 0,1 \}^n} be a binary code. Its rate is {rate(C)=\frac{1}{n}\log_2 |C|}. Its distance (see ‘s talk last week) is {distance(C)=\frac{1}{n}\min\{|x-y|\,;\,x,\;y\in C\}}, 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

\displaystyle  \begin{array}{rcl}  r(\delta)=\limsup_{n\rightarrow\infty} \max\{rate(C)\,;\, C\subset\{ 0,1 \}^n ,\, distance (C)\geq \delta\}. \end{array}


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 {\delta=1/2} 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 {p:T\rightarrow G} be the universal covering based a some vertex {x}. If {G} is {d}-regular, so is {T}. View {p} as a coloring of vertices of {T}. Then {girth(G)} 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 {p}, {q\geq 2} be integers. Let {R(p,q)} be the minimal {N} such that the following holds: in every coloring of the vertices of {K_N}, there is either a blue {K_p} or a red {K_q}.


Example 2 {R(3,3)=6}.


Theorem 12 (Ramsey). {R(p,q)\leq \begin{pmatrix}p+q-2\\ p-1\end{pmatrix}}.


This is asymptotically sharp if {p=q}. 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 {n}-vertex graph contains either a clique or an anti-clique (aka independent set) of size {\geq (\frac{1}{2}-o(1))\log_2 n}. Conversely, there exits graphs whedre no clique nor anti-clique can have size {\geq (2+o(1))\log_2 n}.


Proof: Let {\Omega} denote the set of all {n}-vertex graphs on vertex set {[n]}. The {G(n,p)} measure on {\Omega} consists in putting an edge between a pair of vertices independantly at random with probability {p}. Here, {p=1/2} is sufficient. Let {X:\Omega\rightarrow{\mathbb N}} be the “number of size {k} cliques in {G}” random variable. Let {Y:\Omega\rightarrow{\mathbb N}} be the “number of size {k} anti-cliques in {G}” random variable. We compute {\mathop{\mathbb E}(X+Y)}. For every subset {E\subset[n]} of size {k}, let {X_S (G)=1} if {S} is a clique, {=0} otherwise. Then

\displaystyle  \begin{array}{rcl}  \mathop{\mathbb E}(X)=\sum_{S}\mathop{\mathbb E}(X_S)=\begin{pmatrix}n\\ k\end{pmatrix}\mathop{\mathbb P}(X_S =1)=\begin{pmatrix}n\\ k\end{pmatrix}2^{-k}. \end{array}

Choose {k=2\log n}. This makes {\begin{pmatrix}n\\ k\end{pmatrix}2^{-k}<1/2}. In the same manner, {\mathop{\mathbb E}(Y)<1/2}, so {\mathop{\mathbb E}(X+Y)<1}. So there exists a graph with {X(G)+Y(G)<1}, i.e. no {k}-clique, no {k}-anticlique. \Box

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 {R(n,3)=\Theta(\frac{n^2}{\log n})}.

This has a beautiful proof. For {k>3}, with do not even know the right exponent is {R(n,k)}. Ramsey’s theorem gives {R(n,4)\leq O(n^3)}. To get a lower bound, it seems that the {G(n,p)} 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 {G(n,p)}.

Theorem 15 (Erdös). For all {k} and {g}, there exist graphs {G} with {girth(G)\geq g} and {\chi(G)\geq k}.

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.

  1. When does the graph contains a cycle ?
  2. When does it become connected ?

It is equivalent to studying {G(n,p)} with {p} depending on {n}.

Theorem 16 The critical probability of graph connectivity 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}


Proof: Coupon collector argument. We show that with positive probability, there exist isolated vertices. Let {X=}“number of isolated vertices” random variables. Then {X=\sum_{i}X_i}. Then

\displaystyle  \begin{array}{rcl}  \mathop{\mathbb E}(X)=\sum_{i}\mathop{\mathbb E}(X_i)=n\mathop{\mathbb E}(X_1)=ne^{-pn} \end{array}

tends to zero if {p<(1-\epsilon)\frac{\log n}{n})}. \Box

One observes what physicists would call phase transitions (E. Friedgut, G. Kalai). For every monotone graph property {P}, as a function of {p=p(n)}, the property that an {n}-vertex random graph satisfies {P} increases brutally from nearly {0} to nearly {1}. This sharp threshold follow from the KKL theorem.


2.1. Towards higher dimensions


Given a set {V} of vertices, a simplicial complex is a subset {F} of {2^V} which is closed under taking subsets. The elements of {F} are called faces of the simplicial complex. Dimension is the maximal dimension (i.e. {|A|-1}) of faces.

Here is a sample extremal problem in higher dimensions.

Theorem 17 (Brown, Erdös, Sós). The largest number of {2}-faces a {2}-dimensional simplicial complex can have without containing a subcomplex homeomorphic to the {2}-sphere is {\Theta(n^{5/2})}.


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 {\geq n^{5/2}} faces, typical links have {\geq n^{3/2}} edges, so for some pair of adjacent vertices, links have {\geq (n^{3/2})^2/(n(n-1)/2)} edges in common, so at least a cycle un common.




[BKSSW] B. Barak, G. Kindler, R. Shaltiel, B. Sudakov, A. Wigderson; Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers and Extractors. J. ACM 57(4), 2010.



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