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

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

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

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

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

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