MHB Proving Turan's Theorem (Dual Version) and its Implications for $ex(n, K_{p+1})$

  • Thread starter Thread starter joypav
  • Start date Start date
  • Tags Tags
    Dual Theorem
AI Thread Summary
The discussion focuses on proving the dual version of Turan's Theorem, which establishes that for a graph G with n vertices and edges equal to those of T'(n,q), the independence number α(G) is at least q, with equality implying G is isomorphic to T'(n,q). The thread explores how this dual version leads to the original Turan's Theorem, specifically showing that if the number of edges in G exceeds that of T(n,p), then the size of the largest clique ω(G) must be at least p+1. It emphasizes the relationship between the edge count of G and the independence number of its complement, leading to the conclusion that ω(G) equals α(¬G). The proof is presented as a logical progression from the dual theorem to the implications for Turan's Theorem.
joypav
Messages
149
Reaction score
0
I have already proved that for a graph $G$ with $n$ vertices and $|E(T'(n,q))|$ edges, $\alpha (G) \geq q$. Additionally, if $\alpha (G) = q$ then it must be that $G \cong T'(n,q)$.

Apparently this is the "dual version" of Turan's Theorem. How does this theorem imply Turan's?

That $ex(n, K_{p+1}) = |E(T(n,p))|$

Where:

- $T'(n,q)$ : $q$ disjoint cliques with size as equal as possible
- $\alpha (G)$ : independence number of $G$
- $ex(n, K_{p+1})$ : max number of edges in an n-vertex graph with no $K_{p+1}$ subgraph
 
Physics news on Phys.org
For completeness, here is the proof I wrote.
I'm not sure it is correct! May be some mistakes in the details.

Known Theorem:
Define $T'(n,q)$ to be q disjoint cliques with sizes of vertex sets as equal as possible. Let G be a graph with n vertices and $|E(T'(n,q))|$ edges. Then,
$$\alpha (G) \geq q$$
and if $\alpha (G) = q$ then $G \cong T'(n,q)$.To prove Turan's theorem, it suffices to show that if $|E(G)|>|E(T(n,p))|$ then $\omega (G) \geq p+1$, (where $\omega (G)$ is the size of the largest clique in G).\\
Assume $|E(G)|>|E(T(n,p))|$ then $|E(\overline{G})| \leq |E(T'(n,p))|$. By the in class proof, $\alpha (\overline{G}) \geq p+1$.
Notice that $\omega(G) = \alpha(\overline{G})$. Then we have, $\omega(G) = \alpha(\overline{G}) \geq p+1$, completing the proof.
 
Back
Top