Тротуарный матроид

В математической теории матроидов матроид мощения — это матроид, в котором размер каждой схемы не меньше ранга матроида. В матроиде ранга $r$ каждая схема имеет максимальный размер $r+1$ , поэтому эквивалентно определить матроиды дорожного покрытия как матроиды, в которых размер каждой цепи принадлежит множеству $\{r,r+1\}$ . ^[1] Было высказано предположение, что почти все матроиды являются матроидами мощения.

Примеры

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

Униформа матроидов ранга $r$ обладают тем свойством, что каждая цепь имеет длину ровно $r+1$ и, следовательно, все они являются матроидами; ^[2] обратное неверно, например, для матроида циклов полного графа $K_{4}$ укладывает, но не равномерно. ^[3]

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

г -Перегородки

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

Комбинаторное перечисление

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

История

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

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

Примечания

^ Jump up to: ^а ^б ^с Валлийский (1976) .
^ Оксли 1992 , с. 26
^ Оксли 1992 , с. 27
^ Оксли 1992 , с. 367
^ Мэйхью и др. (2011) .
^ Pendavingh & van der Pol (2015) .
^ Оксли 1992 , с. 75
^ Гилен и Хамфрис (2006) .

Ссылки

Гилен, Джим ; Хамфрис, Питер Дж. (2006), «Базовая гипотеза Роты для мощения матроидов» (PDF) , SIAM Journal on Discrete Mathematics , 20 (4): 1042–1045 (электронный), doi : 10.1137/060655596 , hdl : 10092/11877 , MR 2272246 , заархивировано из оригинала (PDF) 17 июня 2012 г. , получено 3 февраля 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 University Press , ISBN 0-19-853563-5 , Збл 0784.05002
Пендавинг, Руди; ван дер Пол, Йорн (2015), «О количестве матроидов по сравнению с количеством матроидов с разреженным дорожным покрытием», Электронный журнал комбинаторики , 22 (2), #2.51 .
Валлийский, DJA (1976), «2.3. Мощение матроидов», Теория матроидов , Courier Dover Publications, стр. 40–41, 44, ISBN 9780486474397 . Перепечатано в 2010 году.

[w-1] Jump up to: ^а ^б ^с Валлийский (1976) .

[Ox26-2] Оксли 1992 , с. 26

[Ox27-3] Оксли 1992 , с. 27

[Ox367-4] Оксли 1992 , с. 367

[FOOTNOTEMayhewNewmanWelshWhittle2011-5] Мэйхью и др. (2011) .

[FOOTNOTEPendavinghvan_der_Pol2015-6] Pendavingh & van der Pol (2015) .

[Ox75-7] Оксли 1992 , с. 75

[FOOTNOTEGeelenHumphries2006-8] Гилен и Хамфрис (2006) .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]