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$

Combinatorics Seminar: Eigenvalues and quasirandom hypergraph

Oggi pomeriggio ho partecipato al seminario di Combinatoria su Eigenvalues and quasirandom hypergraph, tenuto da Dhruv Mubayi (University of Illinois, Chicago). Very enlightening!

Yoneda Lemma

Sia $\mathcal C$ una categoria. Si consideri la categoria $\mathrm{Funct}(\mathcal C^\mathrm{op},\mathrm{Sets})$, i cui oggetti sono funtori controvarianti $\mathcal C\rightarrow \mathrm{Sets}$, e i cui morfismi sono trasformazioni naturali. Per ogni $Z \in \mathcal C$ si definisce il funtore controvariante \[ \begin{array}{l@{}l} F_Z: &\ \mathcal C \rightarrow \mathrm{Sets}\\ &\ X \mapsto \mathrm{Map}_{\mathcal C}(X,Z)=F_Z(X)\,. \end{array} \] Il morfismo $f:Z_1\rightarrow Z_2$ dà origine alla trasformazione naturale \[ f_\ast:F_{Z_1}=\mathrm{Map}_{\mathcal C}(\cdot,Z_1)\rightarrow\mathrm{Map}_{\mathcal C}(\cdot,Z_2)=F_{Z_2}. \] Allora può essere costruito il funtore \[ \mathcal Y: \mathcal C \rightarrow \mathrm{Funct}(\mathcal C,\mathrm{Sets}) \] in modo che $\mathcal Y(Z)=F_Z$. Questo funtore è detto Yoneda embedding.

Lemma (Yoneda) L'applicazione \[ \mathrm{Map}_{\mathcal C}(Z_1,Z_2)\rightarrow \mathrm{Nat}(F_{Z_1},F_{Z_2}) \] è una bigezione. Qui, $\mathrm{Nat}(F_{Z_1},F_{Z_2})$ è la collezione delle trasformazioni naturali.

Dimostrazione. Per ottenere la tesi, è sufficiente provare che l'applicazione \[ \mathrm{Map}_{\mathcal C}(Z_1,Z_2)\rightarrow \mathrm{Nat}(F_{Z_1},F_{Z_2}) \] ammette inversa. Innanzitutto, essa opera in modo che ad ogni $\varphi \in \mathrm{Map}_{\mathcal C}(Z_1,Z_2)$ associ il suo pushforward $\varphi_\ast$, defnito come: per ogni $X \in \mathcal C$, e $f: X\rightarrow Z_1$, $\varphi_\ast(X)(f)=\varphi f$. Si consideri dunque $\Phi \in \mathrm{Nat}(F_{Z_1},F_{Z_2})$ trasformazione naturale. Ricordiamo che, per ogni $Z \in \mathcal C$, il funtore $F_Z$ opera come il pullback: per ogni $f \in \mathrm{Map}_{\mathcal C}(X,Y)$, e $\alpha \in \mathrm{Map}_{\mathcal C}(Y,Z)=F_Z(Y)$, si ha $F_Z(f)(\alpha)=\alpha f= f^\ast(\alpha)$. Allora, dalla definizione, si ha che: \[ \Phi(X):\mathrm{Map}_{\mathcal C}(X,Z_1)\rightarrow\mathrm{Map}_{\mathcal C}(X,Z_2) \] e inoltre, per ogni $f:Y \rightarrow X$ in $\mathcal C$, il seguente diagramma è commutativo:\[
\begin{array}{c@{}c@{}ccc@{}c@{}c} F_{Z_1}(X) &=&\mathrm{Map}_{\mathcal C}(X,Z_1)&\stackrel{\Phi(X)}{\rightarrow}&\mathrm{Map}_{\mathcal C}(X,Z_2) &=&F_{Z_2}(X)\\
 &&\downarrow\scriptstyle{f^\ast=F_{Z_1}(f)}&&\downarrow\scriptstyle{F_{Z_2}(f)=f^\ast}&&\\
F_{Z_1}(Y) &=&\mathrm{Map}_{\mathcal C}(Y,Z_1)&\stackrel{\Phi(Y)}{\rightarrow}&\mathrm{Map}_{\mathcal C}(Y,Z_2) &=&F_{Z_2}(Y)
\end{array}
\]ovvero $\Phi(Y)(F_{Z_1}(f))=F_{Z_2}(f)(\Phi(X))$. Per costruire una mappa $\mathrm{Map}_{\mathcal C}(Z_1,Z_2)\rightarrow \mathrm{Nat}(F_{Z_1},F_{Z_2})$ inversa di quella assegnata, possiamo pensare di associare alla trasformazione naturale $\Phi$ la mappa $\Phi(Z_1)(\mathrm{id}_{Z_1}) \in \mathrm{Map}_{\mathcal C}(Z_1,Z_2)$. Riassumendo, il claim è che \[ B: \Phi \in \mathrm{Nat}(F_{Z_1},F_{Z_2}) \mapsto \Phi(Z_1)(\mathrm{id}_{Z_1}) \in \mathrm{Map}_{\mathcal C}(Z_1,Z_2) \] è l'inversa di \[ A: \varphi \in \mathrm{Map}_{\mathcal C}(Z_1,Z_2) \mapsto \varphi_\ast \in \mathrm{Nat}(F_{Z_1},F_{Z_2}). \] Infatti \[ \varphi \stackrel{A}{\mapsto}\varphi_\ast \stackrel{B}{\mapsto} \varphi_\ast(Z_1)(\mathrm{id}_{Z_1}) = \varphi\mathrm{id}_{Z_1}=\varphi \] E inoltre: \[ \Phi \stackrel{B}{\mapsto} \Phi(Z_1)(\mathrm{id}_{Z_1}) \stackrel{A}{\mapsto} (\Phi(Z_1)(\mathrm{id}_{Z_1}))_\ast \] e puntualmente, per ogni $X \in \mathcal C$ e $f:X \rightarrow Z_1$ in $\mathcal C$: \[ (\Phi(Z_1)(\mathrm{id}_{Z_1}))_\ast(X)(f)=\Phi(Z_1)(\mathrm{id}_{Z_1})(f)=f^\ast\Phi(Z_1)(\mathrm{id}_{Z_1})= \Phi(X)f^\ast(\mathrm{id}_{Z_1})= \Phi(X)(f) \] da cui segue la tesi. $\square$

Prime lezioni

Seminar in Theoretical Computer Science
Prof. L. Orecchia

Introduction to Algebraic Geometry
Prof. M. Artin

Ieri abbiamo seguito le prime lezioni (tra cui quelle nelle foto!). Qui l'approccio alla matematica è del tutto nuovo per noi: per esempio spesso si mira a dare l'idea del risultato, più che l'intera dimostrazione, dando maggior peso alle applicazioni
Siamo anche al lavoro su alcuni problem sets. Più tardi spero di riuscire a postare la dimostrazione di un Lemma di Topologia Algebrica. Stay tuned!