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

From TCS Wiki
Jump to navigation Jump to search
imported>WikiSysop
imported>WikiSysop
Line 193: Line 193:
:<math>|T(n,r-1)|\le\mathrm{ex}(n,H)</math>.
:<math>|T(n,r-1)|\le\mathrm{ex}(n,H)</math>.
It is not hard to see that  
It is not hard to see that  
:<math>\frac{|T(n,r-1)|}{{n\choose 2}}\ge\frac{{r-1\choose 2}\left\lfloor\frac{n}{r-1}\right\rfloor^2}{{n\choose 2}}\ge\frac{{r-1\choose 2}\left(\frac{n}{r-1}-1\right)^2}{{n\choose 2}}=\frac{r-2}{r-1}-o(1)</math>.
:<math>|T(n,r-1)|\ge {r-1\choose 2}\left\lfloor\frac{n}{r-1}\right\rfloor^2\ge{r-1\choose 2}\left(\frac{n}{r-1}-1\right)^2=\left(\frac{r-2}{2(r-1)}-o(1)\right)n^2</math>.


On the other hand, any finite graph <math>H</math> with chromatic number <math>r</math> has that <math>H\subseteq K_s^r</math> for all sufficiently large <math>s</math>. We just connect all pairs of vertices from different color classes. Thus,  
On the other hand, any finite graph <math>H</math> with chromatic number <math>r</math> has that <math>H\subseteq K_s^r</math> for all sufficiently large <math>s</math>. We just connect all pairs of vertices from different color classes. Thus,  

Revision as of 08:12, 17 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)
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_{uv\in E}(d_u+d_v)=\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].

Partition [math]\displaystyle{ V }[/math] into [math]\displaystyle{ r-1 }[/math] disjoint classes [math]\displaystyle{ V=V_1\cup V_2\cup\cdots\cup V_{r-1} }[/math], [math]\displaystyle{ n_i=|V_i| }[/math], [math]\displaystyle{ n_1+n_2+\cdots+n_{r-1}=n }[/math]. For every two vertice [math]\displaystyle{ u,v }[/math], [math]\displaystyle{ uv\in E }[/math] if and only if [math]\displaystyle{ u\in V_i }[/math] and [math]\displaystyle{ v\in V_j }[/math] for distinct [math]\displaystyle{ V_i }[/math] and [math]\displaystyle{ V_j }[/math]. The resulting graph is a complete [math]\displaystyle{ (r-1) }[/math]-partite graph, denoted [math]\displaystyle{ K_{n_1,n_2,\ldots,n_{r-1}} }[/math]. It is obvious that any [math]\displaystyle{ (r-1) }[/math]-partite graph contains no [math]\displaystyle{ r }[/math]-clique since only those vertices from different classes can be adjacent.

A [math]\displaystyle{ K_{n_1,n_2,\ldots,n_{r-1}} }[/math] has [math]\displaystyle{ \sum_{i\lt j}n_i n_j\, }[/math] edges, which is maximized when the numbers [math]\displaystyle{ n_i }[/math] are divided as evenly as possible, that is, if [math]\displaystyle{ n_i\in\left\{\left\lfloor\frac{n}{r-1}\right\rfloor,\left\lceil\frac{n}{r-1}\right\rceil\right\} }[/math] for every [math]\displaystyle{ 1\le i\le r-1 }[/math].

