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

Indice

  1. 1. Pagina principale
  2. 2. Numeri di Ramsey per grafi non completi
  3. 3. Numeri di Ramsey per ipergrafi

Supponiamo di prendere n punti sul piano e di collegarli tramite segmenti, in tutti i modi possibili, vale a dire con Numero di archi in un grafo completo con n nodi archi: il grafo risultante è il grafo completo per n punti e si indica con Kn.

La figura seguente mostra i grafi completi fino a K6.

 

Grafi completi fino a 6 nodi

 

 

Supponiamo di colorare gli archi di K6 di rosso o blu: comunque lo faremo, ci sarà sempre un triangolo rosso o uno blu. Un modo equivalente di presentare la stessa conclusione è dire che tra 6 persone ce ne devono per forza essere 3 che si conoscono tutte tra loro o altrettante, nessuna delle quali conosce le altre. Se riduciamo le persone a 5, questo non è più vero.

Il matematico inglese Frank Plumpton Ramsey (Cambridge, UK,, 22/1/1903 – Londra, 19/2/1930) dimostrò nel 1930 che per ogni valore di n esiste un k = R(n) tale che Kk, colorato con due colori, contiene un Kn con archi tutti dello stesso colore; se n = 3 abbiamo il triangolo degli esempi precedenti.

Il concetto chiave espresso dal teorema di Ramsey è che ogni struttura complessa abbastanza grande, per quanto disordinata possa apparire, contiene una struttura ordinata di qualsiasi dimensione voluta; all’incirca lo stesso concetto espresso dai teoremi di Schur (v. numeri di Schur) e van der Waerden (v. numeri di van der Waerden).

 

La versione infinita del teorema afferma che un grafo completo con un’infinità numerabile di nodi colorato con due colori contiene un sottografo completo con un’infinità numerabile di nodi, colorato con un solo colore.

 

Se anziché cercare un solo grafo completo ne cerchiamo uno tra due distinti, Kn e Km, di nuovo il teorema ci assicura che in ogni Kk, esiste un Kn del primo colore o un Km del secondo, se k è almeno R(n, m). Dalla definizione segue che R(n, m) = R(m, n).

Per esempio, R(3, 4) = 9, vale a dire che tra 9 persone ne possiamo trovare almeno 3 che si conoscono o 4 tutte mutuamente estranee.

I numeri di Ramsey R(n) = R(n, n) della versione originale del problema sono anche chiamati “numeri di Ramsey diagonali”.

 

La letteratura sui numeri di Ramsey è immensa; sono stati trovati e raffinati più volte i limiti entro i quali debbono trovarsi i numeri di Ramsey; di seguito sono riportati alcuni dei principali risultati.

Limiti per i numeri di Ramsey diagonali:

Limite inferiore per R(n) (Paul Erdös, 1947); J. Spencer nel 1975 migliorò leggermente il limite, dimostrando che Limite inferiore per R(n);

R(n) ≤ 4R(n – 2, n) + 2 (K. Walker, 1968);

Limite superiore per R(n), per una costante positiva c (David Conlon, 2009);

Limite superiore per R(n), per una costante positiva c (David Conlon, 2009);

Limite superiore per R(n), per qualsiasi r > 0 una costante positiva cr che dipende da r (David Conlon, 2009).

 

Limiti per i numeri di Ramsey generali:

Limite inferiore per R(n, m), per una costante c che dipende solo da n (Bohman e Keevash);

Limite inferiore per R(n, m) (Paul Erdös e G. Szekeres, 1935) e quindi Limite inferiore per R(n) per una costante c;

Limite inferiore per R(n, m) (R.E. Greenwood e A.M. Gleason, 1955);

R(n, m) ≥ R(n, m – 1) + 2n – 3, per n e m maggiori di 2 (S.A. Burr, Paul Erdös, R.J. Faudree e R.H. Schelp, 1968);

R(n, m + k – 1) ≥ R(n, m) + R(n, k) + n – 3 (Xu Xiaodong e Xie Zheng, 2002);

