Sui grafi di Kneser K(n,2)

[e3353cdc139f9576d1418ef5ef3cff2aac614a86]

Ciao

Vi propongo un nuovo problemino.

Sia [tex]n \geq 3[/tex] un intero. Sia [tex]K(n,2)[/tex] il grafo (semplice) i cui vertici sono i [tex]\binom{n}{2}[/tex] sottoinsiemi di [tex]\{1,...,n\}[/tex] di [tex]2[/tex] elementi, e due vertici sono collegati da un arco se sono insiemisticamente disgiunti, cioè se la loro intersezione è l'insieme vuoto.

Per esempio il grafo [tex]K(5,2)[/tex] è rappresentabile come segue:



Si tratta di un caso particolare della famiglia dei "grafi di Kneser", [tex]K(n,t)[/tex], la generalizzazione ovvia dove anziché [tex]2[/tex] c'è [tex]t[/tex].

Dato un grafo [tex]G[/tex] indichiamo con [tex]\omega(G)[/tex] il massimo numero di vertici di un sottografo completo (o "cricca") di [tex]G[/tex] (ricordo che un grafo si dice completo se ogni due vertici sono connessi) ed indichiamo con [tex]\chi(G)[/tex] il "numero cromatico" di [tex]G[/tex], cioè il minimo numero di colori che servono a colorare i vertici di [tex]G[/tex] in modo tale che due vertici collegati ricevano colori diversi.

Osserviamo che ovviamente si ha [tex]\omega(G) \leq \chi(G)[/tex]

Calcolare [tex]\omega(K(n,2))[/tex] e [tex]\chi(K(n,2))[/tex].

Si tratta di un esercizio ispirato dalla lettura dell'articolo "On finite simple groups and Kneser graphs" di Lucchini e Maróti, ma credo che si possa trovare la soluzione anche altrove.

[Rggb1]

Non male come problemino (posso ficcare il naso?)

La colorazione di $K(n,k)$ è un risultato noto ("altrove" == in un sacco di documenti reperibili sul web...) L'altro vale uno di meno. Ma vuoi una dimostrazione?

EDIT: nascondo.

[e3353cdc139f9576d1418ef5ef3cff2aac614a86]

Il problema formulato in questo caso particolare non è trascendentale e credo sia bello trovare una dimostrazione.

[Deckard1]

Segue una dimostrazione inutile perché non avevo letto attentamente il problema. La lascio così, per dare un senso a questi 5 minuti di follia.