Definition
We call a complete multipartite graph [math]\displaystyle{ K_{n_1,n_2,\ldots,n_{r-1}} }[/math] with [math]\displaystyle{ n_i\in\left\{\left\lfloor\frac{n}{r-1}\right\rfloor,\left\lceil\frac{n}{r-1}\right\rceil\right\} }[/math] for every [math]\displaystyle{ i }[/math] a Turán graph, denoted [math]\displaystyle{ T(n,r-1) }[/math].
Example
Turán graph [math]\displaystyle{ T(13,4) }[/math]
Turán graph [math]\displaystyle{ T(13,4) }[/math]
Turán graph [math]\displaystyle{ T(13,4) }[/math]
First proof. (induction)
(Turán's original proof)

Induction on [math]\displaystyle{ n }[/math]. It is easy to verify that the theorem holds for [math]\displaystyle{ n\lt r }[/math].

Let [math]\displaystyle{ G }[/math] be a graph on [math]\displaystyle{ n }[/math] vertices without [math]\displaystyle{ r }[/math]-cliques where [math]\displaystyle{ n\ge r }[/math]. Suppose that [math]\displaystyle{ G }[/math] has a maximum number of edges among such graphs. [math]\displaystyle{ G }[/math] certainly has [math]\displaystyle{ (r-1) }[/math]-cliques, since otherwise we could add edges to [math]\displaystyle{ G }[/math]. Let [math]\displaystyle{ A }[/math] be an [math]\displaystyle{ (r-1) }[/math]-clique and let [math]\displaystyle{ B=V\setminus A }[/math]. Clearly [math]\displaystyle{ |A|=r-1 }[/math] and [math]\displaystyle{ |B|=n-r+1 }[/math].

By the induction hypothesis, since [math]\displaystyle{ B }[/math] has no [math]\displaystyle{ r }[/math]-cliques, [math]\displaystyle{ |E(B)|\le\frac{r-2}{2(r-1)}(n-r+1)^2 }[/math]. And [math]\displaystyle{ E(A)={r-1\choose 2} }[/math]. Since [math]\displaystyle{ G }[/math] has no [math]\displaystyle{ r }[/math]-clique, every [math]\displaystyle{ v\in B }[/math] is adjacent to at most [math]\displaystyle{ r-2 }[/math] vertices in [math]\displaystyle{ A }[/math], since otherwise [math]\displaystyle{ A }[/math] and [math]\displaystyle{ v }[/math] would form an [math]\displaystyle{ r }[/math]-clique. We obtain that the number edges crossing between [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] is [math]\displaystyle{ |E(A,B)|\le (r-2)|B|=(r-2)(n-r+1) }[/math]. Combining everything together,

[math]\displaystyle{ |E|=|E(A)|+|E(B)|+|E(A,B)|\le {r-1\choose 2}+\frac{r-2}{2(r-1)}(n-r+1)^2+(r-2)(n-r+1)=\frac{r-2}{2(r-1)}n^2 }[/math].
[math]\displaystyle{ \square }[/math]
Second proof. (weight shifting)
(due to Motzkin and Straus)

Assign each vertex [math]\displaystyle{ v\in V }[/math] a nonnegative weight [math]\displaystyle{ w_v\ge 0 }[/math], and assume that [math]\displaystyle{ \sum_{v\in V}w_v=1 }[/math]. We try to maximize the quantity

[math]\displaystyle{ S=\sum_{uv\in E}w_uw_v }[/math].

Let [math]\displaystyle{ W_u=\sum_{v:v\sim u}w_v\, }[/math] be the sum of the weights of [math]\displaystyle{ u }[/math]'s neighbors. Note that [math]\displaystyle{ S }[/math] can also be computed as [math]\displaystyle{ S=\frac{1}{2}\sum_{u\in V}w_uW_u }[/math]. For any nonadjacent pair of vertices [math]\displaystyle{ u\not\sim v }[/math], supposed that [math]\displaystyle{ W_u\ge W-v }[/math], then for any [math]\displaystyle{ \epsilon\ge 0 }[/math],

[math]\displaystyle{ (w_u+\epsilon)W_u+(w_v-\epsilon)W_v\ge w_uW_u+w_vW_v }[/math].

This means that we do not decrease [math]\displaystyle{ S }[/math] by shifting all of the weight of the vertex [math]\displaystyle{ v }[/math] to the vertex [math]\displaystyle{ u }[/math]. It follows that [math]\displaystyle{ S }[/math] is maximized when all of the weight is concentrated on a complete subgraph, i.e., a clique.

Now if [math]\displaystyle{ w_u\gt w_v\gt 0 }[/math], then choose [math]\displaystyle{ \epsilon }[/math] with [math]\displaystyle{ 0\lt \epsilon\lt w_u-w_v }[/math] and change [math]\displaystyle{ w_u'=w_u-\epsilon }[/math] and [math]\displaystyle{ w_v'=w_v+\epsilon }[/math]. This changes [math]\displaystyle{ S }[/math] to [math]\displaystyle{ S'=S+\epsilon(w_u-w_v)-\epsilon^2\gt S }[/math]. Thus, the maximal value of [math]\displaystyle{ S }[/math] is attained when all nonzero weights are equal and concentrated on a clique.

[math]\displaystyle{ G }[/math] has at most an [math]\displaystyle{ (r-1) }[/math]-clique, thus [math]\displaystyle{ S\le{r-1\choose 2}\frac{1}{(r-1)^2}=\frac{r-2}{2(r-1)} }[/math].

As we argued above, this inequality hold for any nonnegative weight assignments with [math]\displaystyle{ \sum_{v\in V}w_v=1 }[/math]. In particular, for the case that all [math]\displaystyle{ w_v=\frac{1}{n} }[/math],

[math]\displaystyle{ S=\sum_{uv\in E}w_uw_v=\frac{|E|}{n^2} }[/math].

Thus,

[math]\displaystyle{ \frac{|E|}{n^2}\le \frac{r-2}{2(r-1)} }[/math],

which implies the theorem.

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

Write [math]\displaystyle{ \omega(G) }[/math] for the number of vertices in a largest clique, called the clique number of [math]\displaystyle{ G }[/math].

Claim: [math]\displaystyle{ \omega(G)\ge\sum_{v\in V}\frac{1}{n-d_v} }[/math].

We prove this by the probabilistic method. Fix a random ordering of vertices in [math]\displaystyle{ V }[/math], say [math]\displaystyle{ v_1,v_2,\ldots,v_n }[/math]. We construct a clique as follows:

  • for [math]\displaystyle{ i=1,2,\ldots, n }[/math], add [math]\displaystyle{ v_i }[/math] to [math]\displaystyle{ S }[/math] iff all vertices in current [math]\displaystyle{ S }[/math] are adjacent to [math]\displaystyle{ v_i }[/math].

It is obvious that an [math]\displaystyle{ S }[/math] constructed in this way is a clique. We now show that [math]\displaystyle{ \mathbf{E}[|S|]=\sum_{v\in V}\frac{1}{n-d_v} }[/math].

Let [math]\displaystyle{ X_v }[/math] be the random variable that indicates whether [math]\displaystyle{ v\in S }[/math], i.e.,

[math]\displaystyle{ X_v=\begin{cases} 1 & v\in S,\\ 0 & \mbox{otherwise.} \end{cases} }[/math]

Note that a vertex [math]\displaystyle{ v\in S }[/math] if and only if [math]\displaystyle{ v }[/math] is ranked before all its [math]\displaystyle{ n-d_v-1 }[/math] non-neighbors in the random ordering. The probability that this event occurs is [math]\displaystyle{ \frac{1}{n-d_v} }[/math]. Thus,

[math]\displaystyle{ \mathbf{E}[X_v]=\Pr[v\in S]=\frac{1}{n-d_v}. }[/math]

Observe that [math]\displaystyle{ |S|=\sum_{v\in V}X_v }[/math]. Due to linearity of expectation,

[math]\displaystyle{ \mathbf{E}[|S|]=\sum_{v\in V}\mathbf{E}[X_v]=\sum_{v\in V}\frac{1}{n-d_v} }[/math].

There must exists a clique of at least such size, so that [math]\displaystyle{ \omega(G)\ge\sum_{v\in V}\frac{1}{n-d_v} }[/math]. The claim is proved.

Apply the Cauchy-Schwarz inequality

[math]\displaystyle{ \left(\sum_{v\in V}a_vb_v\right)^2\le\left(\sum_{v\in V}^na_v^2\right)\left(\sum_{v\in V}^nb_v^2\right) }[/math].

Set [math]\displaystyle{ a_v=\sqrt{n-d_v} }[/math] and [math]\displaystyle{ b_v=\frac{1}{\sqrt{n-d_v}} }[/math], then [math]\displaystyle{ a_vb_v=1 }[/math] and so

[math]\displaystyle{ n^2\le\sum_{v\in V}(n-d_v)\sum_{v\in V}\frac{1}{n-d_v}\le\omega(G)\sum_{v\in V}(n-d_v). }[/math]

By the assumption of Turán's theorem, [math]\displaystyle{ \omega(G)\le r-1 }[/math]. Recall the handshaking lemma [math]\displaystyle{ 2|E|=\sum_{v\in V}d_v }[/math]. The above inequality gives us

[math]\displaystyle{ n^2\le (r-1)(n^2-2|E|) }[/math],

which implies the theorem.

[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]

Cycle Structures

Girth

Recall that the girth of a graph [math]\displaystyle{ G }[/math] is the length of the shortest cycle in [math]\displaystyle{ G }[/math].

Theorem
Let [math]\displaystyle{ G(V,E) }[/math] be a graph on [math]\displaystyle{ n }[/math] vertices. If girth [math]\displaystyle{ g(G)\ge 5 }[/math] then [math]\displaystyle{ |E|\le\frac{1}{2}n\sqrt{n-1} }[/math].
Proof.

Suppose [math]\displaystyle{ g(G)\ge 5 }[/math]. Let [math]\displaystyle{ v_1,v_2,\ldots,v_d }[/math] be the neighbors of a vertex [math]\displaystyle{ u }[/math], where [math]\displaystyle{ d=d(u) }[/math]. Let [math]\displaystyle{ S_i=\{v\in V\mid v\sim v_i\wedge v\neq u\} }[/math] be the set of neighbors of [math]\displaystyle{ v_i }[/math] other than [math]\displaystyle{ u }[/math].

  • For any [math]\displaystyle{ v_i,v_j }[/math], [math]\displaystyle{ v_iv_j\not\in E }[/math] since [math]\displaystyle{ G }[/math] has no triangle. Thus, [math]\displaystyle{ S_i\cap\{u,v_1,v_2,\ldots,v_d\}=\emptyset }[/math] for every [math]\displaystyle{ i }[/math].
  • No vertex other than [math]\displaystyle{ u }[/math] can be adjacent to more than one vertices in [math]\displaystyle{ v_1,v_2,\ldots,v_d }[/math] since there is no [math]\displaystyle{ C_4 }[/math] in [math]\displaystyle{ G }[/math]. Thus, [math]\displaystyle{ S_i\cap S_j=\emptyset }[/math] for any distinct [math]\displaystyle{ i }[/math] and [math]\displaystyle{ j }[/math].

Therefore, [math]\displaystyle{ \{u,v_1,v_2,\ldots,v_d\}\cap S_1\cup S_2\cup\cdots\cup S_d\subseteq V }[/math] implies that

[math]\displaystyle{ (d+1)+|S_1|+|S_2|+\cdots+|S_d|=(d+1)+(d(v_1)-1)+(d(v_2)-1)+\cdots+(d(v_d)-1)\le n }[/math],

so that [math]\displaystyle{ \sum_{v:v\sim u}d(v)\le n-1 }[/math].

By Cauchy-Schwarz inequality,

[math]\displaystyle{ n(n-1)\ge \sum_{u\in V}\sum_{v:v\sim u}d(v)=\sum_{v\in V}d(v)^2\ge\frac{\left(\sum_{v\in V}d(v)\right)}{n}=\frac{4|E|^2}{n} }[/math],

which implies that [math]\displaystyle{ |E|\le\frac{1}{2}n\sqrt{n-1} }[/math].

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

Hamiltonian cycle

Dirac's Theorem
A graph [math]\displaystyle{ G(V,E) }[/math] on [math]\displaystyle{ n }[/math] vertices has a Hamiltonian cycle if [math]\displaystyle{ d_v\ge\frac{n}{2} }[/math] for all [math]\displaystyle{ v\in V }[/math].
Proof.

Suppose to the contrary, the theorem is not true and there exists a non-Hamiltonian graph with [math]\displaystyle{ d_v\ge\frac{n}{2} }[/math] for all [math]\displaystyle{ v\in V }[/math]. Let [math]\displaystyle{ G }[/math] be such a graph with a maximum number of edges. Then adding any edge to [math]\displaystyle{ G }[/math] creates a Hamiltonian cycle. Thus, [math]\displaystyle{ G }[/math] must have a Hamiltonian path, say [math]\displaystyle{ v_1v_2\cdots v_n }[/math].

Consider the sets,

  • [math]\displaystyle{ S=\{i\mid v_iv_n\in E\} }[/math];
  • [math]\displaystyle{ T=\{i\mid v_{i+1}v_1\in E\} }[/math].

Therefore, [math]\displaystyle{ S\subseteq\{v_1,v_2,\ldots,v_{n-1}\} }[/math] contains the neighbors of [math]\displaystyle{ v_n }[/math]; and [math]\displaystyle{ T\subseteq\{v_1,v_2,\ldots,v_{n-1}\} }[/math] contains the predecessors (along the Hamiltonian path) of the neighbors of [math]\displaystyle{ v_1 }[/math]. It holds that [math]\displaystyle{ S,T\subseteq\{v_1,v_2,\ldots,v_{n-1}\} }[/math].

Since [math]\displaystyle{ d_v\ge\frac{n}{2} }[/math] for all [math]\displaystyle{ v\in V }[/math], [math]\displaystyle{ |S|,|T|\ge\frac{n}{2} }[/math]. By the pigeonhole principle, there exists some [math]\displaystyle{ v_i\in S\cap T }[/math]. We can construct the following Hamiltonian cycle:

[math]\displaystyle{ v_1v_{i+1}v_{i+2}\cdots v_nv_{i}v_{i-1}\cdots v_1\cdots }[/math],

which contradict to the assumption that [math]\displaystyle{ G }[/math] is non-Hamiltonian.

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

Erdős–Stone theorem

Let [math]\displaystyle{ K_s^r=K_{\underbrace{s,s,\cdots,s}_{r}} }[/math] be the complete [math]\displaystyle{ r }[/math]-partite graph with [math]\displaystyle{ s }[/math] vertices in each class, i.e., the Turán graph [math]\displaystyle{ T(rs,r) }[/math].

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], if [math]\displaystyle{ n }[/math] is sufficiently large then every graph on [math]\displaystyle{ n }[/math] vertices and with 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)= \left(\frac{r-2}{2(r-1)}+o(1)\right)n^2 }[/math].

