Бесконечно много контрпримеров к гипотезе Нэша-Вильямса о гамильтоничности?
Вопрос от 2013 года дает один контрпример к гипотезе Нэша-Вильямса о гамильтоничности плотных орграфов.
Позже мы нашли десятки контрпримеров на более чем 30 вершинах и полагаем, что контрпримеров бесконечно много.
Определить $K_{x_1,x_2,...x_n}$ к полному многостороннему орграфу с разбиениями $x_i$и каждое ребро ориентировано в обоих направлениях. Позволять$L=\max x_i$.
Гипотеза 1: как $n,L$ варьируются, существует бесконечно много контрпримеров
Q1 Дает ли это бесконечно много контрпримеров?
код sagemath для $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 вершинах возьмем $x_i=(1, 1, 1, 2, 2, 8)$.
Добавлено Предлагаемые контрпримеры неверны и явились результатом ошибки программы.
Ответы
Эти примеры представляют собой симметричные орграфы, то есть графы. Для графов гипотеза Нэша-Вильямса просто превращается в теорему Чватала (если$G$ это график на $n\geq 3$ вершины с последовательностью степеней $d_1\leq d_2\leq \dots\leq d_n$ и для всех $1\leq i<n/2$, $d_i\geq i+1$ или же $d_{n-i}\geq n-i$, тогда $G$имеет гамильтонов цикл). Другими словами, эти примеры не могут быть контрпримерами к гипотезе Нэша-Вильямса.
Конечно, в этих примерах нет гамильтонова цикла, поскольку существует независимое множество больше, чем $n/2$, но условие Нэша-Вильямса не выполняется. Посмотрите на пример$K_{1,1,1,1,5}$например; обе последовательности степеней$[4,4,4,4,4,8,8,8,8]$, но $d_4=4$ и $d_{9-4}=d_5=4$.