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

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

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

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

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

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

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

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

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

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

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

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

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

Заявленное доказательство

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

См. также

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

Ссылки

^ Рота, Джан-Карло (1971), «Комбинаторная теория, старая и новая», Труды Международного конгресса математиков (Ницца, 1970), Том 3 , Париж: Готье-Виллар, стр. 229–233, МР 0505646 .
^ «Решение гипотезы Роты» (PDF) , Уведомления Американского математического общества : 736–743, 17 августа 2014 г.
^ Вамос, П. (1978), «Недостающая аксиома теории матроидов утеряна навсегда», Журнал Лондонского математического общества , вторая серия, 18 (3): 403–408, doi : 10.1112/jlms/s2-18.3.403 , МР 0518224 .
^ Тутте, В.Т. (1958), «Гомотопическая теорема для матроидов. I, II», Труды Американского математического общества , 88 : 144–174, doi : 10.2307/1993244 , MR 0101526 .
^ Тутте, WT (1965), «Лекции по матроидам» , Журнал исследований Национального бюро стандартов , 69B : 1–47, doi : 10.6028/jres.069b.001 , MR 0179781 . См., в частности, раздел 5.3, «Характеристика бинарных матроидов», стр.17.
^ Биксби, Роберт Э. (1979), «О характеристике Ридом троичных матроидов», Журнал комбинаторной теории , серия B, 26 (2): 174–204, doi : 10.1016/0095-8956(79)90056-X , МР 0532587 . Биксби приписывает эту характеристику троичных матроидов Ральфу Риду.
^ Jump up to: ^а ^б Сеймур, П.Д. (1979), «Матроидное представление над GF(3)», Журнал комбинаторной теории , серия B, 26 (2): 159–173, doi : 10.1016/0095-8956(79)90055-8 , MR 0532586 .
^ Гилен, Дж. Ф. ; Джерардс, AMH; Капур, А. (2000), «Исключенные миноры для GF(4)-представимых матроидов» (PDF) , Journal of Combinatorial Theory , Series B, 79 (2): 247–299, doi : 10.1006/jctb.2000.1963 , MR 1769191 , заархивировано из оригинала (PDF) на 24 сентября 2010 г.
^ Келли, LM ; Мозер, WOJ (1958), «О количестве обычных линий, определяемых n точками» , Can. Дж. Математика. , 10 : 210–219, номер документа : 10.4153/CJM-1958-024-6 .
^ Цитата на премию Фулкерсона 2003 г. , получено 18 августа 2012 г.
^ Беттен, А.; Кинган, Р.Дж.; Кинган, С.Р. (2007), «Заметка о GF(5)-представимых матроидах» (PDF) , MATCH Communications in Mathematical and in Computer Chemistry , 58 (2): 511–521, MR 2357372 .
↑ Гилен, Джерардс и Уиттл объявляют о доказательстве гипотезы Роты , Университет Ватерлоо, 28 августа 2013 г.
↑ Гипотеза Роты: исследователь решает математическую задачу 40-летней давности PhysOrg, 15 августа 2013 г.
↑ Исследователь CWI доказывает знаменитую гипотезу Роты. Архивировано 26 октября 2013 г. в Wayback Machine CWI, 22 августа 2013 г.
^ «Решение гипотезы Роты» (PDF) , Уведомления Американского математического общества : 736–743, 17 августа 2014 г.
^ Гилен, Джим; Джерардс, Берт; Уиттл, Джефф (2015), «Матроиды с высокой степенью связи в второстепенных закрытых классах», Annals of Combinatorics , 19 (1): 107–123, arXiv : 1312.5012 , doi : 10.1007/s00026-015-0251-3 , MR 3319863

[1] Рота, Джан-Карло (1971), «Комбинаторная теория, старая и новая», Труды Международного конгресса математиков (Ницца, 1970), Том 3 , Париж: Готье-Виллар, стр. 229–233, МР 0505646 .

[2] «Решение гипотезы Роты» (PDF) , Уведомления Американского математического общества : 736–743, 17 августа 2014 г.

[3] Вамос, П. (1978), «Недостающая аксиома теории матроидов утеряна навсегда», Журнал Лондонского математического общества , вторая серия, 18 (3): 403–408, doi : 10.1112/jlms/s2-18.3.403 , МР 0518224 .

[4] Тутте, В.Т. (1958), «Гомотопическая теорема для матроидов. I, II», Труды Американского математического общества , 88 : 144–174, doi : 10.2307/1993244 , MR 0101526 .

[5] Тутте, 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 , МР 0532587 . Биксби приписывает эту характеристику троичных матроидов Ральфу Риду.

[s79-7] Jump up to: ^а ^б Сеймур, П.Д. (1979), «Матроидное представление над GF(3)», Журнал комбинаторной теории , серия B, 26 (2): 159–173, doi : 10.1016/0095-8956(79)90055-8 , MR 0532586 .

[8] Гилен, Дж. Ф. ; Джерардс, AMH; Капур, А. (2000), «Исключенные миноры для GF(4)-представимых матроидов» (PDF) , Journal of Combinatorial Theory , Series B, 79 (2): 247–299, doi : 10.1006/jctb.2000.1963 , MR 1769191 , заархивировано из оригинала (PDF) на 24 сентября 2010 г.

[9] Келли, LM ; Мозер, WOJ (1958), «О количестве обычных линий, определяемых n точками» , Can. Дж. Математика. , 10 : 210–219, номер документа : 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) , Уведомления Американского математического общества : 736–743, 17 августа 2014 г.

[16] Гилен, Джим; Джерардс, Берт; Уиттл, Джефф (2015), «Матроиды с высокой степенью связи в второстепенных закрытых классах», Annals of Combinatorics , 19 (1): 107–123, arXiv : 1312.5012 , doi : 10.1007/s00026-015-0251-3 , MR 3319863

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]