R(n, m + k – 1) ≥ R(n, m) + R(n, k) + m – 2 (Xu Xiaodong e Xie Zheng, 2002);

R(2n – 1, m) ≥ 4R(n, m – 1) – 3, per n > 4 e m > 1 (Xu Xiaodong, Xie Zheng, G. Exoo e Stanisłav P. Radziszowski, 2004);

Limite superiore per R(n, m) (Miklós Ajtai, János Komlós e Endre Szemerédy, 1980);

Limite superiore per R(n, m), per una costante c (A. Thomason, 1988);

Limite superiore per R(n, m), per due costanti c1 e c2 (V. Röhl);

Limite superiore per R(n, m) (R.L. Graham e V. Röhl);

Limite superiore per R(n, m), per nm e una costante c (A. Thomason, 1988);

Limite superiore per R(n, m), per una costante c che dipende solo da n (Miklós Ajtai, János Komlós e Endre Szemerédi, 1980);

R(3, 4k + 1) ≤ 6R(3, k + 1) (F.R.K. Chung, R. Cleve e P. Dagum, 1993);

Limiti inferiore e superiore per R(3, m), dove c1 e c2 sono costanti e Limiti superiori per c1 e c2 (Miklós Ajtai, János Komlós e Endre Szemerédy, 1980);

Limiti inferiore e superiore per R(n, m), per n fissato e maggiore di 3, dove c1 e c2 sono costanti che dipendono da n (Miklós Ajtai, János Komlós e Endre Szemerédy, 1980).

 

Paul Erdös e G. Szekeres dimostrarono nel 1935 che se esiste Limite cui tende R(n)^(1 / n), il limite è compreso tra sqrt(2) e 4, ma non riuscirono a dimostrare l’esistenza del limite.

 

Nonostante l’impiego delle più raffinate tecniche di analisi combinatoria, e talvolta di potenti elaboratori, la ricerca dei numeri di Ramsey è estremamente difficile e sinora se ne conoscono pochissimi, mentre per alcuni altri si conoscono limiti superiori e inferiori del valore, riportati nella tabella seguente.

n

m

R(n, m)

1

k

1

2

k

k

3

3

6 (R.E. Greenwood e A.M. Gleason, 1955)

3

4

9 (R.E. Greenwood e A.M. Gleason, 1955)

3

5

14 (R.E. Greenwood e A.M. Gleason, 1955)

3

6

18 (G. Kéry, 1964)

3

7

23 (J.G. Kalbfleisch, 1965)

3

8

28 (C. Grinstead e M. Roberts, 1982, Brendan D. McKay e Zang Ke Min, 1992)

3

9

36 (J.G. Kalbfleisch, 1966 e C. Grinstead e M. Roberts, 1982)

3

10

[40 .. 42] (Stanisłav P. Radziszowski e D.L. Kreher, 1988)

3

11

[46 .. 51] (J.G. Kalbfleisch, 1966 e Stanisłav P. Radziszowski e D.L. Kreher, 1988)

3

12

[52 .. 59] (G. Exoo 1998)

3

13

[59 .. 69] (Stanisłav P. Radziszowski e D.L. Kreher, 1988)

3

14

[66 .. 78] (Stanisłav P. Radziszowski e D.L. Kreher, 1988)

3

15

[73 .. 88] (Wang Qingxian e Wang Gongben, 1989)

3

16

[79 .. 135] (Wang Qingxian e Wang Gongben, 1989)

3

17

[92 .. 152] (Wang Qingxian, Wang Gongben e Yan Shuda, 1994)

3

18

[98 .. 170 ] (Wang Qingxian, Wang Gongben e Yan Shuda, 1994)

3

19

[106 .. 189] Wang Qingxian, Wang Gongben e Yan Shuda, 1994)

3

20

[109 .. 209] (Wang Qingxian, Wang Gongben e Yan Shuda, 1994)

3

21

[122 .. 230] (Wang Qingxian, Wang Gongben e Yan Shuda, 1994)

3

22

