Матроид для мощения

Матроид Вамоса, матроид для мощения четвертого ранга; заштрихованные параллелограммы изображают его пять цепей размера четыре

В математической теории матроидов, матроид для мощения - это матроид, в котором каждая цепь имеет размер по крайней мере, такого же размера, как ранг матроида. В матроиде ранга $r\; \{\backslash \; displaystyle\; r\}$каждая схема имеет размер не более $r\; +\; 1\; \{\backslash \; displaystyle\; r\; +\; 1\}$, поэтому он эквивалентен определить матроиды дорожного покрытия как матроиды, в которых размер каждой цепи принадлежит набору $\{r,\; r\; +\; 1\}\; \{\backslash \; displaystyle\; \backslash \; \{r,\; r\; +\; 1\; \backslash \}\}$. Было высказано предположение, что почти все матроиды являются матроидами мощения.

• 1 Примеры
• 2 d-раздела
• 3 Комбинаторное перечисление
• 4 История
• 5 Примечания
• 6 Ссылки

Каждый простой матроид третьего ранга - матроид для мощения; например, это верно для матроида Фано . Матроид Vámos является другим примером четвертого ранга.

Унифицированные матроиды ранга $r\; \{\backslash \; displaystyle\; r\}$обладают тем свойством, что каждая цепь имеет длину точно $r\; +\; 1\; \{\backslash \; displaystyle\; r\; +\; 1\}$и, следовательно, все матроиды для мощения; обратное неверно, например, матроид цикла из полного графа $K\; 4\; \{\backslash \; displaystyle\; K\_\; \{4\}\}$прокладывает, но не единообразно.

A Система Штейнера $S\; (t,\; k,\; v)\; \{\backslash \; displaystyle\; S\; (t,\; k,\; v)\}$- это пара $(S,\; D)\; \{\backslash \; displaystyle\; (S,\; \{\backslash \; mathcal\; \{D\}\})\}$где $S\; \{\backslash \; displaystyle\; S\}$- конечный набор размера $v\; \{\backslash \; displaystyle\; v\}$и $D\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{D\}\}\}$- семейство $k\; \{\backslash \; displaystyle\; k\}$-элементные подмножества $S\; \{\backslash \; displaystyle\; S\}$со свойством, что каждое $t\; \{\backslash \; displaystyle\; t\}$-элементное подмножество $S\; \{\backslash \; displaystyle\; S\}$также является подмножеством ровно одного набора в $D\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{D\}\}\}$. Элементы $D\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{D\}\}\}$образуют $t\; \{\backslash \; displaystyle\; t\}$-раздел $S\; \{\backslash \; displaystyle\; S\}$и, следовательно, являются гиперплоскостями матроида для мощения на $S\; \{\backslash \; displaystyle\; S\}$.

Если матроид для мощения имеет ранг $d\; +\; 1\; \{\backslash \; displaystyle\; d\; +\; 1\}$, тогда его гиперплоскости образуют систему множеств, известную как $d\; \{\backslash \; displaystyle\; d\}$-partition. Семейство из двух или более наборов $F\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{F\}\}\}$образует $d\; \{\backslash \; displaystyle\; d\}$-раздел, если каждый набор в $F\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{F\}\}\}$имеет размер не менее $d\; \{\backslash \; displaystyle\; d\}$и каждые $d\; \{\backslash \; displaystyle\; d\}$-элементное подмножество $\bigcup \; F\; \{\backslash \; displaystyle\; \backslash \; bigcup\; \{\backslash \; mathcal\; \{F\}\}\}$- это подмножество ровно одного набора в $F\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{F\}\}\}$. И наоборот, если $F\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{F\}\}\}$является разделом $d\; \{\backslash \; displaystyle\; d\}$, то его можно использовать для определите матроид для мощения на $E\; =\; \bigcup \; F\; \{\backslash \; displaystyle\; E\; =\; \backslash \; bigcup\; \{\backslash \; mathcal\; \{F\}\}\}$, для которого $F\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{F\}\}\}$- набор гиперплоскостей. В этом матроиде подмножество $I\; \{\backslash \; displaystyle\; I\}$из $E\; \{\backslash \; displaystyle\; E\}$является независимым, если $|\; Я\; |\; \le \; d\; \{\backslash \; displaystyle\; |\; I\; |\; \backslash \; leq\; d\}$или $|\; Я\; |\; =\; d\; +\; 1\; \{\backslash \; displaystyle\; |\; I\; |\; =\; d\; +\; 1\}$и $I\; \{\backslash \; displaystyle\; I\}$не является подмножеством какого-либо набора в $F\; \{\; \backslash \; displaystyle\; \{\backslash \; mathcal\; \{F\}\}\}$.

