 |  |
 |  |
Logo_messaggericonoscenza
Diario dell'esperienza all'estero presso il MIT
giovedì 13 marzo 2014
The evolution of MATLAB & How Math impacts your life
mercoledì 12 marzo 2014
Simons lectures in Mathematics 3/3 (aggiornato 14/03)
A breve questo pomeriggio, si terrà il primo di tre seminari di Matemarica Applicata (ecco la locandina), tenuto quest'anno da D. Spielman (Yale University).
12/03: Sparsification of graphs and matrices.
13/03: The solution of the Kadison-Singer problem.
14/03: Ramanujan graphs of every degree.
 |
 |
 |
 |
 |
 |
lunedì 10 marzo 2014
4-colorabilità di un ipergrafo - Il ritorno
Esercizio. Sia $n \geq 2$ e sia $H = (V, E)$ un ipergrafo $n$-uniforme con $|E| = 4^{n-1}$ lati. Si mostri che esiste una colorazione di $V$ con $4$ colori tale che nessun lato è monocromatico.
Svolgimento. Si consideri la colorazione dei vertici di $H$ tale che ogni vertice di $H$ è colorato indipendentemente e uniformly at random con i colori $1,2,3,4$. Per ogni lato $e \in E$, definiamo $X_e$ la Indicator Random Variable (IRV) per l'evento che tutti i vertici di $e$ hanno lo stesso colore. Poiché ogni lato ha $n$ vertici,
\[ \mathbb E[X_e]=\mathrm{Pr}[\text{$e$ è monocromatico}]=\sum_{k=1}^4\mathrm{Pr}[\text{$e$ è monocromatico di colore }k]=\sum_{k=1}^4\frac{1}{4^n} = \frac{1}{4^{n-1}}. \] Si definisca $\displaystyle{X=\sum_{e \in E}X_e}$ come il numero di lati monocromatici di $H$, allora $\mathbb E[X]=\displaystyle{\sum_{e \in E}\mathbb E[X_e]=\sum_{e \in E}\frac{1}{4^{n-1}}=\frac{|E|}{4^{n-1}}=1}$. Si consideri la colorazione dei vertici di $H$ con il minor numero di lato monocromatici; usando $\mathbb E[X]=1$, possiamo affermare che tale colorazione ha al più un solo lato monocromatico. Se per assurdo essa avesse un lato monocromatico, allora tutte le colorazioni dovrebbero avere un lato monocromatico, e questo non è vero in quanto colorando tutti i vertici dello stesso colore, otteniamo $|E|=4^{n-1}>1$ lati monocromatici. Allora la colorazione con il minor numero di lati monocromatici non ne contiene nessuno. $\square$
Svolgimento. Si consideri la colorazione dei vertici di $H$ tale che ogni vertice di $H$ è colorato indipendentemente e uniformly at random con i colori $1,2,3,4$. Per ogni lato $e \in E$, definiamo $X_e$ la Indicator Random Variable (IRV) per l'evento che tutti i vertici di $e$ hanno lo stesso colore. Poiché ogni lato ha $n$ vertici,
\[ \mathbb E[X_e]=\mathrm{Pr}[\text{$e$ è monocromatico}]=\sum_{k=1}^4\mathrm{Pr}[\text{$e$ è monocromatico di colore }k]=\sum_{k=1}^4\frac{1}{4^n} = \frac{1}{4^{n-1}}. \] Si definisca $\displaystyle{X=\sum_{e \in E}X_e}$ come il numero di lati monocromatici di $H$, allora $\mathbb E[X]=\displaystyle{\sum_{e \in E}\mathbb E[X_e]=\sum_{e \in E}\frac{1}{4^{n-1}}=\frac{|E|}{4^{n-1}}=1}$. Si consideri la colorazione dei vertici di $H$ con il minor numero di lato monocromatici; usando $\mathbb E[X]=1$, possiamo affermare che tale colorazione ha al più un solo lato monocromatico. Se per assurdo essa avesse un lato monocromatico, allora tutte le colorazioni dovrebbero avere un lato monocromatico, e questo non è vero in quanto colorando tutti i vertici dello stesso colore, otteniamo $|E|=4^{n-1}>1$ lati monocromatici. Allora la colorazione con il minor numero di lati monocromatici non ne contiene nessuno. $\square$