Turan's theorem
Claim :
Let
G(V,E)
be a graph with
|G|=|V|=n
and
d_v = |\{w \in V\,:\,(v,w) \in E\}|
is the degree of x.
Define
t = \frac{1}{n} \sum_{v \in V} d_v
to be the average degree then we claim
\alpha(G) \geq \sum_{v \in V} \frac{1}{d_v + 1} \geq \frac{n}{t+1}
Proof :
We let < be a randomly chosen linear order on V and define
I_< = \{ v \in V \,:\, (v,w) \in E \Rightarrow v<w\}
, let
X_v
be indicator random variable for
v \in I_<
and
X = \sum_v X_v = |I_<|
Now as
v \in I_<
only if it is the smallest element in it's neighbourhood we have
\mathbb{E}(X_v) = \mathbb{P}(v \in I_<) = \frac{1}{d_v + 1}
And so by linearity of expectation
\mathbb{E}(X) = \sum_v \frac{1}{d_v+1}
and so there must exist a specific ordering < with
|I_<| \geq sum_v \frac{1}{d_v+1}
But we notice that if an edge
(v,w) \in G|_{I_<}
then
[eqn] v<w[\eqn] and
[eqn] w<v [\eqn], a contradiction, so
[eqn] I_< [\eqn] is independent. Hence
\alpha(G) \geq \sum_{v \in V} \frac{1}{d_v + 1} \geq \frac{n}{t+1}
Where the final inequality follows by the convexity of
\frac{1}{x}
Fix'd