Комбинаторное перечисление простых матроидов, содержащих до девяти элементов, показало, что большая часть из них также являются матроидами для мощения. На этом основании было высказано предположение, что почти все матроиды являются матроидами для мощения. Точнее, согласно этой гипотезе, предел, когда n стремится к бесконечности, отношения между количеством матроидов для мощения и количеством всех матроидов должен равняться единице. Если это так, то же самое утверждение можно сделать для матроидов с разреженным покрытием, матроидов, которые одновременно являются мощными и двойными матроидам для дорожного покрытия. Хотя это остается открытым, аналогичное утверждение об асимптотическом соотношении логарифмов числа матроидов и разреженных матроидов для дорожного покрытия было доказано.

Матроиды для дорожного покрытия первоначально были изучены Хартманис (1959), в их эквивалентной формулировке в терминах $d\; \{\backslash \; displaystyle\; d\}$-разделов; Хартманис назвал их обобщенными решетками разбиений. В своей книге 1970 года «Комбинаторные геометрии» Генри Крапо и Джан-Карло Рота отметили, что эти структуры были матроидными; название «матроид для мощения» было введено Уэлшем (1976) по предложению Роты.

Более простая конструкция матроидов для мощения по сравнению с произвольными матроидами позволила некоторым фактам о них быть доказанным, что остаются неуловимыми в более общем случае. Примером может служить гипотеза о базисе Роты, утверждение о том, что набор из n непересекающихся баз в матроиде ранга n может быть организован в матрицу размера n × n так, чтобы строки матрицы были заданными базами, а колонны также являются основаниями. Это было доказано для матроидов, но остается открытым для большинства других матроидов.

• Гилен, Джим ; Хамфрис, Питер Дж. (2006), «Основная гипотеза Роты для мощения матроидов» (PDF), SIAM Journal on Discrete Mathematics, 20 (4): 1042–1045 (электронный), doi : 10.1137 / 060655596, MR 2272246, заархивировано из исходного (PDF) 17.06.2012, получено 03.02.2013.
• Хартманис, Юрис (1959), «Теория решеток обобщенных разделов», Canadian Journal of Mathematics, 11 : 97–106, doi : 10.4153 / CJM-1959-013-8, MR 0099931, Zbl 0089.37002.
• Мэйхью, Диллон; Ньюман, Майк; Валлийский, доминик; Уиттл, Джефф (2011), «Об асимптотической пропорции связанных матроидов», European Journal of Combinatorics, 32 (6): 882–890, doi : 10.1016 / j.ejc.2011.01.016, MR 2821559.
• Оксли, Джеймс Г. (1992), теория матроидов, Oxford Science Publications, Oxford: Oxford University Press, ISBN 0-19-853563-5, Zbl 0784.05002
• Пендавинг, Руди; ван дер Поль, Йорн (2015), «О количестве матроидов по сравнению с количеством матроидов с разреженными дорожками», Электронный журнал комбинаторики, 22 (2), # 2.51.
• Валлийский, DJA (1976), «2.3. Мощение матроидов», Теория матроидов, Courier Dover Publications, стр. 40–41, 44, ISBN 9780486474397. Перепечатано в 2010 г.