[125 .. 252] (Wang Qingxian, Wang Gongben e Yan Shuda, 1994)

3

23

[136 .. 275] (Wang Qingxian, Wang Gongben e Yan Shuda, 1994)

3

26

≥ 150 (Luo Haipeng, Su Wenlong e Li Zhengchong, 1999)

3

27

≥ 158 (G. Exoo, 2004)

3

29

≥ 174 (Luo Haipeng, Su Wenlong e Li Zhengchong, 2000)

3

31

≥ 198 (G. Exoo, 2004)

3

32

≥ 212 (Luo Haipeng, Su Wenlong, Zhang Zhengyou e Li Guiqing, 2000)

3

61

≥ 479 (Yu Song Nian, 1996)

3

103

≥ 955 (Yu Song Nian, 1996)

4

4

18 (R.E. Greenwood e A.M. Gleason, 1955)

4

5

25 (Brendan D. McKay e Stanisłav P. Radziszowski, 1993)

4

6

[36 .. 41] (G. Exoo, 1992 e Brendan D. McKay e Stanisłav P. Radziszowski, 1997)

4

7

[49 .. 61] (G. Exoo, 1989)

4

8

[56 .. 84] (G. Exoo, 2004)

4

9

[73 .. 115] (Stanisłav P. Radziszowski e D.L Kreher, 1988)

4

10

[92 .. 149] (J. Mackey, 1994)

4

11

[97 .. 191] (S.A. Burr, 1989)

4

12

[128 .. 238] (T. Spencer, 1994)

4

13

[133 .. 291] (Xu Xiaodong e Xie Zheng, 2002)

4

14

[141 .. 349] (Xu Xiaodong e Xie Zheng, 2002)

4

15

[153 .. 417] (Xu Xiaodong, Xie Zheng e Stanisłav P. Radziszowski, 2004)

4

16

[153 .. 815]

4

17

[182 .. 968] (Luo Haipeng, Su Wenlong e ShenYun-Qiu, 2001)

4

18

[187 .. 1139]

4

19

[198 .. 1329] (Luo Haipeng, Su Wenlong e Li Zhengchong, 2002)

4

20

[230 .. 1539] (Luo Haipeng, Su Wenlong, Zhang Zhengyou e Li Guiqing, 2000)

4

21

[242 .. 1770] (Luo Haipeng, Su Wenlong, Zhang Zhengyou e Li Guiqing, 2000)

4

22

[282 .. 2023] (Luo Haipeng e Su Wenlong, 1998)

5

5

[43 .. 49] (G. Exoo, 1989 e Brendan D. McKay e Stanisłav P. Radziszowski, 1997)

5

6

[58 .. 87] (Walker 1971 e G. Exoo, 1993)

5

7

[80 .. 143] (T. Spencer 1994 e N.J. Calkin, Paul Erdös e C.A: Tovey, 1997)

5

8

[101 .. 216] (T. Spencer 1994)

5

9

[126 .. 316] (J. Mackey, 1994 e G. Exoo, 1998)

5

10

[144 .. 442] (J. Mackey 1994 e G. Exoo, 1998)

5

11

[157 .. 1000] (G. Exoo, 1998 e Xu Xiaodong, Xie Zheng, G. Exoo e Stanisłav P. Radziszowski, 2004)

5

12

[181 .. 1364] (G. Exoo, 1998)

5

13

[205 .. 1819] (G. Exoo, 1998 e Xu Xiaodong, Xie Zheng, G. Exoo e Stanisłav P. Radziszowski, 2004)

5

14

[233 .. 2379] (G. Exoo, 1998 e Xu Xiaodong, Xie Zheng, G. Exoo e Stanisłav P. Radziszowski, 2004)

5

15

[261 .. 3059] (Su Wenlong, 2002 e Xu Xiaodong, Xie Zheng, G. Exoo e Stanisłav P. Radziszowski, 2004)

5

16

[289 .. 3875] (Luo Haipeng, Su Wenlong e ShenYun-Qiu, 2001)

5

17

[313 .. 4844] (G. Exoo, 1998)

