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

Oberwolfach (problema di)

Problemi  Teoria dei grafi 

Durante le conferenze tenute al Mathematical Research Institute of Oberwolfach (Germania) è usanza per i partecipanti cenare insieme con tavoli rotondi, non tutti della stessa misura, cambiando le assegnazioni dei posti a ogni pasto. Nel 1967 Gerhard Ringel (Kollnbrunn, Austria, 28/10/1919 – Santa Cruz, USA, 24/6/2008) pose il problema di come stabilire una sequenza di assegnazioni dei posti, tale che i tavoli siano sempre pieni e ogni coppia di partecipanti si trovi seduta accanto esattamente una volta.

 

Un’istanza del problema si indica come OP(x, y, z, … ), dove x, y, z, … sono le dimensioni dei tavoli, comunemente indicate in ordine crescente; se alcune dimensioni sono ripetute, si possono indicare come esponenti. Per esempio, OP(35) descrive un’istanza con 5 tavoli da 3 posti.

 

Il problema può essere formulato in termini di teoria dei grafi, rappresentando ogni tavolo come un grafo ciclico, nel quale ogni nodo è connesso da due archi ad altrettanti nodi a formare un anello chiuso, e l’intera assemblea è rappresentata come l’unione dei grafi ciclici. Se il totale dei posti è n, il problema si riduce a scomporre il grafo completo Kn, nel quale ogni nodo è connesso da un arco a ogni altro, come l’unione di copie dell’insieme di grafi ciclici dati.

Una soluzione esiste solo se n è dispari; infatti, a ogni pranzo ciascun partecipante ha due vicini, quindi il numero totale di vicini che avrà avuto alla fine, ossia il numero degli altri partecipanti, sarà pari. Il problema è stato esteso ai valori pari di n, ammettendo che ciascun partecipante ceni accanto a tutti gli altri, tranne uno; in questa forma è spesso presentato come il problema di trovare una sequenza di assegnazioni di posti per n / 2 coppie, tale che alla fine ciascuno si sia trovato esattamente una volta accanto a ogni altro partecipante, tranne il coniuge.

La figura seguente illustra una soluzione del problema OP(3, 4) con 3 copie di ciascun ciclo, indicate con colori differenti.

 

Illustrazione della soluzione di OP(3, 4)

 

 

Oltre un secolo fa Walecki aveva dimostrato che ogni grafo completo può essere scomposto in cicli separati, ma questo basta a garantire che esiste almeno una soluzione per ogni valore di n, non che esista una soluzione se si fissano le lunghezze dei cicli.

 

