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).

The late late problem set

Ancora un esercizio di topologia algebrica!

Definizione. Si dice che l'applicazione $i: A \rightarrow X$ è una cofibrazione se verifica la proprietà di estensione dell'omotopia (Homotopy Extension Property - HEP): per ogni $f:X\rightarrow Y$ e $H:A \rightarrow \mathrm{Map}(I,Y)$, $I=[0,1]$, esiste $\overline H:X \rightarrow \mathrm{Map}(I,Y)$ tale che il seguente diagramma è commutativo: \[ \begin{array}[c]{ccc} A&\stackrel{H}{\rightarrow}&\underline{\mathrm{Map}}(I,Y)\\ \downarrow\scriptstyle{i}&\stackrel{\overline H}{\nearrow}&\downarrow\scriptstyle{\mathrm{ev}_0}\\ X&\stackrel{f}{\rightarrow}&Y \end{array} \]
($\underline{\mathrm{Map}}(I,Y)$ denota lo spazio (topologico) delle applicazione da $I$ in $Y$)
Equivalentemente, per ogni $f:X\rightarrow Y$ e ogni omotopia $H:f\big|_A \simeq g$, esistono $\overline g:X\rightarrow Y$ e $\overline H:f \simeq \overline g$ tale che $\overline H$ sia estensione di $H$.

Esercizio. Provare che se $A \hookrightarrow X$ è una cofibrazione, allora $A\times Y \hookrightarrow X\times Y$ è una cofibrazione

Svolgimento.  Si considerino $f:X\times Y\rightarrow Z$ e l'omotopia $H:A\times Y \rightarrow \underline{\mathrm{Map}}(I,Z)$ tali che il seguente diagramma commuti: \[ \begin{array}[c]{ccc} A\times Y&\rightarrow&\underline{\mathrm{Map}}(I,Z)\\ \downarrow& &\downarrow\\ X\times Y&\rightarrow &Z \end{array} \] Ciò è equivalente a dire che il seguente diagramma è commutativo: \[ \begin{array}[c]{ccc} A&\rightarrow&\underline{\mathrm{Map}}(I,\underline{\mathrm{Map}}(Y,Z))\\ \scriptstyle{i}\downarrow& &\downarrow\\ X&\rightarrow &\underline{\mathrm{Map}}(Y,Z) \end{array} \] Applico l'ipotesi che $A \hookrightarrow X$ è una cofibrazione, quindi esiste $\overline H : X\rightarrow \underline{\mathrm{Map}}(I,\underline{\mathrm{Map}}(Y,Z))$ tale che: \[ \begin{array}[c]{ccc} A&\rightarrow&\underline{\mathrm{Map}}(I,\underline{\mathrm{Map}}(Y,Z))\\ \scriptstyle{i}\downarrow&\nearrow &\downarrow\\ X&\rightarrow &\underline{\mathrm{Map}}(Y,Z) \end{array} \] L'esistenza di $\overline H$ è equivalente all'esistenza di $\overline H: X \times Y \rightarrow \underline{\mathrm{Map}}(I,Z)$ che rende commutativo: \[ \begin{array}[c]{ccc} A\times Y&\rightarrow&\underline{\mathrm{Map}}(I,Z)\\ \downarrow&\nearrow &\downarrow\\ X\times Y&\rightarrow &Z \end{array} \] Segue l'asserto. $\square$

Mit Mathematics...

Il dipartimento di Matematica del MIT: