Nash-Williams'ın Hamiltonisite hakkındaki varsayımına sonsuz sayıda karşı örnek var mı?

Question

2013'ün sorusu, Nash-Williams'ın yoğun digrafların engebeliğiyle ilgili varsayımına bir karşı örnek veriyor.

Daha sonra, 30'dan fazla köşede onlarca karşı örnek bulduk ve sonsuz sayıda karşı örnek olduğuna inanıyoruz.

Tanımlamak $K_{x_1,x_2,...x_n}$ bölümlere sahip tam çok parçalı digraph'a $x_i$ve her kenar her iki yöne yöneliktir. İzin Vermek$L=\max x_i$.

Varsayım 1: as $n,L$ değişir, sonsuz sayıda karşı örnek vardır

S1 Bu sonsuz sayıda karşı örnek veriyor mu?

sagemath kodu $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)]

15 köşede karşı örnek için şunu alın $x_i=(1, 1, 1, 2, 2, 8)$.

Eklendi Önerilen karşı örnekler yanlış ve bir program hatasının sonucuydu.

Answer 1

Bu örnekler simetrik digraflardır, yani grafiklerdir. Grafikler için Nash-Williams varsayımı, Chvatal teoremi haline gelir (If$G$ üzerinde bir grafik $n\geq 3$ derece sıralı köşeler $d_1\leq d_2\leq \dots\leq d_n$ ve herkes için $1\leq i<n/2$, $d_i\geq i+1$ veya $d_{n-i}\geq n-i$, sonra $G$Hamilton döngüsüne sahiptir). Başka bir deyişle, bu örnekler Nash-Williams varsayımına karşı örnek olamaz.

Elbette bu örneklerde Hamilton döngüsü yoktur, çünkü daha büyük bağımsız bir küme vardır. $n/2$, ancak Nash-Williams koşulu karşılanmadı. Örneğe bakınız$K_{1,1,1,1,5}$Örneğin; her iki derece dizisi$[4,4,4,4,4,8,8,8,8]$, fakat $d_4=4$ ve $d_{9-4}=d_5=4$.