Combinatorics - Problem Set 3!

Perdonate la prolungata assenza di post. Sto preparando una "sorpresa" per l'ultima settimana.

Di seguito, un esercizio del terzo - e ultimo :'( - problem set di combinatoria

Esercizio. Si provi che ogni ipergrafo $3$-uniforme con $n$ vertici e $m \geq \frac{n}{3}$ lati contiene un independent set (cioé un insieme di vertici non connessi da lati) di cardinalità almeno \[ \frac{2n^{2/3}}{3\sqrt{3}\sqrt{m}} \]

Svolgimento. Sia $S$ un insieme generico di vertici dell'ipergrafo $3$-uniforme $G$, with $\mathrm{Pr}(v \in S) = p$. Sia $X = |S|$ e $Y$ il numero dei lati in $G\big|_S$. Si consideri $e = \{i, j, k\}$ un lato di $G$ e $Y_e$ la Indicator Random Variable per l'evento che $e \in G\big|_S$. Allora $\mathbb E[Y_e] = p^3$, e $\mathbb E[Y] = \sum_{e \in G}\mathbb E[Y_e]=mp^3$. Inoltre $\mathbb E[X] = np$. Allora $\mathbb E[X-Y] = np - mp^3$, pertanto, se $p$ è tra $0$ e $1$, allora esiste un particolare $S$ per cui $X - Y \geq np - mp^3$. Dunque per ogni lato in $G\big|_S$, scegliamo un vertice e lo rimuoviamo da $S$, ottenendo un insieme indipendente, in quanto un vertice è stato rimosso da ogni lato. In più, abbiamo rimosso $Y$ vertici da $S$, e quindi il nuovo insieme ha $X-Y$ vertici, con $X-Y \geq np - mp^3$. Allora esiste un independent set di cardinalità almeno $np - mp^3$, e possiamo scegliere $p$ per massimizzare $np - mp^3$. Derivando rispetto a $p$ e uguagliando a $0$, otteniamo $n - 3mp^2 = 0$, da cui $p = \frac{\sqrt{n}}{\sqrt{3m}} \leq 1$ (per l'ultima disuguaglianza abbiamo usato l'ipotesi $m\geq \frac{n}{3}$). Concludiamo che esiste un independent set di cardinalità almeno pari a $n\frac{\sqrt{n}}{\sqrt{3m}} - \frac{m n^{3/2}}{(3m)^{3/2}} = \frac{2n^{2/3}}{3\sqrt{3}\sqrt{m}}$. $\square$