Combinatorics (Fall 2010)/Extremal graphs

Extremal Graph Theory

Mantel's theorem

We consider a typical extremal problem for graphs: the largest possible number of edges of triangle-free graphs, i.e. graphs contains no [math]\displaystyle{ K_3 }[/math].

Theorem (Mantel 1907)

Suppose [math]\displaystyle{ G(V,E) }[/math] is graph on [math]\displaystyle{ n }[/math] vertice without triangles. Then [math]\displaystyle{ |E|\le\frac{n^2}{4} }[/math].

First proof. (pigeonhole principle) We prove an equivalent theorem: Any [math]\displaystyle{ G(V,E) }[/math] with [math]\displaystyle{ |V|=n }[/math] and [math]\displaystyle{ |E|\gt \frac{n^2}{4} }[/math] must have a triangle. Use induction on [math]\displaystyle{ n }[/math]. The theorem holds trivially for [math]\displaystyle{ n\le 3 }[/math]. Induction hypothesis: assume the theorem hold for [math]\displaystyle{ |V|\le n-1 }[/math]. For [math]\displaystyle{ G }[/math] with [math]\displaystyle{ n }[/math] vertices, without loss of generality, assume that [math]\displaystyle{ |E|=\frac{n^2}{4}+1 }[/math], we will show that [math]\displaystyle{ G }[/math] must contain a triangle. Take a [math]\displaystyle{ uv\in E }[/math], and let [math]\displaystyle{ H }[/math] be the subgraph of [math]\displaystyle{ G }[/math] induced by [math]\displaystyle{ V\setminus \{u,v\} }[/math]. Clearly, [math]\displaystyle{ H }[/math] has [math]\displaystyle{ n-2 }[/math] vertices. Case.1: If [math]\displaystyle{ H }[/math] has [math]\displaystyle{ \gt \frac{(n-2)^2}{4} }[/math] edges, then by the induction hypothesis, [math]\displaystyle{ H }[/math] has a triangle. Case.2: If [math]\displaystyle{ H }[/math] has [math]\displaystyle{ \le\frac{(n-2)^2}{4} }[/math] edges, then at least [math]\displaystyle{ \left(\frac{n^2}{4}+1\right)-\frac{(n-2)^2}{4}-1=n-1 }[/math] edges are between [math]\displaystyle{ H }[/math] and [math]\displaystyle{ \{u,v\} }[/math]. By pigeonhole principle, there must be a vertex in [math]\displaystyle{ H }[/math] that is adjacent to both [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math]. Thus, [math]\displaystyle{ G }[/math] has a triangle. [math]\displaystyle{ \square }[/math]

