Гипотеза Тойдаса - Toidas conjecture

В комбинаторный математика, Гипотеза Тойды, из-за Шуничи Тойда в 1977 г.^[1] это уточнение опровергнутого Гипотеза Адама с 1967 г.

Заявление

Обе гипотезы касаются циркулянтные графики. Это графики, определенные из положительного целого числа ${\displaystyle n}$ и набор ${\displaystyle S}$ натуральных чисел, вершины которых можно отождествить с числами от 0 до ${\displaystyle n-1}$, и две вершины ${\displaystyle i}$ и ${\displaystyle j}$ связаны ребром, если их разность по модулю ${\displaystyle n}$ принадлежит набору ${\displaystyle S}$. Каждая симметрия циклическая группа сложения по модулю ${\displaystyle n}$приводит к симметрии ${\displaystyle n}$-вершинных циркулянтных графов, и Адам предположил (ошибочно), что это единственные симметрии циркулянтных графов.

Однако известные контрпримеры к гипотезе Адама включают множества ${\displaystyle S}$ в котором некоторые элементы делят нетривиальные делители с ${\displaystyle n}$Гипотеза Тойды гласит, что когда каждый член ${\displaystyle S}$ является относительно простой к ${\displaystyle n}$, то единственные симметрии циркулянтного графа для ${\displaystyle n}$ и ${\displaystyle S}$ являются симметриями, исходящими от основной циклической группы.

Доказательства

Гипотеза была доказана в частном случае, когда п Клин и Пошель в 1978 г.^[2] и Гольфандом, Наджмарком и Пошелем в 1984 г.^[3]

Гипотеза была полностью доказана Музычук, Клин и Пошель в 2001 году с использованием Алгебра Шура,^[4] и одновременно Добсоном и Моррис в 2002 году с помощью классификация конечных простых групп.^[5]

Примечания

1. С. Тойда: «Заметка о гипотезе Адама», Journal of Combinatorial Theory (B), стр. 239–246, октябрь – декабрь 1977 г.
2. Клин, М. и Р. Пошель: проблема Кенига, проблема изоморфизма для циклических графов и метод колец Шура, Алгебраические методы в теории графов, Vol. I, II., Сегед, 1978, стр. 405–434.
3. Гольфанд, Дж. Дж., Н. Л. Наймарк и Р. Пошель: Структура S-колец над Z2m, препринт (1984).
4. Клин, М.Х., М. Музычук и Р. Пошель: Проблема изоморфизма для циркулянтных графов с помощью теории колец Шура, кодов и схем ассоциации, American Math. Общество, 2001.
5. Добсон, Эдвард; Моррис, радость (2002), «Гипотеза Тойды верна», Электронный журнал комбинаторики, 9 (1): R35: 1 – R35: 14, МИСТЕР  1928787