Don't take life too seriously: it's just a temporary situation

Tutte – Beraha (costanti di)

Matematica combinatoria  Teoria dei grafi 

Dato un grafo con k vertici, il numero di modi per colorarne i nodi con n colori, in modo che nodi connessi da un arco abbiano colori diversi, è un polinomio P(n) di grado k, detto “polinomio cromatico” del grafo.

Alcuni esempi di polinomi cromatici:

  • per il poligono con k vertici è (n – 1)k + (–1)k(n – 1) e in particolare per il triangolo è n(n – 1)(n – 2), per il quadrato è n(n – 1)(n2 – 3n + 3) e per il pentagono è n(n – 1)(n – 2)(n2 – 2n + 2);

  • per il quadrato con le diagonali (equivalente a un tetraedro) è n(n – 1)(n – 2)(n – 3);

  • per il reticolo dell’ottaedro è n(n – 1)(n – 2)(n3 – 9n2 + 29n – 32);

  • per il reticolo del cubo è n8 – 12n7 + 66n6 – 214n5 + 441n4 – 572n3 + 423n2 – 133n;

  • per un albero con k nodi è n(n – 1)k – 1;

  • per una foresta di alberi, con k nodi, m archi e r componenti disgiunte è (–1)krnr(1 – n)m;

  • per un grafo lineare con k nodi e per il grafo a stella con k nodi in tutto è n(n – 1)k – 1;

  • per la ruota con k nodi è n((n – 2)k – 1 – (–1)k(n – 2)) e in particolare per il quadrato con tutti i vertici connessi al centro è n(n – 1)(n – 2)(n2 – 5n + 7) e per il pentagono con tutti i vertici connessi al centro è n(n – 1)(n – 2)(n – 3)(n2 – 4n + 5);

  • per grafo completo di k nodi, ciascuno dei quali connesso da un arco a ogni altro, è Polinomio cromatico del grafo completo di k nodi.

 

Si può dimostrare che in ogni polinomio cromatico:

  • il grado è uguale al numero di nodi;

  • il coefficiente del termine di grado massimo è 1;

  • il coefficiente del del termine di grado immediatamente seguente è il numero di archi, con segno negativo;

  • i coefficienti hanno segni alternativamente positivi e negativi (Birkoff, 1912);

  • se il grafo ha k componenti disgiunti, il polinomio cromatico è il prodotto dei polinomi cromatici delle singole componenti, pertanto non contiene potenze della variabile con esponente inferiore a k; in particolare il termine costante è sempre zero;

  • zero e uno sono radici del polinomio.

 

Non tutti i polinomi che rispettano queste condizioni sono polinomi cromatici di un grafo; per esempio, il polinomio x4 – 4x3 + 3x2 non è il polinomio cromatici di alcun grafo.

 

I coefficienti am di un polinomio cromatico Polinomio cromatico soddisfano la relazione Relazione soddisfatta dai coefficienti di un polinomio cromatico, dove l’uguaglianza vale se e solo se il grafo è un albero (F.M. Dong, F.K Koh e K.L. Teo, 2005).

 

Un polinomio cromatico non identifica un grafo, perché grafi diversi possono avere lo stesso polinomio cromatico, come capita per esempio nel caso di un grafo lineare con k nodi e un grafo a stella con k nodi in tutto, e dato un polinomio con le caratteristiche sopra elencate non è facile stabilire se sia il polinomio cromatico di qualche grafo o no.

 

In generale calcolare il polinomio cromatico di un grafo è molto laborioso: il tempo necessario con tutti gli algoritmi noti cresce esponenzialmente all’aumentare del numero di nodi; tecnicamente è un problema almeno NP-completo (S. Skiena, 1990).

 

Il numero cromatico è il minimo numero di colori necessari per colorare i nodi di un grafo, in modo che non vi siano due nodi dello stesso colore uniti da un arco, quindi è il minimo intero che renda maggiore di zero il polinomio. Chiaramente è sempre possibile colorare un grafo di n vertici con altrettanti colori, quindi P(n) > 0.

 

Se il grafo contiene almeno due punti connessi da un arco, servono chiaramente almeno due colori, quindi, P(1) = 0 e se contiene almeno un triangolo servono 3 colori, quindi P(2) = 0.

 