Le uniche istanze note del problema di Oberwolfach che si sa non essere risolubili sono: OP(32) (A. Kotzig e A. Rosa, 1974), OP(34) (A. Kotzig e A. Rosa, 1974), OP(4, 5), e OP(3, 3, 5). Gli esperti ritengono che tutte le altre istanze siano risolubili, ma sono stati dimostrati tali solo alcuni casi particolari, tra i quali:

  • le istanze OP(xy) con x dispari, tranne OP(32) e OP(34) (Brian Alspach, P.J. Schellenberg, D.R. Stinson e David Wagner, 1986, per y ≠ 2, D.G. Hoffman e P.J. Schellenberg, 1991, per y = 2);

  • le istanze OP(x2y) tranne le solite due, OP(4), OP(3, 2x + 1) per x > 1, OP(4, 2x) per x > 1, OP(2x + 1, 2x + 1, 2x + 2) e OP(x, x, 2 per il massimo intero non inferiore a k / 2 più 2 per c), per k ≥ 3 e c ≥ 0 (Charlotte Huang, Anton Kotzig e Alexander Rosa, 1978);

  • le istanze OP(3, 42);

  • le istanze OP(3x, 4y) per n multiplo di 12, tranne eventualmente i casi n = 24, x = 5, y = 6; n = 24, x = 7, y = 4; n = 24, x = 9, y = 2; n = 48, x = 7, y = 16; n = 48, x = 9, y = 14; n = 48, x = 13, y = 10; n = 48, x = 15, y = 8; n = 48, x = 15, y = 18 e n = 48, x = 17, y = 6 (P. Danziger, G. Quattrocchi e B. Stevens, 2009);

  • le istanze OP(3x, 5y) per n ≡ 15 mod 30, tranne eventualmente n = 15, x = 16, y = 1 e i casi x = (n – 3) / 2, y = 1, per n > 15 (P. Adams, E. Billington, D. Bryant e S. El-Zanati, 2002);

  • le istanze OP(3x, 7y) per n ≡ 21 mod 42, tranne eventualmente i casi n = 21, x = 2, y = 8; n = 21, x = 4, y = 6 e n = 21, x = 6, y = 4 (H. Lei e H. Fu, 2016);

  • le istanze OP(3x, 9y) per n multiplo di 9 e diverso da 18, 36 e 54, tranne eventualmente i casi n non della forma 54k + 27 e x = 1 (D. Kamin, 2011);

  • le istanze OP(32, n – 3) e OP(42, n – 3);

  • le istanze OP(2x + 1, 4y);

  • le istanze OP(2x + 1, (4x)y);

  • le istanze OP(x, nx) per x da 3 a 9;

  • le istanze OP(x, x + 1) per x > 2;

  • le istanze OP(xk, nkx) per x pari e n ≥ 6kx – 3 o n della forma 2x(2k + m) – 3 o 2x(2k + m) – 2 per m < k (A.J.W. Hilton e Matthew Johnson, 2001);

  • le istanze OP(xk, nkx) per x dispari, k dispari e n ≥ 6kx – 3 o k pari e n ≥ 6kx – 1 o n della forma 2x(2k + 2m + 1) – 1 o 2x(2k + 2m + 1), 2x(2k + 2m + 2) – 3 o 2x(2k + 2m + 2) – 2 per m < (k – 1) / 2 o della forma 2x(3k – 1) – 1 o 2x(3k – 1) (A.J.W. Hilton e Matthew Johnson, 2001);

  • le istanze OP(x, y) e OP(2x, y, y) per x e y maggiori di 2 tranne OP(3, 3) e OP(4, 5) (Tommaso Tratta, 2012);

  • le istanze OP(3, 3, 4x + 3);

  • le istanze OP(3, 3, x) per x > 9;

  • le istanze OP(4, 4, x) per x > 1;

  • le istanze OP(3, 4x, 4x) per x > 1;

  • le istanze OP(x, x, x + 1) per x dispari e maggiore di 3;

  • le istanze con n ≡ 10 mod 48 e n / 2 primo (Darryn Bryant e Victor Scharaschkin, 2008);

  • le istanze nelle quali tutti i cicli hanno lunghezza pari (Roland Häggkvist, 1985, per il caso n ≡ 0 mod 4, Darryn Bryant e Peter Danziger, 2011, per il caso n ≡ 0 mod 4);

  • le istanze con n ≤ 16, tranne le eccezioni sopra elencate Charlotte Huang, Anton Kotzig e Alexander Rosa, 1978);

  • le istanze con n ≤ 40, tranne le eccezioni sopra elencate (A. Deza, F. Franek, W. Hua, M. Meszka e Alexander Rosa, 2008);

  • le istanze con n ≤ 60, tranne le eccezioni sopra elencate (Fabio Salassa, Gabriele Dragotto, Tommaso Traetta, Marco Buratti e Federico Della Croce, 2019).

 

Nel 2018 Stefan Glock, Felix Joos, Jaehoon Kim, Daniela Kühn, e Deryk Osthus dimostrarono che data un’istanza OP(x, y, z, … ), per r abbastanza grande OP(xr, yr, zr, … ) è risolubile.

 

Il problema non è equivalente alla congettura di Alspach, dimostrata vera, perché in quest’ultima non è richiesto che ogni grafo ciclico sia usato lo stesso numero di volte degli altri.

 

Una versione apparentemente più complicata del problema, nella quale vi sono n coppie, alle quali vanno attribuiti posti in modo da alternare uomini e donne intorno a ogni tavolo e che ciascuno sia seduto esattamente una volta accanto a ogni persona del sesso opposto, è stata risolta da W.L. Piotrowski nel 1991: una disposizione è sempre possibile se e solo se il numero di coppie è pari, tranne nel caso di 6 coppie e 2 tavoli da 6 posti.

Se il numero di coppie è dispari e si evita di far sedere ogni persona accanto al proprio coniuge, una soluzione è sempre possibile se i tavoli hanno un numero pari di posti e sono tutti uguali (S.H. Holliday, 2003).

Vedi anche

Congettura di Alspach.

Contattami

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