Гипотеза Роты
Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

Гипотеза об исключенных минорах Роты - одна из многих гипотез, сделанных математиком Джан-Карло Рота . Некоторые члены сообщества структурной комбинаторики считают это важной проблемой. В 1971 году Рота предположил, что для каждого конечного поля семейство матроидов, которое может быть представлено над этим полем, имеет только конечное число исключенных миноров . [1] Доказательство гипотезы было объявлено Гиленом, Джерардсом и Уиттлом. [2]

Формулировка гипотезы

Если - набор точек в векторном пространстве, определенный над полем , то линейно независимые подмножества образуют независимые множества матроида ; называется представлением любого матроида, изоморфного . Не каждый матроид имеет представление над каждым полем, например, плоскость Фано представима только над полями характеристики два. Другие матроиды вообще не могут быть представлены без полей. Матроиды, которые можно представить в определенном поле, образуют надлежащий подкласс всех матроидов.

Минор матроида еще один матроидом формируется последовательность двух операций: удаления и сокращения. В случае точек из векторного пространства удаление точки - это просто удаление этой точки из ; сжатие - это двойная операция, при которой точка удаляется, а оставшиеся точки проецируются на гиперплоскость, не содержащую удаленных точек. Отсюда следует, что если матроид представим над полем, то все его миноры тоже. Матроид, который не может быть представлен поверх и является второстепенным- минимальным с этим свойством, называется «исключенным второстепенным»; матроид представим над, если и только если он не содержит одного из запрещенных миноров.

Для представимости над действительными числами существует бесконечно много запрещенных миноров. [3] Гипотеза Роты состоит в том, что для каждого конечного поля существует только конечное число запрещенных миноров.

Частичные результаты

У. Т. Тутте доказал, что бинарные матроиды (матроиды, представимые над полем из двух элементов) имеют единственный запрещенный минор, однородный матроид (геометрически линия с четырьмя точками на ней). [4] [5]

Матроид представим над тернарным полем GF (3) тогда и только тогда, когда он не имеет одного или нескольких из следующих четырех матроидов в качестве миноров: пятиконечной прямой , ее двойственного матроида (пять точек в общем положении в трех измерениях) , плоскость Фано или двойственная к плоскости Фано. Таким образом, гипотеза Роты верна и в этом случае. [6] [7] Как следствие этого результата и запрещенной минорной характеристики, данной Тутте (1958) для обычных матроидов (матроидов, которые могут быть представлены над всеми полями), следует, что матроид является правильным тогда и только тогда, когда он как двоичные, так и троичные. [7]

Для матроидов, представимых над GF (4), существует семь запрещенных миноров. [8] Это:

  • Шеститочечная линия .
  • Двойная к шеститочечной линии, шесть точек в общем положении в четырех измерениях.
  • Самодуальный шеститочечный матроид третьего ранга с одной трехточечной линией.
  • Не-фано-матроид, образованный семью точками в вершинах, серединами ребер и центроидом равностороннего треугольника на евклидовой плоскости . Эта конфигурация является одним из двух известных наборов плоских точек с менее чем двухточечными линиями . [9]
  • Двойник матроида нефано.
  • Восьмиконечный матроид квадратной антипризмы .
  • Матроид, полученный расслаблением уникальной пары непересекающихся контуров-гиперплоскостей квадратной антипризмы.

Этот результат получил премию Фулкерсона 2003 года для авторов Джима Гилена , AMH Джерардса и А. Капура. [10]

Для GF (5) известно несколько запрещенных миноров до 12 элементов [11], но неизвестно, является ли список полным.

Сообщенное доказательство

Джефф Уиттл объявил во время визита в Великобританию в 2013 году, что он, Джим Гилен и Берт Джерардс решили гипотезу Роты. Сотрудничество включало интенсивные посещения, когда исследователи каждый день целый день сидели в комнате перед доской. [12] Им потребуются годы, чтобы полностью описать свое исследование и опубликовать его. [13] [14] Схема доказательства появилась в Уведомлениях AMS. [15]

Смотрите также

  • Гипотеза Роты о базисе , другая гипотеза Роты о линейной алгебре и матроидах

использованная литература

  1. ^ Рота, Джан-Карло (1971), «Комбинаторная теория, старая и новая», Actes du Congrès International des Mathématiciens (Ницца, 1970), Том 3 , Париж: Готье-Виллар, стр. 229–233, MR  0505646.
  2. ^ «Решение гипотезы Роты» (PDF) , Уведомления Американского математического общества : 736–743, 17 августа 2014 г.
  3. ^ Vámos, P. (1978), "Отсутствующая аксиома теории матроидов теряется навсегда", журнал Лондонского математического общества , вторая серия, 18 (3): 403-408, DOI : 10.1112 / jlms / s2-18.3. 403 , Руководство MR 0518224 .
  4. ^ Tutte, WT (1958), "Гомотопия теорема для матроидов I, II.", Труды Американского математического общества , 88 : 144-174, DOI : 10,2307 / 1993244 , MR 0101526 .
  5. ^ Tutte, WT (1965), "Лекция по матроидам" , Журнал исследований Национального бюро стандартов , 6 : 1-47, DOI : 10,6028 / jres.069b.001 , MR 0179781 . См., В частности, раздел 5.3, «Характеристика бинарных матроидов», стр.17.
  6. ^ Биксби, Роберт Е. (1979), "О характеризации Рейда тройных матроидов", Журнал комбинаторной теории , серии B, 26 (2): 174-204, DOI : 10,1016 / 0095-8956 (79) 90056-X , Руководство по ремонту 0532587 . Биксби приписывает эту характеристику тройных матроидов Ральфу Рейду.
  7. ^ Б Seymour, PD (1979), "матроида представление над GF (3)", Журнал комбинаторной теории , серии B, 26 (2): 159-173, DOI : 10,1016 / 0095-8956 (79) 90055-8 , Руководство по ремонту 0532586 .
  8. ^ Geelen, JF ; Джерардс, AMH; Капур, A. (2000), "Исключенные несовершеннолетних для GF (4) -представимых матроиды" (PDF) , Журнал комбинаторной теории , серии B, 79 (2): 247-299, DOI : 10,1006 / jctb.2000.1963 , MR 1769191 , архивировано из оригинала (PDF) 24 сентября 2010 г.   .
  9. ^ Келли, LM ; Мозер, WOJ (1958), "О числе обычных линий, определяемых n точками" , Can. J. Math. , 10 : 210-219, DOI : 10,4153 / CJM-1958-024-6.
  10. ^ Ссылка на Премию Фулкерсона 2003 г. , получено 18 августа 2012 г.
  11. ^ Беттен, А .; Kingan, RJ; Kingan, SR (2007), «Заметка о матроидах, представимых в GF (5)» (PDF) , MATCH Communications in Mathematical and Computer Chemistry , 58 (2): 511–521, MR 2357372  [ постоянная мертвая ссылка ] .
  12. ^ Geelen, Gerards и Виттл объявить доказательство гипотезы Роты университета Ватерлоо, 28 августа 2013
  13. ^ Рота Гипотеза: Исследователь решает 40-летней математику проблема PHYSorg, 15 августа 2013.
  14. ^ КРИ исследователь доказывает известную Роты гипотезу в архив 2013-10-26 в Wayback Machine КРИ, 22 августа 2013.
  15. ^ «Решение гипотезы Роты» (PDF) , Уведомления Американского математического общества : 736–743, 17 августа 2014 г.
Источник « https://en.wikipedia.org/w/index.php?title=Rota%27s_conjecture&oldid=1032122786 »
Contribute a better translation