Recall that [math]\displaystyle{ \chi(G) }[/math] is the chromatic number of [math]\displaystyle{ G }[/math], the smallest number of colors that one can use to color the vertices so that no adjacent vertices have the same color.

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].
Proof of corollary

Let [math]\displaystyle{ r=\chi(H) }[/math].

Note that [math]\displaystyle{ T(n,r-1) }[/math] can be colored with [math]\displaystyle{ r-1 }[/math] colors, one color for each part. Thus, [math]\displaystyle{ H\not\subseteq T(n,r-1) }[/math], since otherwise [math]\displaystyle{ H }[/math] can also be colored with [math]\displaystyle{ r-1 }[/math] colors, contradicting that [math]\displaystyle{ \chi(H)=1 }[/math]. By definition, [math]\displaystyle{ \mathrm{ex}(n,H) }[/math] is the maximum number of edges that an [math]\displaystyle{ n }[/math]-vertex graph [math]\displaystyle{ G\not\supseteq H }[/math] can have. Thus,

[math]\displaystyle{ |T(n,r-1)|\le\mathrm{ex}(n,H) }[/math].

It is not hard to see that

[math]\displaystyle{ |T(n,r-1)|\ge {r-1\choose 2}\left\lfloor\frac{n}{r-1}\right\rfloor^2\ge{r-1\choose 2}\left(\frac{n}{r-1}-1\right)^2=\left(\frac{r-2}{2(r-1)}-o(1)\right)n^2 }[/math].

