Acknowledgements!

The time you get used to it, you have to leave...

Venerdì sera, Cambridge. Inizia l'ultimo weekend, e si comincia a sentire che le ultime ore qui scivolano via. Credo sia arrivato il momento dei ringraziamenti!

Vorrei innanzitutto ringraziare i responsabili dell'organizzazione: il direttore del Dipartimento di Matematica dell'Università degli Studi di Bari, il Prof. Francesco Altomare, il Responsabile scientifico del Progetto Messaggeri della Conoscenza, il Prof. Enrico Jannelli, e i Responsabili amministrativi, la Dott.ssa Roberta Peschiulli e il Dott. Enzo Torino.
Ringrazio sinceramente anche il Dott. Lorenzo Orecchia e il Dott. Bruno Benedetti per aver proposto il progetto, e per aver tenuto l'imperdibile corso estivo Geometria, Ottimizzazione e Teoria dei Grafi.
Grazie alla Dott. Sandra Lucente, per la grande pazienza nel seguire il progetto.
Ancora grazie al Dott. Lorenzo Orecchia (ti tocca due volte!) per essere stato un importante riferimento durante i giorni passati a Cambridge.
Ringrazio i professori che hanno tenuto i corsi, tutti davvero interessanti, da me seguiti (o solo studiati, causa sovrapposizioni(*)):
Lorenzo Orecchia - Seminar in Theoretical Computer Science
Jacob Fox - Probabilistic Methods in Combinatorics
Michael Artin - Introduction to Algebraic Geometry
Johnatan Kelner - Topics in Theoretical Computer Science: an algorithmist's toolkit
Mark Behrens - Algebraic Topology (*)
E ancora, grazie a tutti i matematici che ho avuto occasione di incontrare e conoscere, e a tutti coloro che hanno tenuto seminari.

Questa è stata una esperienza così enormemente importante, così densa di contenuti, che credo debba ancora realizzare quanto abbia significato per me, matematicamente e non: ho avuto la possibilità di partecipare a lezioni di livello estremamente avanzato, di capire come viene spiegata e studiata la matematica al Massachusetts Institute of Technology(!), e di conoscere persone che vengono da posti disparati, ognuno con una sua storia, la sua meravigliosa storia (un'altra cosa che mi affascina dell'America!)



Finally I want to thank the people I met here, and changed my days for the better: Dr. Chelsea Walton, Rachel, Eva, Renee, Francesco, Zhenyu, Madalina. I wish I could spend more time here, in order to know you better and... have another cookie together! You are a reason to come back!

This experience was so important, so dense of contents, that I think I still have not fully appreciated how much it meant to me, mathematically and not: I had the chance to take high-level classes, to see how Mathematics is explained and studied at Massachusetts Institute of Technology (!), and to know people from a lot of different places, everyone with their wonderful story (another thing I like about America!).

Season finale - Discretizing Morse Theory, an algorithmic approach

Vorrei sinceramente ringraziare il Prof. Lorenzo Orecchia per avermi invitato a dare un piccolo seminario, Discretizing Morse Theory: an algorithmic approach, riguardo il mio lavoro di tesi con il Prof. Bruno Benedetti. Devo un ringraziamento anche a Vitantonio per esserci stato e aver scattato le fotografie che trovate in questo post.

Simple Person's Applied Math Seminar (SPAMS) - Scheduling Algorithms

Il MIT non finisce mai di stupire! Oggi ho scoperto dell'esistenza di un ciclo di seminari organizzato da grad students, destinato a graduate students. Ognuno di loro espone agli altri i risultati che sta studiando in quel momento, e ci si confronta in un ambiente più familiare, in cui lo speaker comincia ad apprezzare la bellezza di spiegare agli altri il proprio lavoro, e gli auditori hanno opportunità di trovare nuove idee.

Nel tardo pomeriggio di oggi c'è stato il seminario Scheduling Algorithms, with Applications to Life, tenuto da Samuel Elder (MIT), estremamente interessante!

Brandeis-Harvard-MIT-Northeastern Joint Mathematics Colloquium - Small gaps between primes

Oggi si è tenuto il seminario di teoria dei numeri Small gaps between primes, tenuto da James Maynard (University of Montreal).

Spring break...

