Une infinité de contre-exemples à la conjecture de Nash-Williams sur la hamiltonicité?

Aug 15 2020

Une question de 2013 donne un contre-exemple à la conjecture de Nash-Williams sur l'hamiltonicité des digraphes denses.

Plus tard, nous avons trouvé des dizaines de contre-exemples sur plus de 30 sommets et pensons qu'il existe une infinité de contre-exemples.

Définir $K_{x_1,x_2,...x_n}$ au digraphe multipartite complet avec partitions $x_i$et chaque arête est orientée dans les deux sens. Laisser$L=\max x_i$.

Conjecture 1: comme $n,L$ varient, il existe une infinité de contre-exemples

Q1 Cela donne-t-il une infinité de contre-exemples?

code sagemath pour $K_{1,1,2,5}$:

G1=graphs.CompleteMultipartiteGraph((1,1,2,5)).to_directed()
sage: print G1.edges(False)
[(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (1, 0), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (2, 0), (2, 1), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (3, 0), (3, 1), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8), (4, 0), (4, 1), (4, 2), (4, 3), (5, 0), (5, 1), (5, 2), (5, 3), (6, 0), (6, 1), (6, 2), (6, 3), (7, 0), (7, 1), (7, 2), (7, 3), (8, 0), (8, 1), (8, 2), (8, 3)]

Pour un contre-exemple sur 15 sommets, prenez $x_i=(1, 1, 1, 2, 2, 8)$.

Ajouté Les contre-exemples suggérés sont incorrects et résultent d'un bogue du programme.

Réponses

4 LouisD Aug 16 2020 at 05:54

Ces exemples sont des digraphes symétriques, c'est-à-dire des graphes. Pour les graphes, la conjecture de Nash-Williams devient simplement le théorème de Chvatal (Si$G$ est un graphique sur $n\geq 3$ sommets avec séquence de degrés $d_1\leq d_2\leq \dots\leq d_n$ et pour tous $1\leq i<n/2$, $d_i\geq i+1$ ou $d_{n-i}\geq n-i$, puis $G$a un cycle hamiltonien). En d'autres termes, ces exemples ne peuvent pas être des contre-exemples à la conjecture de Nash-Williams.

Bien sûr, il n'y a pas de cycle hamiltonien dans ces exemples car il existe un ensemble indépendant plus grand que $n/2$, mais la condition de Nash-Williams n'est pas remplie. Regardez l'exemple$K_{1,1,1,1,5}$par exemple; les deux séquences de degrés sont$[4,4,4,4,4,8,8,8,8]$, mais $d_4=4$ et $d_{9-4}=d_5=4$.