Combinatorics (Fall 2010)/Extremal graphs: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>WikiSysop
imported>WikiSysop
Line 16: Line 16:


{{Prooftitle|Third proof. (inequality of the arithmetic and geometric mean)|
{{Prooftitle|Third proof. (inequality of the arithmetic and geometric mean)|
Assume that <math>G(V,E)</math> has <math>|V|=2n</math> vertices and is triangle-free.
Assume that <math>G(V,E)</math> has <math>|V|=n</math> vertices and is triangle-free.


Let <math>A</math> be the largest independent set in <math>G</math> and let <math>\alpha=|A|</math>.  
Let <math>A</math> be the largest independent set in <math>G</math> and let <math>\alpha=|A|</math>.  
Line 23: Line 23:
Take <math>B=V\setminus A</math> and let <math>\beta=|B|</math>.
Take <math>B=V\setminus A</math> and let <math>\beta=|B|</math>.
Since <math>A</math> is an independent set, all edges in <math>E</math> must have at least one endpoint in <math>B</math>. Counting the edges in <math>E</math> according to their endpoints in <math>B</math>, we obtain <math>|E|\le\sum_{v\in B}d_v</math>. By the inequality of the arithmetic and geometric mean,
Since <math>A</math> is an independent set, all edges in <math>E</math> must have at least one endpoint in <math>B</math>. Counting the edges in <math>E</math> according to their endpoints in <math>B</math>, we obtain <math>|E|\le\sum_{v\in B}d_v</math>. By the inequality of the arithmetic and geometric mean,
:<math>|E|\le\sum_{v\in B}d_v\le\alpha\beta\le\left(\frac{\alpha+\beta}{2}\right)^2=n^2</math>.
:<math>|E|\le\sum_{v\in B}d_v\le\alpha\beta\le\left(\frac{\alpha+\beta}{2}\right)^2=\frac{n^2}{4}</math>.
}}
}}



Revision as of 12:43, 13 October 2010

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)
If a graph [math]\displaystyle{ G }[/math] on [math]\displaystyle{ 2n }[/math] vertices contains [math]\displaystyle{ n^2+1 }[/math] edges, then [math]\displaystyle{ G }[/math] contains a triangle.


First proof. (pigeonhole principle)
[math]\displaystyle{ \square }[/math]
Second proof. (Cauchy-Schwarz inequality)
[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{ (k+1) }[/math]-clique, [math]\displaystyle{ k\ge 2 }[/math], then
[math]\displaystyle{ |E|\le\left(1-\frac{1}{k}\right)\frac{n^2}{2} }[/math].
First proof. (induction)
[math]\displaystyle{ \square }[/math]
Second proof. (weight shifting)
[math]\displaystyle{ \square }[/math]
Third proof. (the probabilistic method)
[math]\displaystyle{ \square }[/math]
Fourth proof.

Let [math]\displaystyle{ G(V,E) }[/math] be a [math]\displaystyle{ (k+1) }[/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{ (k+1) }[/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{ (k+1) }[/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_k} }[/math] with [math]\displaystyle{ n_1+n_2+\cdots +n_k=n }[/math]. Optimize the edge number, we have the Turán graph.

[math]\displaystyle{ \square }[/math]

Erdős–Stone theorem

Cycle Structures

Girth

Hamiltonian cycle