Settimana di vacanza, qui al MIT!
In realtà spero finisca presto, e no, non solo per tornare a lezione. Principalmente perché in questa settimana gran parte degli studenti e dei dottorandi che ho conosciuto hanno approfittato dei giorni di pausa per tornare a casa. E così il MIT è ancora una volta troppo silenzioso per me, come è stato i primi giorni qui.
Poco male, anche io ho colto l'occasione, e sono stato a New York. Per poco tempo, ma ci sono stato! Perché «non sei fregato veramente finché hai da parte una buona storia, e qualcuno a cui raccontarla» (A. Baricco)

Combinatorics Seminar - Rotor routing on spanning trees and planar graphs

Nel pomeriggio ho partecipato al seminario Rotor routing on spanning trees and planar graphs, tenuto da Melody Chan (Harvard University).

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$

The evolution of MATLAB & How Math impacts your life

Ho scoperto quasi per caso del seminario The evolution of MATLAB & How Math impacts your life di Cleve Moler, creatore di MATLAB.

Intermezzo

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.

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$

Real Analysis

Maximum Principle

$\Omega$ bounded open in $\mathbb{R}^n$, $u\in C\left(\overline{\Omega}\right)\cap C^2(\Omega)$ harmonic in $\Omega$. Then $\displaystyle\max_\Omega u=\max_{\partial\Omega}u$,

Proof: let $\varepsilon>0$, and let $u_\varepsilon(x):=u(x)+\varepsilon|x|^2$. Then $\Delta u_\varepsilon=2\varepsilon n>0$. So $\displaystyle\max_\Omega u_\varepsilon=\max_{\partial\Omega}u_\varepsilon$, and the claim follows if we let $\varepsilon\rightarrow 0$.

Mean value principle

Let $B_r$ be the open ball of radius $r$ in $\mathbb{R}^n$, and let $u\in C^2\left(\overline{B_r}\right)$ be harmonic in $B_r$. Then
$$
u(0)=\mbox{mean of }u\mbox{ over }\partial B_r.
$$

Proof: set $\Theta u:=u(\Theta^{-1})$ for $\Theta\in O(n)$, and
$$
Au(x):=\mbox{mean of the function }\Theta\in  O(n)\mapsto \Theta u(x)\mbox{ over }O(n),\qquad x\in \overline{B_r}.
$$
Then $\Delta Au=0$ since $\Delta$ is $O(n)$-invariant, and $Au(x)=\mbox{mean of }u\mbox{ over }\partial B_r$ for $|x|=r$. So $Au$ is constant by the maximum principle. But $Au(0)=u(0)$.

Geometry of (contact) manifolds

foliations; distributions; integrability (Frobenius theorem); contact structures

some symplectic linear algebra: symplectic forms and symplectic vector spaces; $\omega\in\Lambda^2(V^{2n})^\ast$ is symplectic iff $\omega^n\neq 0$; isotropic and Lagrangian subspaces of a symplectic vector space

coorientability of hyperplane distributions: if $\xi^{n-1}\subset TM^n$, then $\xi=\ker\alpha$ for some $\alpha\in\Omega^1M$ iff the line bundle $TM/\xi$ is orientable

$\alpha\in\Omega M^{2n+1}$ everywhere non-zero. Then $\ker\alpha$ is contact iff $\alpha(d\alpha)^n$ is a volume form

contact forms of coorientable contact structures

Cartan's magic formula: $\mathcal{L}_X=X\lrcorner d+d X\lrcorner$

the standard contact form on $(\mathbb{R}^{2n+1},x_1,y_1,\dots,x_n,y_n,z)$: $\alpha_{std}=dz-\sum y_idx_i$

contactomorphisms, contact isotopies, contact vector fields; "contact vector fields are the tangent vectors of the group of contactomorphisms at the identity"; contact vector fields on $(M,\xi)$ and sections of $TM/\xi$ "are the same" (as vector spaces of course); isotopy extension; if $(M,\ker\alpha)$ is contact, then $\alpha$ induces an iso between $TM/\xi$ and the trivial line bundle, and hence between contact vector fields and functions. The Reeb vector field of $\alpha$ is then the contact vector field corresponding to $1$

contact conditions in terms of contact forms: $\phi:(M,\ker\alpha)\rightarrow (M,\ker\alpha)$ is contact iff $\phi^\ast\alpha=f\alpha$ for some everywhere non zero $f\in C^\infty M$; $X\in\Gamma TM$ is contact iff $\mathcal{L}_X\alpha\in C^\infty(M)\alpha$

