Combinatoria estremale
I problemi estremali sono quei problemi di combinatoria che richiedono di determinare la cardinalità massima che può avere una famiglia di insiemi che soddisfa certe condizioni.
Tecnica degli spazi vettoriali
Un metodo spesso efficace per risolvere un problema estremale consiste nell’associare a ogni elemento di una famiglia di insiemi un vettore di un opportuno spazio vettoriale in modo univoco, e fare in modo che vettori che soddisfano le nostre condizioni siano ortogonali. Se si riesce a dimostrare che i vettori così ottenuti sono linearmente indipendenti, si otterrà la maggiorazione richiesta: la cardinalità della famiglia non potrà infatti superare la dimensione dello spazio .
Teorema 1 Sia una famiglia di sottoinsiemi di tale che:
- ogni sottoinsieme di ha un numero dispari di elementi;
- due sottoinsiemi di si intersecano in un numero pari di elementi. Allora la famiglia ha al più sottoinsiemi.
Dim Codifichiamo i sottoinsiemi di una famiglia con vettori , ad componenti, con ovvio significato. Effettuando un prodotto scalare tra due insiemi:
come è ovvio verificare. Se lavoriamo in , se l’intersezione ha cardinalità pari otteniamo , se dispari . Allora il nostro vincolo equivale a dire:
Quindi la mia famiglia estremale sarà un insieme di vettori ortonormali, di conseguenza ne posso avere al massimo come la dimensione dello spazio vettoriale, .
Corollario Una famiglia di singleton di ha cardinalità massima . Dim Segue dal teorema precedente: i singleton hanno cardinalità uno (dispari), e si intersecano in zero elementi (pari).
Teorema di Sperner
Def Una famiglia di sottoinsiemi di viene detta di famiglia di Sperner se presi comunque due sottoinsiemi della famiglia nessuno dei due è conenuto nell’altro:
Oss E’ chiaro come ogni famiglia uniforme (sottoinsiemi della stessa cardinalità) sia di Sperner (per essere distinti devono avere almeno un elemento non in comune).
Def Una famiglia di sottoinsiemi di viene detta di catena se presi comunque due sottoinsiemi della famiglia uno dei due è conenuto nell’altro:
Oss E’ una proprietà opposta a quella di Sperner, anticatena è sinonimo di famiglia di Sperner.
Una catena massimale dei sottoinsiemi di è una catena con sottoinsiemi di cardinalità crescente che parte dal vuoto. Quante catene massimali esistono in totale? Inizio col vuoto, una scelta. Poi scelgo un singleto, scelte. Ora un insieme di cardinalità due che contiene il singleton, quindi , e cosi via. Tutte le catene massimali sono dunque . Ora ci chiediamo quante sono le catene massimali in cui compare un dato insieme fissato . Prima conto tutte le catene che arrivano ad , quindi , e i modo per estenderle sono , in totale:
Torniamo alle anticatene, sia un’anticatena di , ed un elemento di . E’ chiaro che ogni catena massimale non può passare per più di un elemento di , quindi per ogni le catene massimali passanti per questi insiemi sono disgiunte.
(non ho fatto una partizione compelta, potrei avere pochi elementi nell’anticatena). Ma so calcolare il numero di catene che passano per un insieme di cardinalità :
risulato noto come inequality: Teorema (Disuquaglianza LYM) Se è una famiglia di Sperner (anticatena) di sottoinsieme di , allora vale:
Dim Dividendo per ottengo la definizione del coefficente binomiale.
Da questa segue il teorma di Sperner.
Teorema (Sperner 1928) Se è una famiglai di Sperner di sottoinsiemi di , allora:
Dim Segue direttamente dalla disuguaglianza LYM, infatti il valore massimo del coefficiente binomiale si ottiene in (oppure in è bimodale), quindi:
|\mathcal{F}|\binom{n}{\lfloor \frac{n}{2}\rfloor}^{-1} \leq \sum_{I \in \mathcal{F}} \binom{n}{|I|}^{-1} \leq 1 \quad \square$$ Quindi la famiglia uniforme di sottoinsiemi di $[n]$ di cardinalità $\lfloor n/2 \rfloor$, che è di Sperner è di cardinalità massima. Non abbiamo mostrato l'unicità. **Oss** Ottengo una sola famiglia se $n$ è pari, due se $n$ è dispari (prendendo parte intera superiore o inferiore). ## Famiglia intersecante $I(n)$ **Def** Una famiglia $\mathcal{F}$ di sottoinsiemi di $[n]$ viene detta _intersecante_ se vale $\forall A,B \in \mathcal{F}$ si ha $A \cap B \neq \emptyset$. Ci chiediamo, qual è la massima cardinalità di una famiglia intersecante. **Proposizione** Sia $I(n)$ la cardinalità massima di una famiglia intersecante di sottoinsiemi di $[n]$:I(n) := \max\left{ |\mathcal{F}| , :, \mathcal{F} \subseteq 2^{[n]}, \text { intersecante}\right}
Allora $I(n)=2^{n-1}$. **Dim** Dimostriamo prima che $I(n) \geq 2^{n-1}$ esibendo una famiglia intersecante con questa proprietà. Ma è facile, basta richiedere che tutte contengano un elemento fissato, di fatto lo sto togliendo da $n$. Questa famiglia ha cardinalità $2^{n-1}$. Ora dimostriamo $I(n) \leq 2^{n-1}$. Scriviamo tutti gli elementi di $2^{[n]}$ in una tabella, mettendo su ogni riga un insieme $A$ ed il suo complementare $A^c$. La tabella avrà $2^{n-1}$ righe. Se $E \in \mathcal{F}$, allora di certo non posso includere in $\mathcal{F}$ il suo complementare (l'argomento delle righe è superfluo, basta notare che se scelgo un insieme, non posso prendere il complementare, quindi di fatto ho dimezzato le scelte!). $\square$ **Oss** Le famiglie estremali non sono uniche! Ne esistono sicuramente più di due, passo alla "famiglia complentare". Vale una teorema nel caso in cui richiediamo che le famiglia di sottoinsiemi siano uniformi di cardinalità $k$, [[Erdos-Ko-Rado theorem]].