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

Ramsey planari (numeri di)

Matematica combinatoria  Teoria dei grafi 

Un grafo si dice “planare” se può essere disegnato sul piano senza incroci tra gli archi.

L’operazione di suddivisione di un grafo consiste nell’inserire nuovi nodi lungo alcuni archi, dividendo gli stessi in due nuovi archi.

Nel 1930 il matematico polacco Kazimierz Kuratowski (Varsavia, 2/2/1896 – Varsavia, 18/6/1980) dimostrò che un grafo è planare se e solo se non contiene una suddivisione di un grafo completo con 5 nodi K5 o di un grafo bipartito completo K3, 3 ossia di uno dei due grafi mostrati nella figura seguente.

 

Grafo completo K(5) e grafo bipartito completo K(3, 3)

 

 

Nel 1969 K. Walker estese il teorema di Ramsey (v. numeri di Ramsey) ai grafi planari, mostrando che fissati due grafi G1 e G2, per n abbastanza grande ogni grafo planare F di n nodi contiene una copia di G1 oppure il complemento FC di F, ossia ciò che resta di un grafo completo Kn rimuovendo gli archi che costituiscono F, contiene una copia di G2. In pratica è come aggiungere al teorema di Ramsey la condizione che gli archi colorati col primo colore costituiscano un grafo planare.

 

Questo porta a definire una nuova categoria di numeri di Ramsey: il numero di Ramsey planare RP(G1, G2) di due grafi G1 e G2 è il minimo intero n tale che ogni grafo planare F con n nodi contiene una copia di G1 oppure FC contiene una copia di G2.

 

Analogamente a quanto succede per i numeri di Ramsey, se G1 è un sottografo di H1 e G2 è un sottografo di H2, RP(G1, G2) ≤ RP(H1, H2); in particolare se G ha n nodi, RP(G, H) ≤ RP(Kn, H) e RP(H, G) ≤ RP(H, Kn).

Se G1 non è planare, RP(G1, G2) dipende esclusivamente da G2.

Data l’asimmetria della definizione, generalmente RP(G1, G2) ≠ RP(G2, G1), anche se G1 e G2 sono grafi della stessa categoria o addirittura completi.

 

Anche per i numeri di Ramsey planari vi è una vasta letteratura, ma manca una teoria generale che permetta di trovarli facilmente per una qualsiasi coppia di grafi. Il problema sembra però più trattabile del problema relativo ai numeri di Ramsey ed esistono soluzioni per alcune categorie di grafi. In particolare è stato risolto per alcune coppie di categorie, tra le quali (per la nomenclatura dei grafi v. numeri di Ramsey):

  • RP(Cn, Cm) (Izolda Gorgol e Andrzej Ruciński);

  • RP(Cn, Km), per n ≠ 4 (Andrzej Dudek e Andrzej Ruciński, 2008);

  • RP(Kn, Cm) (Andrzej Dudek e Andrzej Ruciński, 2008);

  • RP(Kn, Km) (K. Walker, 1969 e R. Steinberg e C.A. Tovey, 1993);

  • RP(Kn, Km – e), per n > 3 (Andrzej Dudek e Andrzej Ruciński, 2008);

  • RP(Kn – e, Cm) (Andrzej Dudek e Andrzej Ruciński, 2008);

  • RP(Kn – e, Km), per n ≠ 4 (Andrzej Dudek e Andrzej Ruciński, 2008);

  • RP(Kn – e, Km – e), per n ≠ 4 (Andrzej Dudek e Andrzej Ruciński, 2008).

 

La tabella seguente riporta alcuni dei risultati noti.

G1

G2

RP(G1, G2)

C3

C3

6 (Izolda Gorgol e Andrzej Ruciński)

C3

C4

7 (Izolda Gorgol e Andrzej Ruciński)

C3

Cn

n + 2, per n ≥ 5 (Izolda Gorgol e Andrzej Ruciński)

C3

Kn

3n – 3, per n ≥ 3 (Andrzej Dudek e Andrzej Ruciński, 2008)