On the other hand, any finite graph [math]\displaystyle{ H }[/math] with chromatic number [math]\displaystyle{ r }[/math] has that [math]\displaystyle{ H\subseteq K_s^r }[/math] for all sufficiently large [math]\displaystyle{ s }[/math]. We just connect all pairs of vertices from different color classes. Thus,

[math]\displaystyle{ \mathrm{ex}(n,H)\le\mathrm{ex}(n,K_s^r) }[/math].

Due to Erdős–Stone theorem,

[math]\displaystyle{ \mathrm{ex}(n,K_s^r)=\left(\frac{r-2}{2(r-1)}+o(1)\right)n^2 }[/math].

Altogether, we have

[math]\displaystyle{ \frac{r-2}{r-1}-o(1)\le\frac{|T(n,r-1)|}{{n\choose 2}}\le \frac{\mathrm{ex}(n,H)}{{n\choose 2}} \le \frac{\mathrm{ex}(n,K_s^r)}{{n\choose 2}}=\frac{r-2}{r-1}+o(1) }[/math]

The theorem follows.

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

References

(声明: 资料受版权保护, 仅用于教学.)
(Disclaimer: The following copyrighted materials are meant for educational uses only.)
  • van Lin and Wilson, A course in combinatorics, Chapter 4.
  • Aigner and Ziegler. Proofs from THE BOOK, 4th Edition. Springer-Verlag. Chapter 36.
  • Diestel. Graph Theory, 3rd Edition. Springer-Verlag 2000. Chapter 7.