5

18

[365 .. 5984]

5

19

[389 .. 7314] (Su Wenlong, 1999)

5

20

[421 .. 8854] (Luo Haipeng, Su Wenlong e ShenYun-Qiu, 2001)

5

21

[433 .. 10625]

5

22

[485 .. 12649] (Luo Haipeng, Su Wenlong, Zhang Zhengyou e Li Guiqing, 2000)

5

23

[509 .. 14949] (Luo Haipeng, Su Wenlong, Zhang Zhengyou e Li Guiqing, 2000)

5

24

[509 .. 17549]

5

25

[509 .. 20474]

5

26

[509 .. 23750]

6

6

[102 .. 165] (J.G. Kalbfleisch, 1965)

6

7

[113 .. 298] (J. Mackey 1994 e G. Exoo, 1998)

6

8

[132 .. 495] (J. Mackey 1994 e G. Exoo, 1998)

6

9

[169 .. 780] (J. Mackey, 1994)

6

10

[179 .. 1171] (J. Mackey 1994 e Xu Xiaodong, Xie Zheng, 2002)

6

11

[253 .. 2002] (Xu Xiaodong, Xie Zheng e Stanisłav P. Radziszowski, 2004)

6

12

[262 .. 4367] (Xu Xiaodong e Xie Zheng, 2002)

6

13

[317 .. 6187] (Xu Xiaodong, Xie Zheng, G. Exoo e Stanisłav P. Radziszowski 2004)

6

14

[317 .. 8567] (Xu Xiaodong, Xie Zheng, G. Exoo e Stanisłav P. Radziszowski 2004)

6

15

[401 .. 11627] (Su Wenlong, 2002)

6

16

[434 .. 15503] (Su Wenlong, Luo Haipeng, Li Guiqing e Li Qiao, 2002)

6

17

[548 .. 20348] (Su Wenlong, Luo Haipeng, Li Guiqing e Li Qiao, 2002)

6

18

[614 .. 26333] (Su Wenlong, Luo Haipeng, Li Guiqing e Li Qiao, 2002)

6

19

[710 .. 33648] (Su Wenlong, Luo Haipeng, Li Guiqing e Li Qiao, 2002)

6

20

[878 .. 42503] (Su Wenlong, Luo Haipeng, Li Guiqing e Li Qiao, 2002, 2002)

6

21

[878 .. 53129]

6

22

[1070 .. 65779] (Su Wenlong, Luo Haipeng, Li Guiqing e Li Qiao, 2002, 2002)

7

7

[205 .. 540] (G. Giraud, 1973 e J.B. Shearer, 1986)

7

8

[217 .. 1031] (Xu Xiaodong e Xie Zheng, 2002)

7

9

[241 .. 1713] (Huang Hi Ru e Ke Min Zhang, 1998)

7

10

[289 .. 2826] (J. Mackey, 1994)

7

11

[405 .. 8007] (Xu Xiaodong, Xie Zheng, G. Exoo e Stanisłav P. Radziszowski 2004)

7

12

[416 .. 12375] (Xu Xiaodong, Xie Zheng, G. Exoo e Stanisłav P. Radziszowski 2004)

7

13

[511 .. 18563] (Xu Xiaodong, Xie Zheng e Stanisłav P. Radziszowski, 2004)

7

14

[511 .. 27131]

7

15

[511 .. 38759]

7

16

[511 .. 54263]

7

17

[673 .. 74612] (Xu Xiaodong e Xie Zheng, 2002)

7

18

[725 .. 100946] (Xu Xiaodong e Xie Zheng, 2002)

7

19

[908 .. 134595] (Su Wenlong, Luo Haipeng, Li Guiqing e Li Qiao, 2002)

7

20

[908 .. 177099]

7

21

[1214 .. 230229] (Su Wenlong, Luo Haipeng, Li Guiqing e Li Qiao, 2002)

8

8

[282 .. 1870] (J.P. Burling e S.W. Reyner, 1972)

8

9