C3

K3 – e

5 (Andrzej Dudek e Andrzej Ruciński, 2008)

C3

K4 – e

7 (Andrzej Dudek e Andrzej Ruciński, 2008)

C3

K5 – e

9 (Andrzej Dudek e Andrzej Ruciński, 2008)

C3

K6 – e

12 (Andrzej Dudek e Andrzej Ruciński, 2008)

C3

K7 – e

15 (Andrzej Dudek e Andrzej Ruciński, 2008)

C3

Kn – e

3n – 6, per n ≥ 8 (Andrzej Dudek e Andrzej Ruciński, 2008)

C3

W3

9 (Guofei Zhou, Yaojun Chen, Zhengke Miao e Shariefuddin Pirzada, 2012)

C3

W4

9 (Guofei Zhou, Yaojun Chen, Zhengke Miao e Shariefuddin Pirzada, 2012)

C3

W5

10 (Guofei Zhou, Yaojun Chen, Zhengke Miao e Shariefuddin Pirzada, 2012)

C3

W6

11 (Guofei Zhou, Yaojun Chen, Zhengke Miao e Shariefuddin Pirzada, 2012)

C3

Wn

3n + 4, per n ≥ 7 (Guofei Zhou, Yaojun Chen, Zhengke Miao e Shariefuddin Pirzada, 2012)

C4

C3

7 (Izolda Gorgol e Andrzej Ruciński)

C4

C4

6 (Izolda Gorgol e Andrzej Ruciński)

C4

C5

7 (Izolda Gorgol e Andrzej Ruciński)

C4

Cn

n + 1, per n ≥ 6 (Izolda Gorgol e Andrzej Ruciński)

C4

K3

7 (Andrzej Dudek e Andrzej Ruciński, 2008)

C4

K4

10 (Andrzej Dudek e Andrzej Ruciński, 2008)

C4

K5

13 (Andrzej Dudek e Andrzej Ruciński, 2008)

C4

K6

17 (Andrzej Dudek e Andrzej Ruciński, 2008)

C4

Kn

Limiti inferiore e superiore per RP(C(4), K(n)), per n ≥ 7 (Andrzej Dudek e Andrzej Ruciński, 2008)

C4

K4 – e

4 (Andrzej Dudek e Andrzej Ruciński, 2008)

C4

K4 – e

7 (Andrzej Dudek e Andrzej Ruciński, 2008)

C4

K5 – e

11 (Andrzej Dudek e Andrzej Ruciński, 2008)

C4

K6 – e

14 (Andrzej Dudek e Andrzej Ruciński, 2008)

C4

Kn – e

Limite inferiore per RP(C(4), K(n) – e), per n ≥ 8 (Andrzej Dudek e Andrzej Ruciński, 2008)

C4

Wn

10, per n = 3;

9, per n = 6;

n + 4, per n da 7 a 25 o uguale a 27, 28, 29, 30, 31, 33, 34, 36, 37 o 39;

n + 5, per n ≥ 40 o uguale a 4, 5, 26, 32, 35 o 38.

(Guofei Zhou, Yaojun Chen, Zhengke Miao e Shariefuddin Pirzada, 2012)

C5

C4

7 (Izolda Gorgol e Andrzej Ruciński)

C5

C6

8 (Izolda Gorgol e Andrzej Ruciński)

C5

Cn

n + 2, per n ≥ 7 (Izolda Gorgol e Andrzej Ruciński)

C5

K5 – e

5 (Andrzej Dudek e Andrzej Ruciński, 2008)

C5

K4 – e

9 (Andrzej Dudek e Andrzej Ruciński, 2008)

C5

K5 – e

13 (Andrzej Dudek e Andrzej Ruciński, 2008)

C5

K6 – e

17 (Andrzej Dudek e Andrzej Ruciński, 2008)

C3

Kn – e

4n – 7, per n ≥ 7 (Andrzej Dudek e Andrzej Ruciński, 2008)

C6

C4

7 (Izolda Gorgol e Andrzej Ruciński)

