TCS Wiki - User contributions [en]

Combinatorics (Fall 2010)/Extremal graphs

2010-10-14T07:14:17Z

172.21.1.240: /* Erdős–Stone theorem */

== 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>K_3</math>.

{{Theorem|Theorem (Mantel 1907)|
:Suppose <math>G(V,E)</math> is graph on <math>n</math> vertice without triangles. Then <math>|E|\le\frac{n^2}{4}</math>.
}}

{{Prooftitle|First proof. (pigeonhole principle)|
We prove an equivalent theorem: Any <math>G(V,E)</math> with <math>|V|=n</math> and <math>|E|>\frac{n^2}{4}</math> must have a triangle.

Use induction on <math>n</math>. The theorem holds trivially for <math>n\le 3</math>.

Induction hypothesis: assume the theorem hold for <math>|V|\le n-1</math>.

For <math>G</math> with <math>n</math> vertices, without loss of generality, assume that <math>|E|=\frac{n^2}{4}+1</math>, we will show that <math>G</math> must contain a triangle. Take a <math>uv\in E</math>, and let <math>H</math> be the subgraph of <math>G</math> induced by <math>V\setminus \{u,v\}</math>. Clearly, <math>H</math> has <math>n-2</math> vertices.
:'''Case.1:''' If <math>H</math> has <math>>\frac{(n-2)^2}{4}</math> edges, then by the induction hypothesis, <math>H</math> has a triangle.
:'''Case.2:''' If <math>H</math> has <math>\le\frac{(n-2)^2}{4}</math> edges, then at least <math>\left(\frac{n^2}{4}+1\right)-\frac{(n-2)^2}{4}-1=n-1</math> edges are between <math>H</math> and <math>\{u,v\}</math>. By pigeonhole principle, there must be a vertex in <math>H</math> that is adjacent to both <math>u</math> and <math>v</math>. Thus, <math>G</math> has a triangle.
}}

