Infinitamente muitos contra-exemplos à conjectura de Nash-Williams sobre a hamiltonicidade?

Question

A pergunta de 2013 oferece um contra-exemplo à conjectura de Nash-Williams sobre a hamiltonicidade de dígrafos densos.

Mais tarde, encontramos dezenas de contra-exemplos em mais de 30 vértices e acreditamos que existem infinitos contra-exemplos.

Definir $K_{x_1,x_2,...x_n}$ ao dígrafo multipartido completo com partições $x_i$e cada aresta é orientada em ambas as direções. Deixei$L=\max x_i$.

Conjectura 1: como $n,L$ variam, há infinitos contra-exemplos

Q1 Isso dá infinitamente muitos contra-exemplos?

código sagemath para $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)]

Para um contra-exemplo em 15 vértices, pegue $x_i=(1, 1, 1, 2, 2, 8)$.

Adicionado Os contra-exemplos sugeridos estão errados e foram o resultado de um bug do programa.

Answer 1

Esses exemplos são dígrafos simétricos, ou seja, gráficos. Para gráficos, a conjectura de Nash-Williams torna-se apenas o teorema de Chvatal (Se$G$ é um gráfico em $n\geq 3$ vértices com sequência de graus $d_1\leq d_2\leq \dots\leq d_n$ e para todos $1\leq i<n/2$, $d_i\geq i+1$ ou $d_{n-i}\geq n-i$, então $G$tem um ciclo hamiltoniano). Em outras palavras, esses exemplos não podem ser contra-exemplos à conjectura de Nash-Williams.

Claro que não há ciclo hamiltoniano nestes exemplos, uma vez que existe um conjunto independente maior do que $n/2$, mas a condição de Nash-Williams não foi atendida. Olhe para o exemplo$K_{1,1,1,1,5}$por exemplo; ambas as sequências de graus são$[4,4,4,4,4,8,8,8,8]$, mas $d_4=4$ e $d_{9-4}=d_5=4$.