4-colorabilità di un ipergrafo

Di seguito, un esercizio del primo problem set:

Definizione. Un ipergrafo è una coppia ordinata $H =(V,E)$, in cui $V$ è un insieme finito i cui elementi sono detti vertici ed $E$ è una famiglia di sottoinsiemi di $V$, detti lati. Un ipergrafo si dice $n$-uniforme se ogni suo lato contiene esattamente $n$ vertici.

(Esercizio 2, Ch.1 Alon, Spencer, The Probabilistic Method, (2008))

Esercizio. Sia $n > 4$ e sia $H$ un ipergrafo $n$-uniforme, con al più $\frac{4^{n-1}}{3^n}$ lati. Si provi che esiste una colorazione dei vertici di $H$ con quattro colori in modo che in ogni lato siano presenti tutti i quattro colori.

Svolgimento. Sia $H = (V,E)$. Si colori ogni vertice in $H$ uniformly at random con quattro colori. Sia $A_e$ l'evento che i vertici nel lato $e$ sono colorati con al più $3$ colori. Si noti che esistono $4$ modi di scegliere $3$ colori per colorare i vertici di $e$ e, per ogni scelta, abbiamo $3^n$ colorazioni. Pertanto \[ \mathrm{Pr}\left[\bigcup_{e \in E}A_e\right]< \sum_{e \in E} \mathrm{Pr}[A_e] \leq \frac{4^{n-1}}{3^n}\frac{3^n}{4^{n-1}}=1\,, \] (attenzione: $A_{e_1}$, $A_{e_2}$ non sono disgiunti se $e_1 \cap e_2 \neq \varnothing$). Segue la tesi. $\square$