Supponiamo che il grafo contenga un triangolo . Allora esisterebbero 3 sottoinsiemi di ${1,...,5}$ disgiunti. Ciò è impossibile perché altrimenti $ n >= 6$. Ovviamente la massima cricca deve avere almeno dimensione 2 altrimenti il grafo non avrebbe lati. Abbiamo dimostrato che $ ω(K(5,2) = 2$.
$2 <= χ(K(5,2) <= 3$ per il disegno e per il punto precedente. $χ(K(5,2) >= 3$ perché il grafo contiene un ciclo di lunghezza dispari. Quindi $χ(K(5,2) = 3$.
Sono un cretino. Ho trattato il caso particolare (il grafo di Petersen in figura) senza accorgermi che il problema si riferiva quello generale .
Non so fare la chi bella come la vostra .

EDIT: Posso riutilizzare parte della dimostrazione per calcolare $\omega(K(n,2))$:

Esiste ovviamente una cricca di dimensione $ \lfloor n/2 \rfloor$. Non esiste una cricca di dimensione maggiore poiché altrimenti avremmo più di n elementi distinti.

La seconda parte per ora non mi viene in mente.

[Rggb1]

A determinare $omega(K(n,2))$ ci si arriva (e il risultato di Deckard va benissimo). Ora, poiché dici che è particolare, dovrebbe esserlo anche determinare il numero cromatico, ma non mi è riuscito di trovare ancora nulla. (a parte il risultato, noto).

Speravo di vedere qualcosa di combinatorio, ma pure lì... ci dormirò sopra.

[Rggb1]

@Martino
In pratica mi sono arenato nel caso banale della colorazione con almeno $n-1$ colori, e non ho trovato metodi combinatori validi per migliorare il limite fino a trovare il risultato.

Quindi -curiosone- sono andato a vedere la soluzione che hai citato. Ma poiché in algebra sono una schiappa ci ho capito poco, visto che mi mancano alcune (parecchie) nozioni, e quindi non mi è servito a molto: cercavo un metodo combinatorio e non ce l'ho trovato (o io non riesco a vederlo per ignoranza, il che è lo stesso).

Ci penserò ancora. Sento che una soluzione combinatoria "semplice" ci deve essere (sempre che si possa parlare di "sensazioni" in matematica ).

[e3353cdc139f9576d1418ef5ef3cff2aac614a86]

"Rggb":Quindi -curiosone- sono andato a vedere la soluzione che hai citato. Ma poiché in algebra sono una schiappa ci ho capito poco, visto che mi mancano alcune (parecchie) nozioni, e quindi non mi è servito a molto.

Non capisco di cosa parli Vai a pagina 5 dell'articolo che ho citato. Lemmi 2.2 e 2.3. Tutto cio' che viene detto e' puramente insiemistico-combinatorio.

@Deckard: bene per [tex]\omega[/tex]

[Rggb1]

Ok. Ora ho capito perché non avevo capito.

[Deckard1]

Sono riuscito a trovare una colorazione che usa $ n - 2 $ colori: partiamo colorando ugualmente tutti i nodi etichettati da un insieme contenente il numero 1 (avendo un elemento in comune essi sono indipendenti tra loro). Esistono $n-1$ di questi insiemi. Dopodiché quelli etichettati da 2. Ne esistono ancora $n-1$, ma l'insieme ${1,2}$ è già stato colorato. Coloriamo gli $n-3$ nodi rimanenti contenenti il numero 3 e così via. Per completare questa colorazione utilizzeremo $n-1$ colori poiché:
$ (n-1)+(n-2)+...+2+1 = n(n-1)/2$ che è uguale al numero dei nodi.
Tuttavia l'ultimo nodo colorato sarà del tipo ${n-1, n}$ quando la precedente colorazione avrà colorato due nodi del tipo ${n-2,n-1}$ e ${n-2,n}$. Di conseguenza posso colorare anche ${n-1, n}$ nello stesso modo di quei due nodi. Ciò dimostra che esiste una colorazione a $n-2$ colori.
Credo sia abbastanza intuitivo capire che questa è la colorazione ottimale, tuttavia ho difficoltà nel dimostrarlo. Suggerimenti?

[Rggb1]

E' proprio lì il nodo, bisogna dimostrare che è ottimale. Suggerimento di metodo: per fare questo devi dimostrare che il numero cromatico è almeno il numero del tuo risultato. Ci si può arrivare (io però non direi che la dimostrazione è intuitiva... non per me almeno).

Per altri suggerimenti lascio la parola a Martino visto che ho "sbirciato" la soluzione.

[Deckard1]

"Rggb":E' proprio lì il nodo, bisogna dimostrare che è ottimale. Suggerimento di metodo: per fare questo devi dimostrare che il numero cromatico è almeno il numero del tuo risultato. Ci si può arrivare (io però non direi che la dimostrazione è intuitiva... non per me almeno).

Senz'altro. Io infatti ho detto di trovare intuitivamente ottimale la mia soluzione, non che la dimostrazione dell'ottimalità sia intuitiva.

[Deckard1]

Ci provo:

Supponiamo esista una colorazione migliore (= utilizza meno colori). Poiché la colorazione da me proposta ad ogni colore esaurisce l'insieme d'indipendenza massimale tra quelli rimasti, necessariamente la colorazione ottimale dovrà al colore i-esimo colorare un numero minore di $n-i$ nodi (supponiamo $n-i-k$). Esisterà anche un j t.c. al passo j-esimo $(j>i)$ dovrà invece colorare più di $n-j$ nodi per compensare il numero minore di nodi colorati finora (si prenda j più piccolo possibile). Esistono ovviamente $n-j$ nodi indipendenti (etichettati con uno stesso elemento, x ad esempio). Possiamo supporre che nella colorazione i-esima (in tutte le altre sì) siano stati colorati nodi non contenenti alcun elemento x. Allora al passo j-esimo coloreremo $n-j+1$ nodi, ma comunque il numero totale dei nodi colorati dalla procedura che si ritiene ottimale rimarrà minore o uguale a quelli colorati dalla procedura descritta prima. La situazione non cambia se prima del passo j-esimo esistono più passi di colorazione che colorano un numero minore di nodi (se ne esistono h, alla j-esima si potranno avere al più $n-j+k$ nodi colorati). Poiché ciò è vero per ogni i e j così scelti, si avrà che per ogni $l$ ($1

Mi sembra corretta però non mi convince, è un po' confusa.
Edit: e soprattutto mi sembra affermare anche che un algoritmo greedy così costruito sia sempre ottimale. Mi pare improbabile.

Cita

Segnala