Second proof. (Cauchy-Schwarz inequality) (Mantel's original proof) For any edge [math]\displaystyle{ uv\in E }[/math], no vertex can be a neighbor of both [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math], or otherwise there will be a triangle. Thus, for any edge [math]\displaystyle{ uv\in E }[/math], [math]\displaystyle{ d_u+d_v\le n }[/math]. It follows that [math]\displaystyle{ \sum_{uv\in E}(d_u+d_v)\le n|E| }[/math]. Note that [math]\displaystyle{ d(v) }[/math] appears exactly [math]\displaystyle{ d_v }[/math] times in the sum, so that [math]\displaystyle{ \sum_{uv\in E}(d_u+d_v)=\sum_{v\in V}d_v^2 }[/math]. Applying Chauchy-Schwarz inequality, [math]\displaystyle{ n|E|\ge\sum_{v\in V}d_v^2\ge\frac{\left(\sum_{v\in V}d_v\right)^2}{n}=\frac{4|E|^2}{n}, }[/math] where the last equation is due to Euler's equality [math]\displaystyle{ \sum_{v\in V}d_v=2|E| }[/math]. The theorem follows. [math]\displaystyle{ \square }[/math]

Third proof. (inequality of the arithmetic and geometric mean) Assume that [math]\displaystyle{ G(V,E) }[/math] has [math]\displaystyle{ |V|=n }[/math] vertices and is triangle-free. Let [math]\displaystyle{ A }[/math] be the largest independent set in [math]\displaystyle{ G }[/math] and let [math]\displaystyle{ \alpha=|A| }[/math]. Since [math]\displaystyle{ G }[/math] is triangle-free, for very vertex [math]\displaystyle{ v }[/math], all its neighbors must form an independent set, thus [math]\displaystyle{ d(v)\le \alpha }[/math] for all [math]\displaystyle{ v\in V }[/math]. Take [math]\displaystyle{ B=V\setminus A }[/math] and let [math]\displaystyle{ \beta=|B| }[/math]. Since [math]\displaystyle{ A }[/math] is an independent set, all edges in [math]\displaystyle{ E }[/math] must have at least one endpoint in [math]\displaystyle{ B }[/math]. Counting the edges in [math]\displaystyle{ E }[/math] according to their endpoints in [math]\displaystyle{ B }[/math], we obtain [math]\displaystyle{ |E|\le\sum_{v\in B}d_v }[/math]. By the inequality of the arithmetic and geometric mean, [math]\displaystyle{ |E|\le\sum_{v\in B}d_v\le\alpha\beta\le\left(\frac{\alpha+\beta}{2}\right)^2=\frac{n^2}{4} }[/math]. [math]\displaystyle{ \square }[/math]

Turán's theorem

Theorem (Turán 1941)

Let [math]\displaystyle{ G(V,E) }[/math] be a graph with [math]\displaystyle{ |V|=n }[/math]. If [math]\displaystyle{ G }[/math] has no [math]\displaystyle{ r }[/math]-clique, [math]\displaystyle{ k\ge 2 }[/math], then [math]\displaystyle{ |E|\le\frac{r-2}{2(r-1)}n^2 }[/math].

First proof. (induction) (Turán's original proof) [math]\displaystyle{ \square }[/math]

Second proof. (weight shifting) (due to Motzkin and Straus) [math]\displaystyle{ \square }[/math]

Third proof. (the probabilistic method) (due to Alon and Spencer) [math]\displaystyle{ \square }[/math]

Fourth proof. Let [math]\displaystyle{ G(V,E) }[/math] be a [math]\displaystyle{ r }[/math]-clique-free graph on [math]\displaystyle{ n }[/math] vertices with a maximum number of edges. Claim: [math]\displaystyle{ G }[/math] does not contain three vertices [math]\displaystyle{ u,v,w }[/math] such that [math]\displaystyle{ uv\in E }[/math] but [math]\displaystyle{ uw\not\in E, vw\not\in E }[/math]. Suppose otherwise. There are two cases. Case.1: [math]\displaystyle{ d(w)\lt d(u) }[/math] or [math]\displaystyle{ d(w)\lt d(v) }[/math]. Without loss of generality, suppose that [math]\displaystyle{ d(w)\lt d(u) }[/math]. We duplicate [math]\displaystyle{ u }[/math] by creating a new vertex [math]\displaystyle{ u' }[/math] which has exactly the same neighbors as [math]\displaystyle{ u }[/math] (but [math]\displaystyle{ uu' }[/math] is not an edge). Such duplication will not increase the clique size. We then remove [math]\displaystyle{ w }[/math]. The resulting graph [math]\displaystyle{ G' }[/math] is still [math]\displaystyle{ r }[/math]-clique-free, and has [math]\displaystyle{ n }[/math] vertices. The number of edges in [math]\displaystyle{ G' }[/math] is [math]\displaystyle{ |E(G')|=|E(G)|+d(u)-d(w)\gt |E(G)|\, }[/math], which contradicts the assumption that [math]\displaystyle{ |E(G)| }[/math] is maximal. Case.2: [math]\displaystyle{ d(w)\ge d(u) }[/math] and [math]\displaystyle{ d(w)\ge d(v) }[/math]. Duplicate [math]\displaystyle{ w }[/math] twice and delete [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math]. The new graph [math]\displaystyle{ G' }[/math] has no [math]\displaystyle{ r }[/math]-clique, and the number of edges is [math]\displaystyle{ |E(G')|=|E(G)|+2d(w)-(d(u)+d(v)+1)\gt |E(G)|\, }[/math]. Contradiction again. The claim implies that [math]\displaystyle{ uv\not\in E }[/math] defines an equivalence relation on vertices (to be more precise, it guarantees the transitivity of the relation, while the reflexivity and symmetry hold directly). Graph [math]\displaystyle{ G }[/math] must be a complete multipartite graph [math]\displaystyle{ K_{n_1,n_2,\ldots,n_{r-1}} }[/math] with [math]\displaystyle{ n_1+n_2+\cdots +n_{r-1}=n }[/math]. Optimize the edge number, we have the Turán graph. [math]\displaystyle{ \square }[/math]

Erdős–Stone theorem

Fundamental theorem of extremal graph theory (Erdős–Stone 1946)

For any integers [math]\displaystyle{ r\ge 2 }[/math] and [math]\displaystyle{ s\ge 1 }[/math], and any [math]\displaystyle{ \epsilon\gt 0 }[/math], there exists an [math]\displaystyle{ N_0 }[/math] such that every graph with [math]\displaystyle{ n\ge N_0 }[/math] vertices and at least [math]\displaystyle{ \left(\frac{r-2}{2(r-1)}+\epsilon\right)n^2 }[/math] edges contains [math]\displaystyle{ K_{r,s} }[/math] as a subgraph, i.e., [math]\displaystyle{ \mathrm{ex}(n,K_{s,r})\le \left(\frac{r-2}{2(r-1)}+o(1)\right)n^2 }[/math].

Corollary

For every nonempty graph [math]\displaystyle{ H }[/math], [math]\displaystyle{ \lim_{n\rightarrow\infty}\frac{\mathrm{ex}(n,H)}{{n\choose 2}}=\frac{\chi(H)-2}{\chi(H)-1} }[/math].