P(3) non è zero se e solo se il grafo è euleriano, vale a dire il numero di archi connessi a ogni nodo è pari. Tradotto nel linguaggio della colorazione delle mappe, la mappa è colorabile con 3 soli colori se e solo se ogni regione ha un numero pari di regioni confinanti.

 

Un grafo si dice planare se può essere disegnato sul piano senza che due archi si incrocino. Data una mappa di n regioni, se prendiamo un punto in ciascuna e lo colleghiamo con un arco al punto scelto nelle regioni confinanti, otteniamo un grafo planare; il famoso teorema dei 4 colori assicura che qualsiasi insieme di regioni disegnato sul piano o sulla sfera può essere colorato con 4 soli colori in modo che regioni confinanti non siano dello stesso colore (v. numeri di Heawood). In termini di polinomi cromatici questo significa che per grafi planari P(4) > 0.

 

I polinomi cromatici sono in genere piuttosto complicati e, sebbene nel definirli si faccia uso solo di interi, viene naturale chiedersi che succeda se li si calcola per valori reali della variabile e in particolare per quali valori della variabile si annullino, cioè quali siano le loro radici.

S. Beraha suppose che gli zeri dei polinomi cromatici si raggruppino intorno ai valori, detti “costanti di Tutte – Beraha”, dati da Formula per la definizione delle costanti di Tutte – Beraha. I primi valori delle costanti sono mostrati nella tabella seguente.

n

Bn

1

2 + 2cos(2π) = 4

2

2 + 2cosπ = 0

3

Costante di Tutte – Beraha B(3)

4

Costante di Tutte – Beraha B(4)

5

Costante di Tutte – Beraha B(5)

6

Costante di Tutte – Beraha B(6)

7

Costante di Tutte – Beraha B(7)

8

Costante di Tutte – Beraha B(8)

9

Costante di Tutte – Beraha B(9)

10

Costante di Tutte – Beraha B(10)

11

Costante di Tutte – Beraha B(11)

12

Costante di Tutte – Beraha B(12)

13

Costante di Tutte – Beraha B(13)

14

Costante di Tutte – Beraha B(14)

15

Costante di Tutte – Beraha B(15)

16

Costante di Tutte – Beraha B(16)

17

Costante di Tutte – Beraha B(17)

18

Costante di Tutte – Beraha B(18)

19

Costante di Tutte – Beraha B(19)

20

Costante di Tutte – Beraha B(20)

 

Dato che i polinomi cromatici sono polinomi a coefficienti interi con il coefficiente del termine di grado massimo uguale a 1, tutte le radici sono interi algebrici, come pure le costanti di Tutte – Beraha.

 

Gli esperti cercarono di stabilire quali potessero essere gli zeri dei polinomi cromatici, cercando di dimostrare che non possono trovarsi in determinati intervalli:

  • per prima cosa fu dimostrato che ci sono zeri negativi né nell’intervallo (0 .. 1);

  • Sokal dimostrò che tutti gli zeri del polinomio cromatico di un grafo con n nodi sono minori, in valore assoluto, di Kn, dove K è il minimo della funzione (x + e^x) / log (1 + x * e^(–x)) e vale circa 7.9639060759, per x ≈ 0.4037744626;

  • B. Jackson dimostrò nel 1993 che non hanno zeri nell’intervallo Intervallo privo di zeri di polinomi cromatici; come conseguenza se λ = p + q * sqrt(r), con p e q razionali e r intero positivo, ma non quadrato, e p – |q| * sqrt(r) < 32 / 27, λ non è radice di alcun polinomio cromatico e le potenze di φ con esponente intero positivo non sono radici di alcun polinomio cromatico;

  • infine C. Thomassen dimostrò nel 1997 che che se P(x) è il polinomio cromatico di un grafo con n nodi, |P(x)| ≥ x(1 – x)n – 1, per 1 ≤ x ≤ 32 / 27, mentre esistono zeri di polinomi cromatici arbitrariamente vicini a qualsiasi numero maggiore di 32 / 27, quindi non vi sono altri intervalli privi di zeri.

 