{{Prooftitle|Second proof. (Cauchy-Schwarz inequality)|(Mantel's original proof)
For any edge <math>uv\in E</math>, no vertex can be a neighbor of both <math>u</math> and <math>v</math>, or otherwise there will be a triangle. Thus, for any edge <math>uv\in E</math>, <math>d_u+d_v\le n</math>. It follows that
:<math>\sum_{uv\in E}(d_u+d_v)\le n|E|</math>.
Note that <math>d(v)</math> appears exactly <math>d_v</math> times in the sum, so that
:<math>\sum_{uv\in E}(d_u+d_v)=\sum_{v\in V}d_v^2</math>.
Applying Chauchy-Schwarz inequality,
:<math>
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>\sum_{v\in V}d_v=2|E|</math>. The theorem follows.
}}

{{Prooftitle|Third proof. (inequality of the arithmetic and geometric mean)|
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>.
Since <math>G</math> is triangle-free, for very vertex <math>v</math>, all its neighbors must form an independent set, thus <math>d(v)\le \alpha</math> for all <math>v\in V</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,
:<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>.
}}

=== Turán's theorem ===
{{Theorem|Theorem (Turán 1941)|
:Let <math>G(V,E)</math> be a graph with <math>|V|=n</math>. If <math>G</math> has no <math>r</math>-clique, <math>k\ge 2</math>, then
::<math>|E|\le\frac{r-2}{2(r-1)}n^2</math>.
}}

{{Prooftitle|First proof. (induction)|(Turán's original proof)
}}

{{Prooftitle|Second proof. (weight shifting)|(due to Motzkin and Straus)
}}

{{Prooftitle|Third proof. (the probabilistic method)|(due to Alon and Spencer)
}}

{{Prooftitle|Fourth proof.|
Let <math>G(V,E)</math> be a <math>r</math>-clique-free graph on <math>n</math> vertices with a maximum number of edges.
:'''Claim:''' <math>G</math> does not contain three vertices <math>u,v,w</math> such that <math>uv\in E</math> but <math>uw\not\in E, vw\not\in E</math>.
Suppose otherwise. There are two cases.
* '''Case.1:''' <math>d(w)<d(u)</math> or <math>d(w)<d(v)</math>. Without loss of generality, suppose that <math>d(w)<d(u)</math>. We duplicate <math>u</math> by creating a new vertex <math>u'</math> which has exactly the same neighbors as <math>u</math> (but <math>uu'</math> is not an edge). Such duplication will not increase the clique size. We then remove <math>w</math>. The resulting graph <math>G'</math> is still <math>r</math>-clique-free, and has <math>n</math> vertices. The number of edges in <math>G'</math> is
::<math>|E(G')|=|E(G)|+d(u)-d(w)>|E(G)|\,</math>,
:which contradicts the assumption that <math>|E(G)|</math> is maximal.
* '''Case.2:''' <math>d(w)\ge d(u)</math> and <math>d(w)\ge d(v)</math>. Duplicate <math>w</math> twice and delete <math>u</math> and <math>v</math>. The new graph <math>G'</math> has no <math>r</math>-clique, and the number of edges is
::<math>|E(G')|=|E(G)|+2d(w)-(d(u)+d(v)+1)>|E(G)|\,</math>.
:Contradiction again.

The claim implies that <math>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>G</math> must be a complete multipartite graph <math>K_{n_1,n_2,\ldots,n_{r-1}}</math> with <math>n_1+n_2+\cdots +n_{r-1}=n</math>. Optimize the edge number, we have the Turán graph.
}}

=== Erdős–Stone theorem ===
Let <math>K_s^r=K_{\underbrace{s,s,\cdots,s}_{r}}</math> be the complete <math>r</math>-partite graph with <math>s</math> vertices in each class, i.e., the Turán graph <math>T(rs,r)</math>.

{{Theorem|Fundamental theorem of extremal graph theory (Erdős–Stone 1946)|
:For any integers <math>r\ge 2</math> and <math>s\ge 1</math>, and any <math>\epsilon>0</math>, if <math>n</math> is sufficiently large then every graph on <math>n</math> vertices and with at least <math>\left(\frac{r-2}{2(r-1)}+\epsilon\right)n^2</math> edges contains <math>K_{r,s}</math> as a subgraph, i.e.,
:::<math>\mathrm{ex}(n,K_s^r)= \left(\frac{r-2}{2(r-1)}+o(1)\right)n^2</math>.
}}

{{Theorem|Corollary|
:For every nonempty graph <math>H</math>,
::<math>\lim_{n\rightarrow\infty}\frac{\mathrm{ex}(n,H)}{{n\choose 2}}=\frac{\chi(H)-2}{\chi(H)-1}</math>.
}}

== Cycle Structures ==
=== Girth ===

=== Hamiltonian cycle ===

Combinatorics (Fall 2010)/Extremal graphs

2010-10-14T07:04:04Z

172.21.1.240: /* Erdős–Stone theorem */

== 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>K_3</math>.

{{Theorem|Theorem (Mantel 1907)|
:Suppose <math>G(V,E)</math> is graph on <math>n</math> vertice without triangles. Then <math>|E|\le\frac{n^2}{4}</math>.
}}

{{Prooftitle|First proof. (pigeonhole principle)|
We prove an equivalent theorem: Any <math>G(V,E)</math> with <math>|V|=n</math> and <math>|E|>\frac{n^2}{4}</math> must have a triangle.

Use induction on <math>n</math>. The theorem holds trivially for <math>n\le 3</math>.

Induction hypothesis: assume the theorem hold for <math>|V|\le n-1</math>.

For <math>G</math> with <math>n</math> vertices, without loss of generality, assume that <math>|E|=\frac{n^2}{4}+1</math>, we will show that <math>G</math> must contain a triangle. Take a <math>uv\in E</math>, and let <math>H</math> be the subgraph of <math>G</math> induced by <math>V\setminus \{u,v\}</math>. Clearly, <math>H</math> has <math>n-2</math> vertices.
:'''Case.1:''' If <math>H</math> has <math>>\frac{(n-2)^2}{4}</math> edges, then by the induction hypothesis, <math>H</math> has a triangle.
:'''Case.2:''' If <math>H</math> has <math>\le\frac{(n-2)^2}{4}</math> edges, then at least <math>\left(\frac{n^2}{4}+1\right)-\frac{(n-2)^2}{4}-1=n-1</math> edges are between <math>H</math> and <math>\{u,v\}</math>. By pigeonhole principle, there must be a vertex in <math>H</math> that is adjacent to both <math>u</math> and <math>v</math>. Thus, <math>G</math> has a triangle.
}}

{{Prooftitle|Second proof. (Cauchy-Schwarz inequality)|(Mantel's original proof)
For any edge <math>uv\in E</math>, no vertex can be a neighbor of both <math>u</math> and <math>v</math>, or otherwise there will be a triangle. Thus, for any edge <math>uv\in E</math>, <math>d_u+d_v\le n</math>. It follows that
:<math>\sum_{uv\in E}(d_u+d_v)\le n|E|</math>.
Note that <math>d(v)</math> appears exactly <math>d_v</math> times in the sum, so that
:<math>\sum_{uv\in E}(d_u+d_v)=\sum_{v\in V}d_v^2</math>.
Applying Chauchy-Schwarz inequality,
:<math>
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>\sum_{v\in V}d_v=2|E|</math>. The theorem follows.
}}

{{Prooftitle|Third proof. (inequality of the arithmetic and geometric mean)|
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>.
Since <math>G</math> is triangle-free, for very vertex <math>v</math>, all its neighbors must form an independent set, thus <math>d(v)\le \alpha</math> for all <math>v\in V</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,
:<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>.
}}

=== Turán's theorem ===
{{Theorem|Theorem (Turán 1941)|
:Let <math>G(V,E)</math> be a graph with <math>|V|=n</math>. If <math>G</math> has no <math>r</math>-clique, <math>k\ge 2</math>, then
::<math>|E|\le\frac{r-2}{2(r-1)}n^2</math>.
}}

{{Prooftitle|First proof. (induction)|(Turán's original proof)
}}

{{Prooftitle|Second proof. (weight shifting)|(due to Motzkin and Straus)
}}

{{Prooftitle|Third proof. (the probabilistic method)|(due to Alon and Spencer)
}}

{{Prooftitle|Fourth proof.|
Let <math>G(V,E)</math> be a <math>r</math>-clique-free graph on <math>n</math> vertices with a maximum number of edges.
:'''Claim:''' <math>G</math> does not contain three vertices <math>u,v,w</math> such that <math>uv\in E</math> but <math>uw\not\in E, vw\not\in E</math>.
Suppose otherwise. There are two cases.
* '''Case.1:''' <math>d(w)<d(u)</math> or <math>d(w)<d(v)</math>. Without loss of generality, suppose that <math>d(w)<d(u)</math>. We duplicate <math>u</math> by creating a new vertex <math>u'</math> which has exactly the same neighbors as <math>u</math> (but <math>uu'</math> is not an edge). Such duplication will not increase the clique size. We then remove <math>w</math>. The resulting graph <math>G'</math> is still <math>r</math>-clique-free, and has <math>n</math> vertices. The number of edges in <math>G'</math> is
::<math>|E(G')|=|E(G)|+d(u)-d(w)>|E(G)|\,</math>,
:which contradicts the assumption that <math>|E(G)|</math> is maximal.
* '''Case.2:''' <math>d(w)\ge d(u)</math> and <math>d(w)\ge d(v)</math>. Duplicate <math>w</math> twice and delete <math>u</math> and <math>v</math>. The new graph <math>G'</math> has no <math>r</math>-clique, and the number of edges is
::<math>|E(G')|=|E(G)|+2d(w)-(d(u)+d(v)+1)>|E(G)|\,</math>.
:Contradiction again.

The claim implies that <math>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>G</math> must be a complete multipartite graph <math>K_{n_1,n_2,\ldots,n_{r-1}}</math> with <math>n_1+n_2+\cdots +n_{r-1}=n</math>. Optimize the edge number, we have the Turán graph.
}}

=== Erdős–Stone theorem ===

{{Theorem|Fundamental theorem of extremal graph theory (Erdős–Stone 1946)|
:For any integers <math>r\ge 2</math> and <math>s\ge 1</math>, and any <math>\epsilon>0</math>, if <math>n</math> is sufficiently large then every graph on <math>n</math> vertices and with at least <math>\left(\frac{r-2}{2(r-1)}+\epsilon\right)n^2</math> edges contains <math>K_{r,s}</math> as a subgraph, i.e.,
:::<math>\mathrm{ex}(n,K_{r,s})= \left(\frac{r-2}{2(r-1)}+o(1)\right)n^2</math>.
}}

{{Theorem|Corollary|
:For every nonempty graph <math>H</math>,
::<math>\lim_{n\rightarrow\infty}\frac{\mathrm{ex}(n,H)}{{n\choose 2}}=\frac{\chi(H)-2}{\chi(H)-1}</math>.
}}

== Cycle Structures ==
=== Girth ===

=== Hamiltonian cycle ===

Combinatorics (Fall 2010)/Extremal graphs

2010-10-14T07:00:05Z

172.21.1.240: /* Erdős–Stone theorem */

== 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>K_3</math>.

{{Theorem|Theorem (Mantel 1907)|
:Suppose <math>G(V,E)</math> is graph on <math>n</math> vertice without triangles. Then <math>|E|\le\frac{n^2}{4}</math>.
}}

{{Prooftitle|First proof. (pigeonhole principle)|
We prove an equivalent theorem: Any <math>G(V,E)</math> with <math>|V|=n</math> and <math>|E|>\frac{n^2}{4}</math> must have a triangle.

Use induction on <math>n</math>. The theorem holds trivially for <math>n\le 3</math>.

Induction hypothesis: assume the theorem hold for <math>|V|\le n-1</math>.

For <math>G</math> with <math>n</math> vertices, without loss of generality, assume that <math>|E|=\frac{n^2}{4}+1</math>, we will show that <math>G</math> must contain a triangle. Take a <math>uv\in E</math>, and let <math>H</math> be the subgraph of <math>G</math> induced by <math>V\setminus \{u,v\}</math>. Clearly, <math>H</math> has <math>n-2</math> vertices.
:'''Case.1:''' If <math>H</math> has <math>>\frac{(n-2)^2}{4}</math> edges, then by the induction hypothesis, <math>H</math> has a triangle.
:'''Case.2:''' If <math>H</math> has <math>\le\frac{(n-2)^2}{4}</math> edges, then at least <math>\left(\frac{n^2}{4}+1\right)-\frac{(n-2)^2}{4}-1=n-1</math> edges are between <math>H</math> and <math>\{u,v\}</math>. By pigeonhole principle, there must be a vertex in <math>H</math> that is adjacent to both <math>u</math> and <math>v</math>. Thus, <math>G</math> has a triangle.
}}

{{Prooftitle|Second proof. (Cauchy-Schwarz inequality)|(Mantel's original proof)
For any edge <math>uv\in E</math>, no vertex can be a neighbor of both <math>u</math> and <math>v</math>, or otherwise there will be a triangle. Thus, for any edge <math>uv\in E</math>, <math>d_u+d_v\le n</math>. It follows that
:<math>\sum_{uv\in E}(d_u+d_v)\le n|E|</math>.
Note that <math>d(v)</math> appears exactly <math>d_v</math> times in the sum, so that
:<math>\sum_{uv\in E}(d_u+d_v)=\sum_{v\in V}d_v^2</math>.
Applying Chauchy-Schwarz inequality,
:<math>
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>\sum_{v\in V}d_v=2|E|</math>. The theorem follows.
}}

{{Prooftitle|Third proof. (inequality of the arithmetic and geometric mean)|
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>.
Since <math>G</math> is triangle-free, for very vertex <math>v</math>, all its neighbors must form an independent set, thus <math>d(v)\le \alpha</math> for all <math>v\in V</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,
:<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>.
}}

=== Turán's theorem ===
{{Theorem|Theorem (Turán 1941)|
:Let <math>G(V,E)</math> be a graph with <math>|V|=n</math>. If <math>G</math> has no <math>r</math>-clique, <math>k\ge 2</math>, then
::<math>|E|\le\frac{r-2}{2(r-1)}n^2</math>.
}}

{{Prooftitle|First proof. (induction)|(Turán's original proof)
}}

{{Prooftitle|Second proof. (weight shifting)|(due to Motzkin and Straus)
}}

{{Prooftitle|Third proof. (the probabilistic method)|(due to Alon and Spencer)
}}

{{Prooftitle|Fourth proof.|
Let <math>G(V,E)</math> be a <math>r</math>-clique-free graph on <math>n</math> vertices with a maximum number of edges.
:'''Claim:''' <math>G</math> does not contain three vertices <math>u,v,w</math> such that <math>uv\in E</math> but <math>uw\not\in E, vw\not\in E</math>.
Suppose otherwise. There are two cases.
* '''Case.1:''' <math>d(w)<d(u)</math> or <math>d(w)<d(v)</math>. Without loss of generality, suppose that <math>d(w)<d(u)</math>. We duplicate <math>u</math> by creating a new vertex <math>u'</math> which has exactly the same neighbors as <math>u</math> (but <math>uu'</math> is not an edge). Such duplication will not increase the clique size. We then remove <math>w</math>. The resulting graph <math>G'</math> is still <math>r</math>-clique-free, and has <math>n</math> vertices. The number of edges in <math>G'</math> is
::<math>|E(G')|=|E(G)|+d(u)-d(w)>|E(G)|\,</math>,
:which contradicts the assumption that <math>|E(G)|</math> is maximal.
* '''Case.2:''' <math>d(w)\ge d(u)</math> and <math>d(w)\ge d(v)</math>. Duplicate <math>w</math> twice and delete <math>u</math> and <math>v</math>. The new graph <math>G'</math> has no <math>r</math>-clique, and the number of edges is
::<math>|E(G')|=|E(G)|+2d(w)-(d(u)+d(v)+1)>|E(G)|\,</math>.
:Contradiction again.

The claim implies that <math>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>G</math> must be a complete multipartite graph <math>K_{n_1,n_2,\ldots,n_{r-1}}</math> with <math>n_1+n_2+\cdots +n_{r-1}=n</math>. Optimize the edge number, we have the Turán graph.
}}

=== Erdős–Stone theorem ===

{{Theorem|Fundamental theorem of extremal graph theory (Erdős–Stone 1946)|
:For any integers <math>r\ge 2</math> and <math>s\ge 1</math>, and any <math>\epsilon>0</math>, there exists an <math>N_0</math> such that every graph with <math>n\ge N_0</math> vertices and at least <math>\left(\frac{r-2}{2(r-1)}+\epsilon\right)n^2</math> edges contains <math>K_{r,s}</math> as a subgraph, i.e.,
:::<math>\mathrm{ex}(n,K_{r,s})= \left(\frac{r-2}{2(r-1)}+o(1)\right)n^2</math>.
}}

{{Theorem|Corollary|
:For every nonempty graph <math>H</math>,
::<math>\lim_{n\rightarrow\infty}\frac{\mathrm{ex}(n,H)}{{n\choose 2}}=\frac{\chi(H)-2}{\chi(H)-1}</math>.
}}

== Cycle Structures ==
=== Girth ===

=== Hamiltonian cycle ===

Combinatorics (Fall 2010)/Extremal graphs

2010-10-14T06:59:33Z

172.21.1.240: /* Erdős–Stone theorem */

== 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>K_3</math>.

{{Theorem|Theorem (Mantel 1907)|
:Suppose <math>G(V,E)</math> is graph on <math>n</math> vertice without triangles. Then <math>|E|\le\frac{n^2}{4}</math>.
}}

{{Prooftitle|First proof. (pigeonhole principle)|
We prove an equivalent theorem: Any <math>G(V,E)</math> with <math>|V|=n</math> and <math>|E|>\frac{n^2}{4}</math> must have a triangle.

Use induction on <math>n</math>. The theorem holds trivially for <math>n\le 3</math>.

Induction hypothesis: assume the theorem hold for <math>|V|\le n-1</math>.

For <math>G</math> with <math>n</math> vertices, without loss of generality, assume that <math>|E|=\frac{n^2}{4}+1</math>, we will show that <math>G</math> must contain a triangle. Take a <math>uv\in E</math>, and let <math>H</math> be the subgraph of <math>G</math> induced by <math>V\setminus \{u,v\}</math>. Clearly, <math>H</math> has <math>n-2</math> vertices.
:'''Case.1:''' If <math>H</math> has <math>>\frac{(n-2)^2}{4}</math> edges, then by the induction hypothesis, <math>H</math> has a triangle.
:'''Case.2:''' If <math>H</math> has <math>\le\frac{(n-2)^2}{4}</math> edges, then at least <math>\left(\frac{n^2}{4}+1\right)-\frac{(n-2)^2}{4}-1=n-1</math> edges are between <math>H</math> and <math>\{u,v\}</math>. By pigeonhole principle, there must be a vertex in <math>H</math> that is adjacent to both <math>u</math> and <math>v</math>. Thus, <math>G</math> has a triangle.
}}

{{Prooftitle|Second proof. (Cauchy-Schwarz inequality)|(Mantel's original proof)
For any edge <math>uv\in E</math>, no vertex can be a neighbor of both <math>u</math> and <math>v</math>, or otherwise there will be a triangle. Thus, for any edge <math>uv\in E</math>, <math>d_u+d_v\le n</math>. It follows that
:<math>\sum_{uv\in E}(d_u+d_v)\le n|E|</math>.
Note that <math>d(v)</math> appears exactly <math>d_v</math> times in the sum, so that
:<math>\sum_{uv\in E}(d_u+d_v)=\sum_{v\in V}d_v^2</math>.
Applying Chauchy-Schwarz inequality,
:<math>
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>\sum_{v\in V}d_v=2|E|</math>. The theorem follows.
}}

{{Prooftitle|Third proof. (inequality of the arithmetic and geometric mean)|
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>.
Since <math>G</math> is triangle-free, for very vertex <math>v</math>, all its neighbors must form an independent set, thus <math>d(v)\le \alpha</math> for all <math>v\in V</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,
:<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>.
}}

=== Turán's theorem ===
{{Theorem|Theorem (Turán 1941)|
:Let <math>G(V,E)</math> be a graph with <math>|V|=n</math>. If <math>G</math> has no <math>r</math>-clique, <math>k\ge 2</math>, then
::<math>|E|\le\frac{r-2}{2(r-1)}n^2</math>.
}}

{{Prooftitle|First proof. (induction)|(Turán's original proof)
}}

{{Prooftitle|Second proof. (weight shifting)|(due to Motzkin and Straus)
}}

{{Prooftitle|Third proof. (the probabilistic method)|(due to Alon and Spencer)
}}

{{Prooftitle|Fourth proof.|
Let <math>G(V,E)</math> be a <math>r</math>-clique-free graph on <math>n</math> vertices with a maximum number of edges.
:'''Claim:''' <math>G</math> does not contain three vertices <math>u,v,w</math> such that <math>uv\in E</math> but <math>uw\not\in E, vw\not\in E</math>.
Suppose otherwise. There are two cases.
* '''Case.1:''' <math>d(w)<d(u)</math> or <math>d(w)<d(v)</math>. Without loss of generality, suppose that <math>d(w)<d(u)</math>. We duplicate <math>u</math> by creating a new vertex <math>u'</math> which has exactly the same neighbors as <math>u</math> (but <math>uu'</math> is not an edge). Such duplication will not increase the clique size. We then remove <math>w</math>. The resulting graph <math>G'</math> is still <math>r</math>-clique-free, and has <math>n</math> vertices. The number of edges in <math>G'</math> is
::<math>|E(G')|=|E(G)|+d(u)-d(w)>|E(G)|\,</math>,
:which contradicts the assumption that <math>|E(G)|</math> is maximal.
* '''Case.2:''' <math>d(w)\ge d(u)</math> and <math>d(w)\ge d(v)</math>. Duplicate <math>w</math> twice and delete <math>u</math> and <math>v</math>. The new graph <math>G'</math> has no <math>r</math>-clique, and the number of edges is
::<math>|E(G')|=|E(G)|+2d(w)-(d(u)+d(v)+1)>|E(G)|\,</math>.
:Contradiction again.

The claim implies that <math>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>G</math> must be a complete multipartite graph <math>K_{n_1,n_2,\ldots,n_{r-1}}</math> with <math>n_1+n_2+\cdots +n_{r-1}=n</math>. Optimize the edge number, we have the Turán graph.
}}

=== Erdős–Stone theorem ===

{{Theorem|Fundamental theorem of extremal graph theory (Erdős–Stone 1946)|
:For any integers <math>r\ge 2</math> and <math>s\ge 1</math>, and any <math>\epsilon>0</math>, there exists an <math>N_0</math> such that every graph with <math>n\ge N_0</math> vertices and at least <math>\left(\frac{r-2}{2(r-1)}+\epsilon\right)n^2</math> edges contains <math>K_{r,s}</math> as a subgraph, i.e.,
:::<math>\mathrm{ex}(n,K_{s,r})= \left(\frac{r-2}{2(r-1)}+o(1)\right)n^2</math>.
}}

{{Theorem|Corollary|
:For every nonempty graph <math>H</math>,
::<math>\lim_{n\rightarrow\infty}\frac{\mathrm{ex}(n,H)}{{n\choose 2}}=\frac{\chi(H)-2}{\chi(H)-1}</math>.
}}

== Cycle Structures ==
=== Girth ===

=== Hamiltonian cycle ===

Combinatorics (Fall 2010)/Extremal graphs

2010-10-14T06:58:37Z

172.21.1.240: /* Erdős–Stone theorem */

== 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>K_3</math>.

{{Theorem|Theorem (Mantel 1907)|
:Suppose <math>G(V,E)</math> is graph on <math>n</math> vertice without triangles. Then <math>|E|\le\frac{n^2}{4}</math>.
}}

{{Prooftitle|First proof. (pigeonhole principle)|
We prove an equivalent theorem: Any <math>G(V,E)</math> with <math>|V|=n</math> and <math>|E|>\frac{n^2}{4}</math> must have a triangle.

Use induction on <math>n</math>. The theorem holds trivially for <math>n\le 3</math>.

Induction hypothesis: assume the theorem hold for <math>|V|\le n-1</math>.

For <math>G</math> with <math>n</math> vertices, without loss of generality, assume that <math>|E|=\frac{n^2}{4}+1</math>, we will show that <math>G</math> must contain a triangle. Take a <math>uv\in E</math>, and let <math>H</math> be the subgraph of <math>G</math> induced by <math>V\setminus \{u,v\}</math>. Clearly, <math>H</math> has <math>n-2</math> vertices.
:'''Case.1:''' If <math>H</math> has <math>>\frac{(n-2)^2}{4}</math> edges, then by the induction hypothesis, <math>H</math> has a triangle.
:'''Case.2:''' If <math>H</math> has <math>\le\frac{(n-2)^2}{4}</math> edges, then at least <math>\left(\frac{n^2}{4}+1\right)-\frac{(n-2)^2}{4}-1=n-1</math> edges are between <math>H</math> and <math>\{u,v\}</math>. By pigeonhole principle, there must be a vertex in <math>H</math> that is adjacent to both <math>u</math> and <math>v</math>. Thus, <math>G</math> has a triangle.
}}

{{Prooftitle|Second proof. (Cauchy-Schwarz inequality)|(Mantel's original proof)
For any edge <math>uv\in E</math>, no vertex can be a neighbor of both <math>u</math> and <math>v</math>, or otherwise there will be a triangle. Thus, for any edge <math>uv\in E</math>, <math>d_u+d_v\le n</math>. It follows that
:<math>\sum_{uv\in E}(d_u+d_v)\le n|E|</math>.
Note that <math>d(v)</math> appears exactly <math>d_v</math> times in the sum, so that
:<math>\sum_{uv\in E}(d_u+d_v)=\sum_{v\in V}d_v^2</math>.
Applying Chauchy-Schwarz inequality,
:<math>
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>\sum_{v\in V}d_v=2|E|</math>. The theorem follows.
}}

{{Prooftitle|Third proof. (inequality of the arithmetic and geometric mean)|
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>.
Since <math>G</math> is triangle-free, for very vertex <math>v</math>, all its neighbors must form an independent set, thus <math>d(v)\le \alpha</math> for all <math>v\in V</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,
:<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>.
}}

=== Turán's theorem ===
{{Theorem|Theorem (Turán 1941)|
:Let <math>G(V,E)</math> be a graph with <math>|V|=n</math>. If <math>G</math> has no <math>r</math>-clique, <math>k\ge 2</math>, then
::<math>|E|\le\frac{r-2}{2(r-1)}n^2</math>.
}}

{{Prooftitle|First proof. (induction)|(Turán's original proof)
}}

{{Prooftitle|Second proof. (weight shifting)|(due to Motzkin and Straus)
}}

{{Prooftitle|Third proof. (the probabilistic method)|(due to Alon and Spencer)
}}

{{Prooftitle|Fourth proof.|
Let <math>G(V,E)</math> be a <math>r</math>-clique-free graph on <math>n</math> vertices with a maximum number of edges.
:'''Claim:''' <math>G</math> does not contain three vertices <math>u,v,w</math> such that <math>uv\in E</math> but <math>uw\not\in E, vw\not\in E</math>.
Suppose otherwise. There are two cases.
* '''Case.1:''' <math>d(w)<d(u)</math> or <math>d(w)<d(v)</math>. Without loss of generality, suppose that <math>d(w)<d(u)</math>. We duplicate <math>u</math> by creating a new vertex <math>u'</math> which has exactly the same neighbors as <math>u</math> (but <math>uu'</math> is not an edge). Such duplication will not increase the clique size. We then remove <math>w</math>. The resulting graph <math>G'</math> is still <math>r</math>-clique-free, and has <math>n</math> vertices. The number of edges in <math>G'</math> is
::<math>|E(G')|=|E(G)|+d(u)-d(w)>|E(G)|\,</math>,
:which contradicts the assumption that <math>|E(G)|</math> is maximal.
* '''Case.2:''' <math>d(w)\ge d(u)</math> and <math>d(w)\ge d(v)</math>. Duplicate <math>w</math> twice and delete <math>u</math> and <math>v</math>. The new graph <math>G'</math> has no <math>r</math>-clique, and the number of edges is
::<math>|E(G')|=|E(G)|+2d(w)-(d(u)+d(v)+1)>|E(G)|\,</math>.
:Contradiction again.

The claim implies that <math>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>G</math> must be a complete multipartite graph <math>K_{n_1,n_2,\ldots,n_{r-1}}</math> with <math>n_1+n_2+\cdots +n_{r-1}=n</math>. Optimize the edge number, we have the Turán graph.
}}

=== Erdős–Stone theorem ===

{{Theorem|Fundamental theorem of extremal graph theory (Erdős–Stone 1946)|
:For any integers <math>r\ge 2</math> and <math>s\ge 1</math>, and any <math>\epsilon>0</math>, there exists an <math>N_0</math> such that every graph with <math>n\ge N_0</math> vertices and at least <math>\left(\frac{r-2}{2(r-1)}+\epsilon\right)n^2</math> edges contains <math>K_{r,s}</math> as a subgraph, i.e.,
:::<math>\mathrm{ex}(n,K_{s,r})\le \left(\frac{r-2}{2(r-1)}+o(1)\right)n^2</math>.
}}

{{Theorem|Corollary|
:For every nonempty graph <math>H</math>,
::<math>\lim_{n\rightarrow\infty}\frac{\mathrm{ex}(n,H)}{{n\choose 2}}=\frac{\chi(H)-2}{\chi(H)-1}</math>.
}}

== Cycle Structures ==
=== Girth ===

=== Hamiltonian cycle ===

Combinatorics (Fall 2010)/Extremal graphs

2010-10-14T06:50:52Z

172.21.1.240: /* Erdős–Stone theorem */

== 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>K_3</math>.

{{Theorem|Theorem (Mantel 1907)|
:Suppose <math>G(V,E)</math> is graph on <math>n</math> vertice without triangles. Then <math>|E|\le\frac{n^2}{4}</math>.
}}

{{Prooftitle|First proof. (pigeonhole principle)|
We prove an equivalent theorem: Any <math>G(V,E)</math> with <math>|V|=n</math> and <math>|E|>\frac{n^2}{4}</math> must have a triangle.

Use induction on <math>n</math>. The theorem holds trivially for <math>n\le 3</math>.

Induction hypothesis: assume the theorem hold for <math>|V|\le n-1</math>.

For <math>G</math> with <math>n</math> vertices, without loss of generality, assume that <math>|E|=\frac{n^2}{4}+1</math>, we will show that <math>G</math> must contain a triangle. Take a <math>uv\in E</math>, and let <math>H</math> be the subgraph of <math>G</math> induced by <math>V\setminus \{u,v\}</math>. Clearly, <math>H</math> has <math>n-2</math> vertices.
:'''Case.1:''' If <math>H</math> has <math>>\frac{(n-2)^2}{4}</math> edges, then by the induction hypothesis, <math>H</math> has a triangle.
:'''Case.2:''' If <math>H</math> has <math>\le\frac{(n-2)^2}{4}</math> edges, then at least <math>\left(\frac{n^2}{4}+1\right)-\frac{(n-2)^2}{4}-1=n-1</math> edges are between <math>H</math> and <math>\{u,v\}</math>. By pigeonhole principle, there must be a vertex in <math>H</math> that is adjacent to both <math>u</math> and <math>v</math>. Thus, <math>G</math> has a triangle.
}}

{{Prooftitle|Second proof. (Cauchy-Schwarz inequality)|(Mantel's original proof)
For any edge <math>uv\in E</math>, no vertex can be a neighbor of both <math>u</math> and <math>v</math>, or otherwise there will be a triangle. Thus, for any edge <math>uv\in E</math>, <math>d_u+d_v\le n</math>. It follows that
:<math>\sum_{uv\in E}(d_u+d_v)\le n|E|</math>.
Note that <math>d(v)</math> appears exactly <math>d_v</math> times in the sum, so that
:<math>\sum_{uv\in E}(d_u+d_v)=\sum_{v\in V}d_v^2</math>.
Applying Chauchy-Schwarz inequality,
:<math>
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>\sum_{v\in V}d_v=2|E|</math>. The theorem follows.
}}

{{Prooftitle|Third proof. (inequality of the arithmetic and geometric mean)|
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>.
Since <math>G</math> is triangle-free, for very vertex <math>v</math>, all its neighbors must form an independent set, thus <math>d(v)\le \alpha</math> for all <math>v\in V</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,
:<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>.
}}

=== Turán's theorem ===
{{Theorem|Theorem (Turán 1941)|
:Let <math>G(V,E)</math> be a graph with <math>|V|=n</math>. If <math>G</math> has no <math>r</math>-clique, <math>k\ge 2</math>, then
::<math>|E|\le\frac{r-2}{2(r-1)}n^2</math>.
}}

{{Prooftitle|First proof. (induction)|(Turán's original proof)
}}

{{Prooftitle|Second proof. (weight shifting)|(due to Motzkin and Straus)
}}

{{Prooftitle|Third proof. (the probabilistic method)|(due to Alon and Spencer)
}}

{{Prooftitle|Fourth proof.|
Let <math>G(V,E)</math> be a <math>r</math>-clique-free graph on <math>n</math> vertices with a maximum number of edges.
:'''Claim:''' <math>G</math> does not contain three vertices <math>u,v,w</math> such that <math>uv\in E</math> but <math>uw\not\in E, vw\not\in E</math>.
Suppose otherwise. There are two cases.
* '''Case.1:''' <math>d(w)<d(u)</math> or <math>d(w)<d(v)</math>. Without loss of generality, suppose that <math>d(w)<d(u)</math>. We duplicate <math>u</math> by creating a new vertex <math>u'</math> which has exactly the same neighbors as <math>u</math> (but <math>uu'</math> is not an edge). Such duplication will not increase the clique size. We then remove <math>w</math>. The resulting graph <math>G'</math> is still <math>r</math>-clique-free, and has <math>n</math> vertices. The number of edges in <math>G'</math> is
::<math>|E(G')|=|E(G)|+d(u)-d(w)>|E(G)|\,</math>,
:which contradicts the assumption that <math>|E(G)|</math> is maximal.
* '''Case.2:''' <math>d(w)\ge d(u)</math> and <math>d(w)\ge d(v)</math>. Duplicate <math>w</math> twice and delete <math>u</math> and <math>v</math>. The new graph <math>G'</math> has no <math>r</math>-clique, and the number of edges is
::<math>|E(G')|=|E(G)|+2d(w)-(d(u)+d(v)+1)>|E(G)|\,</math>.
:Contradiction again.

The claim implies that <math>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>G</math> must be a complete multipartite graph <math>K_{n_1,n_2,\ldots,n_{r-1}}</math> with <math>n_1+n_2+\cdots +n_{r-1}=n</math>. Optimize the edge number, we have the Turán graph.
}}

=== Erdős–Stone theorem ===

{{Theorem|Fundamental theorem of extremal graph theory (Erdős–Stone 1946)|
:For any <math>r\ge 2</math> and <math>s\ge 1</math>, and every sufficiently large <math>n</math>, every graph with <math>n</math> vertices and at least <math>\left(\frac{r-2}{2(r-1)}+\epsilon\right)n^2</math> edges contains <math>K_{r,s}</math> as a subgraph.
}}

{{Theorem|Corollary|

}}

== Cycle Structures ==
=== Girth ===

=== Hamiltonian cycle ===