Гипотеза Роты

Гипотеза о запрещенных минорах матроидов

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

Формулировка предположения

Если — множество точек в векторном пространстве , определенное над полем , то линейно независимые подмножества образуют независимые множества матроида ; называется представлением любого матроида, изоморфного . Не каждый матроид имеет представление над каждым полем, например, плоскость Фано представима только над полями характеристики два. Другие матроиды не представимы ни над какими полями. Матроиды, представимые над определенным полем, образуют собственный подкласс всех матроидов. ${\displaystyle S}$ ${\displaystyle F}$ ${\displaystyle S}$ ${\displaystyle M}$ ${\displaystyle S}$ ${\displaystyle M}$

Минор матроида — это другой матроид , образованный последовательностью двух операций: удаление и стягивание. В случае точек из векторного пространства удаление точки — это просто удаление этой точки из ; стягивание — это двойственная операция, в которой точка удаляется, а оставшиеся точки проецируются на гиперплоскость, не содержащую удаленных точек. Из этого следует, что если матроид представим над полем, то и все его миноры также представимы. Матроид, который не представим над , и является минорно- минимальным с этим свойством, называется «исключенным минором»; матроид представим над тогда и только тогда, когда он не содержит ни одного из запрещенных миноров. ${\displaystyle S}$ ${\displaystyle F}$ ${\displaystyle M}$ ${\displaystyle F}$

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

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

В. Т. Тутт доказал, что бинарные матроиды (матроиды, представимые над полем из двух элементов) имеют единственный запрещенный минор — равномерный матроид (геометрически — прямую с четырьмя точками на ней). ^{[4] [5]} ${\displaystyle U{}_{4}^{2}}$

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

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

• Шестиочковая линия . ${\displaystyle U{}_{6}^{2}}$
• Двойственная к шеститочечной линии линия, шесть точек в общем положении в четырех измерениях. ${\displaystyle U{}_{6}^{4}}$
• Самодвойственный шеститочечный матроид ранга три с одной трехточечной линией.
• Не-Фано матроид, образованный семью точками в вершинах, серединами ребер и центроидом равностороннего треугольника в евклидовой плоскости . Эта конфигурация является одним из двух известных наборов плоских точек с линиями, состоящими менее чем из двух точек . ^[9] ${\displaystyle n/2}$
• Двойственный матроиду не-Фано.
• Восьмиточечный матроид квадратной антипризмы .
• Матроид, полученный путем релаксации единственной пары непересекающихся контуров-гиперплоскостей квадратной антипризмы.

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

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

Представленное доказательство

Джефф Уиттл объявил во время визита в Великобританию в 2013 году, что он, Джим Джилен и Берт Джерардс решили гипотезу Роты. Сотрудничество включало интенсивные визиты, когда исследователи сидели в комнате вместе, целый день каждый день, перед доской. ^[12] Им потребовались годы, чтобы полностью описать свое исследование и опубликовать его. ^{[13] [14]} План доказательства появился в 2014 году в Notices of the American Mathematical Society . ^[15] Впоследствии появилась только одна статья тех же авторов, связанная с этой гипотезой. ^[16]

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

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

Ссылки

1. Рота, Джан-Карло (1971), «Комбинаторная теория, старая и новая», Actes du Congrès International des Mathématiciens (Ницца, 1970), Том 3 , Париж: Готье-Вилларс, стр. 229–233, MR  0505646.
2. «Решение гипотезы Рота» (PDF) , Notices of the American Mathematical Society : 736–743, 17 августа 2014 г.
3. Вамос, П. (1978), «Отсутствующая аксиома теории матроидов утеряна навсегда», Журнал Лондонского математического общества , Вторая серия, 18 (3): 403–408, doi :10.1112/jlms/s2-18.3.403, MR  0518224.
4. Tutte, WT (1958), «Гомотопическая теорема для матроидов. I, II», Transactions of the American Mathematical Society , 88 (1): 144–174, doi :10.2307/1993244, JSTOR  1993244, MR  0101526.
5. Tutte, WT (1965), «Лекции о матроидах», Журнал исследований Национального бюро стандартов , 69B : 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 , MR  0532587. Биксби приписывает эту характеристику тернарных матроидов Ральфу Риду.
7. Seymour, PD (1979), «Представление матроида над GF(3)», Журнал комбинаторной теории , Серия B, 26 (2): 159–173, doi : 10.1016/0095-8956(79)90055-8 , MR  0532586.
8. Geelen, JF ; Gerards, AMH; Kapoor, A. (2000), «Исключенные миноры для GF(4)-представимых матроидов» (PDF) , Журнал комбинаторной теории , Серия B, 79 (2): 247–299, doi :10.1006/jctb.2000.1963, MR  1769191, архивировано из оригинала (PDF) 24 сентября 2010 г..
9. Келли, Л. М.; Мозер, В. О. Дж. (1958), «О числе обычных линий, определяемых n точками», Can. J. Math. , 10 : 210–219, doi : 10.4153/CJM-1958-024-6.
10. Ссылка на премию Фулкерсона 2003 года, получена 18 августа 2012 г.
11. Беттен, А.; Кинген, Р.Дж.; Кинген, С.Р. (2007), «Заметка о GF(5)-представимых матроидах» (PDF) , MATCH Communications in Mathematical and in Computer Chemistry , 58 (2): 511–521, MR  2357372.
12. Джилен, Джерардс и Уиттл объявляют о доказательстве гипотезы Рота. Университет Ватерлоо, 28 августа 2013 г.
13. Гипотеза Роты: исследователь решил математическую задачу 40-летней давности PhysOrg, 15 августа 2013 г.
14. Исследователь CWI доказывает знаменитую гипотезу Рота. Архивировано 26 октября 2013 г. на Wayback Machine CWI, 22 августа 2013 г.
15. «Решение гипотезы Рота» (PDF) , Notices of the American Mathematical Society : 736–743, 17 августа 2014 г.
16. Geelen, Jim; Gerards, Bert; Whittle, Geoff (2015), «Высокосвязанные матроиды в замкнутых по минору классах», Annals of Combinatorics , 19 (1): 107–123, arXiv : 1312.5012 , doi : 10.1007/s00026-015-0251-3, MR  3319863