[317 .. 3583] (Xu Xiaodong, Xie Zheng, G. Exoo e Stanisłav P. Radziszowski, 2004)

8

10

[377 .. 6090] (Huang Hi Ru e Ke Min Zhang, 1998)

8

11

[377 .. 19447]

8

12

[377 .. 31823]

8

13

[817 .. 50387] (Xu Xiaodong, Xie Zheng, G. Exoo e Stanisłav P. Radziszowski, 2004)

8

14

[817 .. 77519]

8

15

[861 .. 116279] (Xu Xiaodong e Xie Zheng, 2002)

8

16

[861 .. 170543]

8

17

[925 .. 245156] (Xu Xiaodong e Xie Zheng, 2002)

8

18

[925 .. 346103] (Xu Xiaodong e Xie Zheng, 2002)

8

19

[1054 .. 480699] (Xu Xiaodong, Xie Zheng e Stanisłav P. Radziszowski, 2004)

8

20

[1094 .. 657799] (Su Wenlong, Luo Haipeng, Li Guiqing e Li Qiao, 2002)

8

21

[1617 .. 888029] (Su Wenlong, 2002)

9

9

[565 .. 6588] (J.B. Shearer 1986e Shi Ling Sheng e Ke Min Zhang, 2001)

9

10

[581 .. 12677] (Xu Xiaodong e Xie Zheng, 2002)

9

17

≥ 1411 (Xu Xiaodong, Xie Zheng e Stanisłav P. Radziszowski, 2004)

10

10

[798 .. 23556] (J.B. Shearer, 1986 e Shi Ling Sheng, 2001)

10

15

≥ 1265 (J.B. Shearer, 1986)

11

11

[1597 .. 184755] (J.B. Shearer, 1986 e R. Mathon 1987)

12

12

[1637 .. 705431] (Xu Xiaodong e Xie Zheng, 2002)

13

13

[2557 .. 2704155] (J.B. Shearer, 1986 e R. Mathon 1987)

14

14

[2989 .. 10400599] (J.B. Shearer, 1986 e R. Mathon 1987)

15

15

[5485 .. 40116599] (R. Mathon 1987)

16

16

[5605 .. 155117519] (J.B. Shearer, 1986 e R. Mathon 1987)

17

17

[8917 .. 155117519] (Luo Haipeng, Su Wenlong e Li Zhengchong, 2002)

18

18

[11005 .. 2333606219] (Luo Haipeng, Su Wenlong e Li Zhengchong, 2002)

19

19

[17885 .. 9075135299] (Luo Haipeng, Su Wenlong e Li Zhengchong, 2002)

 

Per dare un’idea della complessità del problema, basti dire che K17 ammette circa 2.46 • 1026 colorazioni differenti con 2 colori e tra queste una sola non contiene un K4, come dimostrarono Evans, Pulham and Sheehan nel 1979, pertanto per dimostrare tramite un’analisi esaustiva che R(4) è almeno 18 bisognerebbe trovare quell’unica eccezione (la dimostrazione fu in realtà ottenuta per altra via).

I risultati, poco numerosi e generalmente sotto forma di un intervallo di valori possibili e la grande varietà di metodi con i quali sono stati ottenuti mostrano che siamo ben lontani da una teoria per il calcolo efficiente, se non semplice, dei numeri di Ramsey. Questo vale a maggior ragione per le varianti più complesse del problema.

 

Il teorema di Ramsey resta valido anche se s’impiegano più colori, ovvero in un grafo completo Kr colorato con m colori, deve per forza trovarsi un sottografo Kn monocromatico, se r è abbastanza grande. Il minimo valore di r si indica con Rm(n).

In questo caso però si sa ben poco su quale sia il minimo numero di nodi: il numero è noto con precisione in un solo caso per più di 2 colori, R3(3) = 17, e in pochi altri conosciamo limiti superiori o inferiori del valore.

Si conoscono anche alcuni limiti generali, come Limiti inferiore e superiore per R3(n, n), per due costanti c e d (Paul Erdös, A. Hajnal, e R. Rado, 1965).

 

