Have some proofs /sci/

I like you /sci/ so I'm gonna post some good proofs, you guys had best fucking appreciate them.

That's better, kk

Turan's theorem

Claim :

Let [eqn] G(V,E) [\eqn] be a graph with [eqn]|G|=|V|=n [\eqn] and [eqn] d_v = |\{w \in V\,:\,(v,w) \in E\}| [\eqn] is the degree of x.

Define [eqn] t = \frac{1}{n} \sum_{v \in V} d_v [\eqn] to be the average degree then we claim

[eqn] \alpha(G)  \geq \sum_{v \in V} \frac{1}{d_v + 1} \geq \frac{n}{t+1} [\eqn]

Proof :
We let < be a randomly chosen linear order on V and define [eqn] I_< = \{ v \in V \,:\, (v,w) \in E \Rightarrow v<w\} [\eqn], let [eqn]X_v[\eqn] be indicator random variable for [eqn] v \in I_<[\eqn] and [eqn] X = \sum_v X_v = |I_<|[\eqn]

Now as [eqn] v \in I_< [\eqn] only if it is the smallest element in it's neighbourhood we have

[eqn] \mathbb{E}(X_v) = \mathbb{P}(v \in I_<) = \frac{1}{d_v + 1} [\eqn]

And so by linearity of expectation

[eqn] \mathbb{E}(X) = \sum_v \frac{1}{d_v+1}[\eqn]

and so there must exist a specific ordering < with [eqn] |I_<| \geq sum_v \frac{1}{d_v+1}[\eqn]

But we notice that if an edge [eqn] (v,w) \in G|_{I_<} [\eqn] then [eqn] v<w[\eqn] and [eqn] w<v [\eqn], a contradiction, so [eqn] I_< [\eqn] is independent. Hence

[eqn]  \alpha(G)  \geq \sum_{v \in V} \frac{1}{d_v + 1} \geq \frac{n}{t+1} [\eqn]

Where the final inequality follows by the convexity of [eqn] \frac{1}{x} [\eqn]

QED

If this TeX fucked up I'll be pissy