Per quanto riguarda i grafi planari:

  • Birkoff e Lewis dimostrarono nel 1946 che i polinomi cromatici dei grafi planari non hanno zeri nell’intervallo (1.. 2) né maggiori o uguali a 5;

  • Thomassen propose la congettura, tuttora non dimostrata, che le radici dei polinomi cromatici dei grafi planari siano un insieme denso nell’intervallo (32 / 27 .. 4).

 

E’ stato dimostrato che alcuni numeri reali non sono radici di alcun polinomio cromatico.

  • W.T. Tutte dimostrò nel 1970 che B2 = φ2 = φ + 1 ≈ 2.6180339887 non è radice di alcun polinomio cromatico.

  • J. Salas e A.D. Sokal dimostrarono nel 2001 che 4 * cos(k * Pi / n)^2 non è radice di alcun polinomio cromatico, per n uguale a 5, 7, 8, 9 o maggiore di 10 e k primo rispetto a n e che B10 = 2 + φ ≈ 3.6180339887 e 3 – φ ≈ 1.3819660113 non sono radici di alcun polinomio cromatico di un grafo planare che contenga al massimo una maglia che non sia un triangolo. Pertanto B10 è l’unica costante di Tutte – Beraha non intera che potrebbe essere radice di un polinomio cromatico.

  • Saeid Alikhani e Yee-Hhock Peng dimostrarono nel 2009 che per n pari, nessuna costante di n-bonacci né le loro potenze con esponente intero positivo sono radici di alcun polinomio cromatico. Gli stessi matematici supposero, senza riuscire a dimostrarlo, che la stessa proprietà valga per n dispari e dimostrarono che se n = 2k + 1, la costante di n-bonacci non è radice del polinomio cromatico di un grafo con al massimo 4k + 2 nodi.

 

Se il grafo è triangolare (ossia costituito esclusivamente da maglie triangolari) e planare, i polinomi ottenuti sembrano avere sempre un numero di Beraha come radice, ma non è stato dimostrato.

 

Per quanto riguarda i grafi planari:

  • S. Beraha stesso dimostrò che B5 è un punto di accumulazione degli zeri dei polinomi cromatici di certe triangolazioni del piano, quindi di grafi planari;

  • S. Beraha , J. Kahane e R. Reid nel 1973 estesero la dimostrazione a B7 e B10;

  • J.L. Jacobsen, J. Salas e A.D. Sokal estesero nel 2003 la dimostrazione a B8 e B9;

  • G. Royle dimostrò che anche B1 è un punto di accumulazione di radici di polinomi cromatici di grafi planari.

Dato che 4 è un punto di accumulazione degli zeri dei polinomi e potrebbe essere il limite dei punti di accumulazione, Finch (v. la bibliografia) osserva acutamente che il teorema dei 4 colori è vero, ma quasi falso!

 

Una famiglia di grafi particolarmente studiata è quella delle triangolazioni sferiche, grafi ottenibili come un insieme di punti sulla sfera, connessi tra loro a formare una rete a maglie triangolari. In termini di regioni da colorare, una triangolazione sferica diviene una mappa della sfera, nella quale nessun punto sia sul confine di più di 3 regioni, condizione comunemente soddisfatta dalla mappe reali.

Dato che per il polinomio cromatico di una triangolazione sferica P(x) vale P(x) > 0 per x ≥ 5, viene naturale chiedersi dove si trovino gli zeri del polinomio.

Sembra che il polinomio cromatico di una triangolazione sferica non abbia zeri tra 1 e 2 e abbia uno zero tra 2 e 3, ma non è stato dimostrato.

Berman e W.T. Tutte dimostrarono nel 1969 che per il polinomio cromatico di una triangolazione sferica P(x) vale 0 < |P(φ + 1)| ≤ φ5 – n, vale a dire che per Valore di B5 il polinomio non si annulla, ma al crescere di n va arbitrariamente vicino allo zero per questo valore della variabile; per questo φ + 1 è detta “radice aurea”, pur non essendo realmente una radice del polinomio. Tutte nel 1969 dimostrò anche che P(φ + 2) = (φ + 2)φ3n – 10P(φ + 1)2 e quindi P(φ + 2) > 0.

Oltre a φ + 1, l’evidenza numerica indica un punto di accumulazione di zeri dei polinomi cromatici delle triangolazioni sferiche a Valore della radice argentea, detta “radice argentea” per analogia con la radice aurea.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.