La tabella seguente riporta i valori noti.

n

m

Rm(n)

3

2

6

3

3

17 (Greenwood and Gleason 1955)

3

4

[51 .. 62] (S. Folkman 1964 e F.R.K. Chung 1973, Fettes, L.R. Kramer e Stanisłav P. Radziszowski, 2004)

3

5

[162 .. 307] (G. Exoo, 1994)

3

6

[538 .. 1898] (Exoo 1994 e Harold Fredricksen e Melvin M. Sweet, 2000)

3

7

[1682 .. 12861] (Harold Fredricksen e Melvin M. Sweet, 2000)

4

3

[128 .. 236] (R. Hill e R.W. Irwing, 1982)

4

4

≥ 634 (Xu Xiaodong, Xie Zheng, G. Exoo e Stanisłav P. Radziszowski, 2004)

4

5

≥ 3416 (Xu Xiaodong, Xie Zheng, G. Exoo e Stanisłav P. Radziszowski, 2004)

5

3

≥ 415 (Xu Xiaodong, Xie Zheng, G. Exoo e Stanisłav P. Radziszowski, 2004)

5

4

≥ 3049 (Xu Xiaodong, 2004)

5

5

≥ 26912 (Xu Xiaodong, 2004)

6

3

≥ 1070 (R. Mathon, 1987)

6

4

≥ 15202 (Xu Xiaodong, Xie Zheng, G. Exoo e Stanisłav P. Radziszowski, 2004)

7

3

≥ 3214 (Xu Xiaodong, 2004)

7

4

≥ 62017 (Xu Xiaodong, Xie Zheng, G. Exoo e Stanisłav P. Radziszowski, 2004)

8

3

≥ 3214 (Xu Xiaodong e Xie Zheng, 2002)

9

3

≥ 3214 (Xu Xiaodong, Xie Zheng, G. Exoo e Stanisłav P. Radziszowski, 2004)

 

Il teorema resta valido anche se si considerano grafi differenti, ossia in un grafo completo Kr colorato con m colori, deve per forza trovarsi uno tra m sottografi monocromatici specificati Kn1, Kn2, … , Knm, se r è abbastanza grande.

All’aumentare del numero di colori, il problema diviene però rapidamente intrattabile: gli unici valori noti sono quelli di R(3, 3, 3) e R(3, 3, 3, 3).

 

La tabella seguente elenca alcuni risultati noti per 3 colori.

n1

n2

n3

R(n1, n2, n3)

3

3

3

17 (Fan Chung)

3

3

4

[30 .. 31] (J.G. Kalbfleisch, 1966 e K. Piwakowski e Stanisłav P. Radziszowski, 1998)

3

3

5

≥ 45 (G. Exoo, 1987)

3

3

6

≥ 60 (A. Robertson, 2000)

3

3

7

≥ 79 (G. Exoo, 2002)

3

3

8

≥ 98 (Zhang Zhengyou, Su Wenlong e Luo Haipeng 2001)

3

3

9

≥ 110 (Zhang Zhengyou, Su Wenlong, Li Luiqing e Luo Haipeng 1999)

3

3

10

≥ 141

3

3

11

≥ 157

3

3

12

≥ 181

3

3

13

≥ 205

3

3

14

≥ 233

3

4

4

≥ 55 (D.L. Kreher, Li Wei e Stanisłav P. Radziszowski, 1988)

3

4

5

≥ 80 (G. Exoo, 1998)

3

4

6

≥ 99

3

5

5

≥ 123

3

6

6

≥ 303 (Xu Xiaodong, Xie Zheng, G. Exoo e Stanisłav P. Radziszowski, 2004)

3

7

7

≥ 609 (Xu Xiaodong, Xie Zheng, G. Exoo e Stanisłav P. Radziszowski, 2004)

3

9

9

≥ 1689 (Xu Xiaodong, Xie Zheng, G. Exoo e Stanisłav P. Radziszowski, 2004)

 

La tabella seguente elenca alcuni risultati noti per 4 colori.