Gray's stability theorem ("contact structures have no deformation theory", or "the space of contact structures modulo diffeomorphisms isotopic to the identity is discrete"); Darboux theorem ($(\mathbb{R}^{2n+1},\alpha_{std})$ is a universal local model, contact manifolds have no local invariants)

Algebraic topology

cats, functors (morphisms between cats), natural transformations (morphisms between functors), adjoint pairs, limits (product, pull-back, projective limit), colimits (push-out, coproduct)

k-spaces, k-ifications, weak Hausdorff spaces, compactly generated spaces

the pointed cat; wedges, smashes, suspensions; homotopy groups

fundamental groupoid and its action on homotopy groups; weak equivalences; relative homotopy groups and the long exact sequence of a pair

cofibrations (homotopy extension property, neighborhood deformation retract pairs); mapping cones and mapping cylinders; cofibers; cofiber sequence

fibrations (homotopy lifting property); homotopy fiber; fiber sequence; Hopf fibration; Hopf invariant; application to the classification of real division algebras

compression lemma; cellular approximation; Whitehead theorem

Topics in several complex variables

Multidimensional Cauchy integral formula, uniqueness of analytic continuation, maximum modulus principle.
Hartog's theorem. Inhomogeneous Cauchy-Riemann equations. Holomorphic implicit and inverse function theorems.

De Rham bicomplex, Dolbeault complex, holomorphic de Rham complex of an open subset of $\mathbb{C}^n$. The Dolbeault complex is acyclic for polydiscs. Strict pluri-sub-harmonicity and pseudoconvexity.

Complex manifolds. $\mathbb{C}P^n$. Affine and projective non-singular algebraic varieties.

$X$ complex compact implies $\mathcal{O}(X)=\mathbb{C}$, so...

... presheaves, sheaves, cohomology of sheaves. Sheaf-theoretic proof of de Rham theorem.

Combinatorics seminar: From combinatorics to motives: cutting and pasting in algebraic geometry

Nel pomeriggio si è tenuto un seminario di Combinatoria, From combinatorics to motives: cutting and pasting in algebraic geometry, tenuto da Ravi Vakil (Stanford).

Seminar in Theoretical Computer Science - Reading assignment

Durante la lezione odierna del corso di Theoretical Computer Science si è discusso dell'articolo Conductance and convergence of Markov Chains, di M. Mihail (Harvard University e U.C. Berkeley). Ai fini della valutazione, si richiede agli studenti di scrivere un survey paper su un argomento scelto tra quelli messi a disposizione dall'instructor. L'obiettivo principale della discussione è stato, dunque, capire qual è il modo migliore di scrivere un articolo scientifico-matematico: si è parlato di come organizzare in modo ottimale le informazioni, e di come rendere più chiare le notazioni.
Credo che questo tipo di corsi, che qui al MIT sono previsti già a livello undergraduate, siano molto utili soprattutto per coloro i quali intendono rimanere nell'ambito accademico, in quanto affiancano alla comprensione dei contenuti un momento in cui ci si occupa dell'aspetto espositivo degli stessi.

Coomologia di $\mathrm{Cone}(i)$!

A seguire, un esercizio di topologia algebrica cui ho lavorato in collaborazione con Vitantonio.

