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

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

Заявление

Обе гипотезы касаются циркулянтные графики. Это графики, определенные из положительного целого числа и набор натуральных чисел, вершины которых можно отождествить с числами от 0 до , и две вершины и связаны ребром, если их разность по модулю принадлежит набору . Каждая симметрия циклическая группа сложения по модулю приводит к симметрии -вершинных циркулянтных графов, и Адам предположил (ошибочно), что это единственные симметрии циркулянтных графов.

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

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

Гипотеза была доказана в частном случае, когда п Клин и Пошель в 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