n1

n2

n3

n4

R(n1, n2, n3, n4)

3

3

3

3

17 (Fan Chung)

3

3

3

4

[93 .. 153] (G. Exoo, 2002 e Xu Xiaodong, Xie Zheng, G. Exoo e Stanisłav P. Radziszowski, 2004)

3

3

3

5

≥ 162 (Xu Xiaodong, Xie Zheng, G. Exoo e Stanisłav P. Radziszowski, 2004)

3

3

3

11

≥ 561 (Xu Xiaodong, Xie Zheng, 2002 e Xu Xiaodong, Xie Zheng, G. Exoo e Stanisłav P. Radziszowski, 2004)

3

3

4

4

≥ 171 (G. Exoo, 2002 e Xu Xiaodong, Xie Zheng, G. Exoo e Stanisłav P. Radziszowski, 2004)

 

Nel 1990 Honghui Wan dimostrò nel caso di n colori, quindi con n volte 3, Limite superiore per un numero di Ramsey con n colori.

 

Un problema interessante legato ai numeri di Ramsey è il numero minimo di triangoli di un solo colore che un grafo completo con n nodi, colorato con due colori, deve necessariamente contenere; A.W. Goodman dimostrò nel 1959 che:

  • se n = 2m è pari, il numero è Numero minimo di triangoli di un solo colore che un grafo completo con n nodi deve contenere, per n = 2m;

  • se n è della forma 4m + 1, il numero è Numero minimo di triangoli di un solo colore che un grafo completo con n nodi deve contenere, per n = 4m + 1;

  • se n è della forma 4m + 3, il numero è Numero minimo di triangoli di un solo colore che un grafo completo con n nodi deve contenere, per n = 4m + 3.

 

Se il numero di triangoli è il minimo possibile, si può fare in modo che siano tutti dello stesso colore se e solo se n è pari o 7, come dimostrò nel 1961 Leopold Sauvé.

 

Un problema per certi versi simile, ma leggermente più facile, è il seguente: supponiamo di attribuire a ogni nodo di un grafo completo Kn fino a un massimo di r colori, in modo che presi comunque m nodi ve ne siano sempre almeno 2 con un colore comune e che presi comunque p nodi non vi sia un colore comune a tutti; in queste condizioni qual è il massimo valore N(r, m, p) di n?

Una possibile interpretazione è: quante persone può contenere al massimo un gruppo se:

  • tra tutte parlano al massimo t lingue;

  • date m persone qualsiasi, almeno 2 parlano una stessa lingua;

  • date p persone qualsiasi, non vi è una lingua comune a tutte.

Anche su questo problema esiste un’abbondante letteratura, ma non si conosce una soluzione completa; tra i risultati più importanti:

  • N(3, 3, 3) = 8;

  • N(1, m, p) = (m – 1)(p – 1);

  • Valore di N(2, m, p)
  • N(r, m, 3) = (m – 1)(r + 1);

  • Valore di N(3, m, 4).

  • Valore di N(2, m, p)

Bibliografia

  • Gardner, Martin;  "Giochi matematici" in Le Scienze, Milano, n. 115, marzo 1978, pag. 108 – 113.
  • Gardner, Martin;  The Colossal Book of Mathematics, New York, W.W. Norton & Company, 2001.
  • Gardner, Martin;  The Colossal Book of Short Puzzles and Problems, New York, W.W. Norton & Co., 2006.
  • Graham, Ronald L.;  Rudiments of Ramsey Theory, The American Mathematical Society, 1981.
  • Higgins, Peter M.;  Divertirsi con la matematica, Bari, Ediz. Dedalo, 1999 -

    trad. di Mathematics for the Curious, Oxford University Press, 1998. Raccolta di fatti e curiosità matematiche di facile e gradevole lettura.

  • Klamkin, Murray S.;  USA Mathematical Olympiads 1972 – 1986, Washington, The Mathematical Association of America, 1988 -

    Raccolta di problemi stimolanti, alla portata di studenti delle medie superiori.

Contattami

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