C6

C6

8 (Izolda Gorgol e Andrzej Ruciński)

C6

K3 – e

6 (Andrzej Dudek e Andrzej Ruciński, 2008)

Cn

C3

9, per n ≥ 5 (Izolda Gorgol e Andrzej Ruciński)

Cn

C4

8, per n ≥ 7 (Izolda Gorgol e Andrzej Ruciński)

Cn

C5

9, per n ≥ 5 (Izolda Gorgol e Andrzej Ruciński)

Cn

C6

9, per n ≥ 5 (Izolda Gorgol e Andrzej Ruciński)

Cn

Cm

m + 2, per n ≥ 5 e m ≥ 7 (Izolda Gorgol e Andrzej Ruciński)

Cn

Km

4m – 3, per n ≥ 5 (Izolda Gorgol e Andrzej Ruciński)

Cn

K3 – e

7, per n ≥ 7 (Andrzej Dudek e Andrzej Ruciński, 2008)

Cn

Km – e

4m – 6, per n ≥ 6 e m ≥ 4 (Andrzej Dudek e Andrzej Ruciński, 2008)

G

C3

9, se G è un grafo non contenuto in 2 copie di K4 (Andrzej Dudek e Andrzej Ruciński, 2008)

G

C4

≤ 8 (Andrzej Dudek e Andrzej Ruciński, 2008)

G

C5

9, se G è un grafo non contenuto in 2 copie di K4 (Andrzej Dudek e Andrzej Ruciński, 2008)

G

C7

9, se G è un grafo non contenuto in 2 copie di K4 (Andrzej Dudek e Andrzej Ruciński, 2008)

G

Cn

≤ 9, per n = 3, 5 e 6 (Andrzej Dudek e Andrzej Ruciński, 2008)

G

Cn

n + 2, per n ≥ 7 (Andrzej Dudek e Andrzej Ruciński, 2008)

G

Cn

n + 2, se G è un grafo non contenuto in 2 copie di K2, n – 1, per n ≥ 7 (Andrzej Dudek e Andrzej Ruciński, 2008)

G

Kn

4n – 3, se G è un grafo connesso con almeno 5 vertici, per n > 1 (Andrzej Dudek e Andrzej Ruciński, 2008)

K3

C3

6 (Andrzej Dudek e Andrzej Ruciński, 2008)

K3

C4

7 (Andrzej Dudek e Andrzej Ruciński, 2008)

K3

Cn

n + 2, per n ≥ 5 (Andrzej Dudek e Andrzej Ruciński, 2008)

K3

Kn

3n – 3, per n ≥ 3 (K. Walker, 1969)

K3

K3 – e

3 (Andrzej Dudek e Andrzej Ruciński, 2008)

K3

K4 – e

7 (Andrzej Dudek e Andrzej Ruciński, 2008)

K3

K5 – e

9 (Andrzej Dudek e Andrzej Ruciński, 2008)

K3

K6 – e

12 (Andrzej Dudek e Andrzej Ruciński, 2008)

K3

K7 – e

15 (Andrzej Dudek e Andrzej Ruciński, 2008)

K3

Kn – e

≥ 3n – 6, per n ≥ 8 (Andrzej Dudek e Andrzej Ruciński, 2008)

K4

C5

8 (Andrzej Dudek e Andrzej Ruciński, 2008)

Kn

C3

9, per n ≥ 4 (Andrzej Dudek e Andrzej Ruciński, 2008)

Kn

C4

8, per n ≥ 4 (Andrzej Dudek e Andrzej Ruciński, 2008)

Kn

C5

9, per n ≥ 5 (Andrzej Dudek e Andrzej Ruciński, 2008)

Kn

C6

9, per n ≥ 4 (Andrzej Dudek e Andrzej Ruciński, 2008)

Kn

Cm

m + 2, per m ≥ 7 (Andrzej Dudek e Andrzej Ruciński, 2008)

Kn

Km

4m – 3, per n ≥ 4 (R. Steinberg e C.A. Tovey, 1993)

