Гипотеза о базисе Рота - Rotas basis conjecture

В линейная алгебра и теория матроидов, Базисная гипотеза Роты недоказанный догадка относительно перестановки базы, названный в честь Джан-Карло Рота. В нем говорится, что если Икс является либо векторное пространство измерения п или, в более общем смысле, матроид ранга п, с п непересекающиеся основания Bя, то можно расположить элементы этих баз в п × п матрица таким образом, что строки матрицы являются точно заданными основаниями, а столбцы матрицы также являются основаниями. То есть должна быть возможность найти второй набор п непересекающиеся основания Cя, каждый из которых состоит из одного элемента из каждой из баз Bя.

Примеры

Девять вершин трех цветных треугольников (красный, синий и желтый) перегруппированы в три радужных треугольника (черные края).

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

Чтобы увидеть в этом пример гипотезы о базисе, можно использовать либо линейная независимость векторов (Икся,уя, 1) в трехмерном настоящий векторное пространство (где (Икся,уя) являются Декартовы координаты вершин треугольника) или, что то же самое, можно использовать матроид ранга три, в котором множество S точек не зависит, если либо |S| ≤ 2 или S образует три вершины невырожденного треугольника. Для этой линейной алгебры и этого матроида базисами являются в точности невырожденные треугольники. Учитывая три входных треугольника и три треугольника радуги, можно упорядочить девять вершин в матрицу 3 × 3, в которой каждая строка содержит вершины одного из одноцветных треугольников, а каждый столбец содержит вершины одного из радужные треугольники.

Аналогично, для точек в трехмерном евклидовом пространстве гипотеза утверждает, что шестнадцать вершин четырех невырожденных тетраэдров четырех разных цветов могут быть перегруппированы в четыре радужных тетраэдра.

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

Формулировка базисной гипотезы Роты была впервые опубликована Хуанг и Рота (1994), приписывая это (без ссылки) Роте в 1989 году.[1] Базисная гипотеза доказана для матроиды для мощения (для всехп)[2] и для случая п ≤ 3 (для всех типов матроидов).[3] Для произвольных матроидов можно расположить базисные элементы в матрицу первой Ω (√п) столбцы которых являются основаниями.[4] Гипотеза о базисе для линейных алгебр над полями нулевой характеристики и для четных значений п следует из другой гипотезы о Латинские квадраты Алон и Тарси.[1][5] На основании этой импликации гипотеза, как известно, верна для линейных алгебр над действительные числа для бесконечного множества значенийп.[6]

Связанные проблемы

В связи с Теорема Тверберга, Барани и Ларман (1992) предположил, что для каждого набора р(d + 1) очков в d-размерный Евклидово пространство, окрашенный d +1 цвет таким образом, чтобы было р точек каждого цвета, есть способ разбить точки на радужные симплексы (наборы d +1 балл по одной точке каждого цвета) таким образом, чтобы выпуклые оболочки этих множеств имели непустое пересечение.[7] Например, двумерный случай (доказанный Барани и Ларманом) с р = 3 утверждает, что для каждого набора из девяти точек на плоскости, раскрашенных в три цвета и по три точки каждого цвета, можно разделить точки на три пересекающихся радужных треугольника, утверждение, подобное основной гипотезе Роты, в которой можно разбить точки на три невырожденных радужных треугольника. Гипотеза Барани и Лармана позволяет рассматривать коллинеарную тройку точек как радужный треугольник, тогда как базисная гипотеза Роты этого не допускает; с другой стороны, гипотеза о базисе Роты не требует, чтобы треугольники имели общее пересечение. Существенный прогресс в гипотезе Барани и Лармана был достигнут Благоевич, Матчке и Циглер (2009).[8]

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

Рекомендации

  1. ^ а б Хуанг, Роза; Рота, Джан-Карло (1994), "О связи различных гипотез о латинских квадратах и ​​коэффициентах выпрямления", Дискретная математика, 128 (1–3): 225–236, Дои:10.1016 / 0012-365X (94) 90114-7, МИСТЕР  1271866. См., В частности, гипотезу 4, с. 226.
  2. ^ Гилен, Джим; Хамфрис, Питер Дж. (2006), "Основная гипотеза Роты для мощения матроидов" (PDF), Журнал SIAM по дискретной математике, 20 (4): 1042–1045, CiteSeerX  10.1.1.63.6806, Дои:10.1137/060655596, МИСТЕР  2272246.
  3. ^ Чан, Венди (1995), "Свойство обмена матроида", Дискретная математика, 146 (1–3): 299–302, Дои:10.1016 / 0012-365X (94) 00071-3, МИСТЕР  1360125.
  4. ^ Гилен, Джим; Уэбб, Керри (2007), «На основе гипотезы Роты» (PDF), Журнал SIAM по дискретной математике, 21 (3): 802–804, Дои:10.1137/060666494, МИСТЕР  2354007.
  5. ^ Онн, Шмуэль (1997), "Красочная детерминантная идентичность, гипотеза Роты и латинские квадраты", Американский математический ежемесячник, 104 (2): 156–159, Дои:10.2307/2974985, JSTOR  2974985, МИСТЕР  1437419.
  6. ^ Глинн, Дэвид Г. (2010), "Гипотезы Алона – Тарси и Роты в размерности простое минус один", Журнал SIAM по дискретной математике, 24 (2): 394–399, Дои:10.1137/090773751, МИСТЕР  2646093.
  7. ^ Барань, И.; Ларман, Д. Г. (1992), "Цветная версия теоремы Тверберга", Журнал Лондонского математического общества, Вторая серия, 45 (2): 314–320, CiteSeerX  10.1.1.108.9781, Дои:10.1112 / jlms / s2-45.2.314, МИСТЕР  1171558.
  8. ^ Благоевич, Павле В. М .; Матчке, Бенджамин; Циглер, Гюнтер М. (2009), Оптимальные оценки цветной задачи Тверберга, arXiv:0910.4987, Bibcode:2009arXiv0910.4987B.

внешняя ссылка