Esercizio. Sia $i: A \hookrightarrow X$ una cofibrazione. Si provi che la mappa canonica $\mathrm{Cone}(i) \rightarrow X/A$ è una equivalenza omotopica ($\mathrm{Cone}(i)$ denota l'unreduced mapping cone) e dedurne che esiste un isomorfismo $H^\ast(X,A)\cong \widetilde H^\ast(X/A)$.

Svolgimento. La mappa canonica $h:\mathrm{Cone}(i) \rightarrow X/A$ è definita come la mappa quoziente $\mathrm{Cone}(i)=X\sqcup \mathrm{Cone}(A)\rightarrow X\sqcup \mathrm{Cone}(A)/\mathrm{Cone}(A)$ composta con l'omeomorfismo $\mathrm{Cone}(i)=X\sqcup \mathrm{Cone}(A)\rightarrow X/A$.
Il mapping cone dell'inclusione è composto da tre tipi di punti: il vertice $v=[A\times\{1\}]$, il resto del cono su $A$ $\{(a,t)\,|\,0\leq t < 1 \}$, dove $(a,0) \equiv a \in A \subset X$, e i punti di $X$ stesso, identificati con i punti di $X \times \{0\}$.
Si definisca $f:A \times I \cup X \times \{0\}\rightarrow \mathrm{Cone}(i)$ come la mappa che collassa $A \times \{1\}$ ad un solo punto. Per definizione di cofibrazione (si veda un post precedente), i seguenti due diagrammi commutativi sono equivalenti: \[ \begin{array}[c]{cccp{2cm}ccc} A& \rightarrow& \underline{\mathrm{Map}}(I,\mathrm{Cone}(i))&& A\times I \sqcup X \times {0}& \stackrel{f}{\rightarrow}& \mathrm{Cone}(i)\\ \scriptstyle{i}\downarrow&\nearrow&\downarrow &&\downarrow&\nearrow&\\ X& \rightarrow & \mathrm{Cone}(i) && X \times I \end{array} \] pertanto, esiste la mappa $\overline f:X \times I\rightarrow \mathrm{Cone}(i)$, ed essa è tale che $\overline f(a,1)=v$, $\overline f(a,t)=(a,t)$, $\overline f(x,0)=x$. Si consideri ora $H_t=\overline f\big|_{X\times \{t\}}$. Poiché $H_1(A)=\{v\}$, $H_1$ si può riguardare come composizione della mappa quoziente $j:X \rightarrow X/A$ e dell'applicazione $g:X/A\rightarrow \mathrm{Cone}(i)$, ovvero $H_1=g\circ j$. Si osservi che $g$ risulta essere continua per definizione di topologia quoziente. Proviamo che $g$ è una equivalenza omotopica, avente $h$ come inversa.
Si consideri innanzitutto l'omotopia $h \circ H_t:X \rightarrow X/A$. Per ogni $t$, essa mappa $A$ nel punto $[A]$ del quoziente. Allora $h \circ H_t$ si fattorizza per dare l'omotopia $h\circ g \simeq [h \circ H_1] \simeq [h \circ H_0] = [j] = 1$.
Viceversa, si consideri $W=(X \times I)/(A \times \{1\})$ e le mappe in figura.

L'applicazione $\overline f'$ è indotta da $\overline f$, mentre $k$ è l'applicazione che mappa $X/A$ nella faccia superiore di $W$, ovvero $k(X/A)=(X\times \{1\}/(A \times \{1\})$. Risulta che
\[ \begin{array}{l} \overline f' \circ l=\mathrm{id}\,,\\ \pi \circ k = \mathrm{id}\,,\\ k \circ \pi \simeq 1\,,\\ \overline f' \circ k=g\,,\\ \pi \circ l =h\,. \end{array} \] Allora $g\circ h=\overline f' \circ (k\circ \pi)\circ l\simeq \overline f' \circ l=1$, come volevamo. Possiamo pertanto affermare che $H^\ast(\mathrm{Cone}(i))\cong H^\ast(X/A)$, da cui $\widetilde H^\ast(\mathrm{Cone}(i))\cong \widetilde H^\ast(X/A)$.
Resta da provare che $H^\ast(\mathrm{Cone}(i))\cong H^\ast(X,A)$. Per far questo utlizzeremo l'assioma di escissione e costruiremo una retrazione di coppie.
Innanzitutto, utilizzando l'assioma di escissione in corrispondenza della terna $[A \times \{1\}]=v \subset \mathrm{int}(\mathrm{Cone}(A))=\mathrm{Cone}(A)\smallsetminus A \subset \mathrm{Cone}(i)$, si ottiene che l'inclusione di coppie
\[ (\mathrm{Cone}(i)\smallsetminus\{v\},\mathrm{Cone}(A)\smallsetminus\{v\}) \hookrightarrow (\mathrm{Cone}(i),\mathrm{Cone}(A)) \] induce un isomorfismo tra i gruppi di omologia e quindi di coomologia:
\[ H^\ast(\mathrm{Cone}(i),\mathrm{Cone}(A))\cong H^\ast(\mathrm{Cone}(i)\smallsetminus\{v\}, \mathrm{Cone}(A)\smallsetminus\{v\}) \] Ora, si osservi che, il Lemma del Serpente garantisce l'esistenza della Sequenza Esatta Lunga per la coomologia della coppia $(\mathrm{Cone}(i),\mathrm{Cone}(A))$:
\[ \cdots\rightarrow H^{n-1}(\mathrm{Cone}(A))\rightarrow H^n(\mathrm{Cone}(i),\mathrm{Cone}(A))\rightarrow H^n(\mathrm{Cone}(i))\rightarrow H^n(\mathrm{Cone}(A))\rightarrow \cdots \] Ma $\mathrm{Cone}(A)=(A\times I)/(A\times \{1\})$ è contraibile (sul vertice $v=[A\times\{1\}]$), pertanto otteniamo:
\[ \cdots\rightarrow 0\rightarrow H^n(\mathrm{Cone}(i),\mathrm{Cone}(A))\rightarrow H^n(\mathrm{Cone}(i))\rightarrow 0\rightarrow \cdots \] ovvero $H^\ast(\mathrm{Cone}(i),\mathrm{Cone}(A))\cong H^\ast(\mathrm{Cone}(i))$.
Inoltre, si osservi che $(X,A)$ è un retratto deformativo di $(\mathrm{Cone}(i)\smallsetminus\{v\}, \mathrm{Cone}(A)\smallsetminus\{v\})$, infatti, ricordando che $\mathrm{Cone}(i)=X\sqcup \mathrm{Cone}(A)$, la retrazione deformativa di coppie $r:(\mathrm{Cone}(i)\smallsetminus\{v\}, \mathrm{Cone}(A)\smallsetminus\{v\})\rightarrow (X,A)$ può essere costruita in modo che
\[ \begin{array}{ll} r(a,t)= (a,0) &\text{per ogni } (a,t) \in A \times [0,1)=\mathrm{Cone}(A)\smallsetminus\{v\}\,, \\ r(x)=x &\text{per ogni } x \in \mathrm{Cone}(i) \smallsetminus \mathrm{Cone}(A) = X\,. \end{array} \] Allora risulta che $H^\ast(\mathrm{Cone}(i)\smallsetminus\{v\}, \mathrm{Cone}(A)\smallsetminus\{v\})\cong H^\ast(X,A)$, da cui $H^\ast(X,A)\cong H^\ast(\mathrm{Cone}(i))\cong \widetilde H^\ast(\mathrm{Cone}(i))$.
Per quanto provato in precedenza, concludiamo che $H^\ast(X,A)\cong \widetilde H^\ast(X/A)$.

References: Glen E. Bredon, Topology and Geometry, Springer (1993).

The daily problem set

Ecco un esercizio per il corso Theoretical Computer Science.

Esercizio. Sia $G = (V,E)$ un grafo di diametro $d$. Provare che la matrice di adiacenza di $G$, $A_G$, ammette almeno $d+1$ autovalori distinti.

Svolgimento. Poniamo $A:=A_G$. Siano $x$ e $y$ vertici di $G$ tali che $\mathrm{dist}(x,y)=d$, e sia $x=v_0, v_1,\dots,v_d=y$ un path di lunghezza $d$ da $x$ a $y$. Allora, per ogni $i \in \{1,\dots,d\}$ esiste un cammino di lunghezza $i$ (ma non più breve) che collega $x=v_0$ a $v_i$. Pertanto $A^i$ ha entrata non nulla in corrispondenza di $(v_0,v_i)$, mentre la stessa entrata nella matrice $A^j$, $j\in \{0,\dots,i-1\}$. Da ciò segue che, per ogni $i \in \{1,\dots,d\}$, $\{I,A,\dots,A^i\}$ sono linearmente indipendenti, e, in particolare, $\{I,A,\dots,A^d\}$ sono linearmente indipendenti.
Inoltre, si noti che $A$ è simmetrica, quindi diagonalizzabile. Allora il polinomio minimo di $A$ si può scrivere nella forma $m_A=(x-\mu_1)\cdots(x-\mu_k)$, dove $\mu_1,\dots,\mu_k$ sono gli autovalori distinti di $A$. Avendo provato che $I,A,\dots,A^d$ sono linearmente indipendenti, non esiste alcun polinomio $\widetilde m$ di grado minore o uguale a $d$ tale che $\widetilde m(A)=0$. Poiché per definizione $m_A(A)=0$, si ha che $k=\deg(m_A)>d$, ovvero $k\geq d+1$. $\square$

Combinatorics seminar: Monochromatic covers in edge-colored graphs and hypergraphs

Dopo qualche settimana al MIT, tra le tante cose, s'impara che qui c'è sempre qualcosa di interessante da fare. Per esempio, oggi pomeriggio c'è stato un bel seminario di Combinatoria, Monochromatic covers in edge-colored graphs and hypergraphs di Gabor Sarkozy (Worcester Polytechnic Institute).