Kn

Km – e

4m – 5, per n ≥ 4 (Andrzej Dudek e Andrzej Ruciński, 2008)

K3 – e

C3

5 (Andrzej Dudek e Andrzej Ruciński, 2008)

K3 – e

Cn

n, per n ≥ 4 (Andrzej Dudek e Andrzej Ruciński, 2008)

K4 – e

C3

7 (Andrzej Dudek e Andrzej Ruciński, 2008)

K4 – e

C4

7 (Andrzej Dudek e Andrzej Ruciński, 2008)

K4 – e

Cn

n + 2, per n ≥ 5 (Andrzej Dudek e Andrzej Ruciński, 2008)

K3 – e

Kn

2n – 1, per n ≥ 3 (Andrzej Dudek e Andrzej Ruciński, 2008)

K3 – e

Kn – e

2n – 3, per n ≥ 3 (Andrzej Dudek e Andrzej Ruciński, 2008)

K4 – e

K3

7 (Andrzej Dudek e Andrzej Ruciński, 2008)

K4 – e

K4

10 (Andrzej Dudek e Andrzej Ruciński, 2008)

K4 – e

K5

14 (Andrzej Dudek e Andrzej Ruciński, 2008)

K4 – e

K6

17 (Yongqi Sun, Yali Wu, Rui Zhang, Yuansheng Yang, 2013)

K4 – e

Kn

Limite inferiore per RP(K(4) – e, K(n)) (Yongqi Sun, Yali Wu, Rui Zhang, Yuansheng Yang, 2013)

K4 – e

K4 – e

5 (Andrzej Dudek e Andrzej Ruciński, 2008)

K4 – e

K4 – e

9 (Andrzej Dudek e Andrzej Ruciński, 2008)

K4 – e

K5 – e

13 (Andrzej Dudek e Andrzej Ruciński, 2008)

Kn – e

C3

9, per n ≥ 5 (Andrzej Dudek e Andrzej Ruciński, 2008)

Kn – e

C4

8, per n ≥ 5 (Andrzej Dudek e Andrzej Ruciński, 2008)

Kn – e

C5

9, per n ≥ 5 (Andrzej Dudek e Andrzej Ruciński, 2008)

Kn – e

C6

9, per n ≥ 5 (Andrzej Dudek e Andrzej Ruciński, 2008)

Kn – e

Cm

m + 2, per n ≥ 4 e m ≥ 7 (Andrzej Dudek e Andrzej Ruciński, 2008)

Kn – e

Km

4m – 3, per n ≥ 5 (Andrzej Dudek e Andrzej Ruciński, 2008)

Kn – e

Km – e

4m – 5, per n ≥ 5 (Andrzej Dudek e Andrzej Ruciński, 2008)

 

Nel 2008 Andrzej Dudek e Andrzej Ruciński avanzarono alcune congetture sui numeri di Ramsey planari:

  • RP(C3, K3 – e) = RP(K3, K3 – e) = 3n – 6, per n ≥ 5 (dimostrata per n uguale a 5, 6 e 7);

  • RP(C5, K3 – e) = 4n – 7, per n ≥ 3 (dimostrata per n uguale a 3, 4, 5 e 6);

  • RP(Cm, K3 – e) = 4n – 6, per n ≥ 4 e m ≥ 6 (dimostrata per n uguale a 3, 4, 5 e 6).

Vedi anche

Numeri di Ramsey.

Bibliografia

  • Dudek, Andrzej ;  Ruciński, Andrzej;  "Planar Ramsey Numbers for Small Graphs" in 36th South-eastern International Conference on Combinatorics, Graph Theory, and Computing, Utilitas Mathematica Publishing Inc., Congressus Numerantium, n. 176, 2005.
  • Gorgol, Izolda;  Ruciński, Andrzej;  "Planar Ramsey Numbers for Cycles" in Discrete Mathematics, Vol. 308, n. 19, 6 Ottobre 2008, pag. 4389 – 4395.

Contattami

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