Matroid brukowy

Matroid Vámos , matroid chodnikowy czwartego stopnia; zacienione równoległoboki przedstawiają pięć obwodów o rozmiarze cztery

W matematycznej teorii matroidów matroid brukowy to matroid, w którym każdy obwód ma rozmiar co najmniej tak duży, jak ranga matroida. W matroidzie rangi $displaystyle$ $r$ najwyżej rozmiar więc równoznaczne jest zdefiniowanie matroidów nawierzchniowych jako matroidów, w których rozmiar każdego obwodu należy do zbioru r {\ ${\ Displaystyle \ {r, r + 1 \}}$ . Przypuszczano, że prawie wszystkie matroidy są matroidami brukowymi.

Przykłady

Każdy prosty matroid rangi trzeciej jest matroidem brukowym; na przykład dotyczy to matroidu Fano . Matroid Vámos stanowi kolejny przykład rangi czwartej.

Jednolite matroidy rangi $mają tę właściwość$ że każdy obwód ma dokładnie długość, $brukowymi$ wszystkie są matroidami odwrotność nie zachodzi, na przykład, $matroid$ pełnego wykresu jest brukowany, ale nie jednolity

S ${\ Displaystyle S (t, k, v)}$ to para ${\ Displaystyle (S {\ mathcal {D}})}$ S $)} displaystyle S}$ \ mathcal {D}} jest skończonym zbiorem $displaystyle$ i jest rodziną podzbiorów -elementowych podzbiorów ${\ displaystyle k} re$ ${\$ $}$ z właściwością, że każdy ${D}}}$ $\$ displaystyle { $mathcal$ . Elementy tworzą $-partycji, a$ $S$ są hiperpłaszczyznami matroidu nawierzchniowego na S $displaystyle$ $.$ }

d -Przegrody

Jeśli matroid nawierzchniowy ma rangę $,$ $hiperpłaszczyzny$ tworzą ustalony system znany jako Rodzina dwóch lub więcej zestawów tworzy -partycję, jeśli $każdy$ zestaw w ma rozmiar co najmniej $\ displaystyle$ $\ mathcal {F}}}$ ${\ displaystyle d}$ i każdy -elementowy podzbiór ⋃ re $displaystyle d}$ jest podzbiorem dokładnie jednego zestawu w ${\ displaystyle {\ mathcal {F}$ $}$ . I odwrotnie, jeśli jest - ${\ displaystyle$ , to można jej użyć do zdefiniowania matroidu nawierzchni na mi $}}},$ $= \ bigcup {\ fa {\ displaystyle {\ displaystyle {\ mathcal {f}$ $} mathcal {$ $dla$ którego jest zbiorem hiperpłaszczyzn. W tym matroidzie podzbiór ja $\ displaystyle I}$ ${\ displaystyle E}$ jest niezależny, gdy albo ${\ Displaystyle | I | \ równoważnik d}$ lub ${\ Displaystyle | I | = d + 1}$ i nie jest podzbiorem żadnego zestawu w $\ mathcal {F}}}$ $displaystyle$ .

Wyliczanie kombinatoryczne

Kombinatoryczne wyliczenie prostych matroidów na maksymalnie dziewięciu elementach wykazało, że duża część z nich to również matroidy brukowe. Na tej podstawie przypuszczano, że prawie wszystkie matroidy są matroidami brukowymi. Dokładniej, zgodnie z tym przypuszczeniem, granica, przy n dążącym do nieskończoności, stosunku liczby matroidów nawierzchniowych do liczby wszystkich matroidów powinna być równa jeden. Jeśli tak, to samo stwierdzenie można odnieść do rzadkich matroidów brukowych , matroidy, które są zarówno brukowe, jak i podwójne w stosunku do matroidu chodnikowego. Chociaż pozostaje to otwarte, udowodniono podobne stwierdzenie dotyczące asymptotycznego stosunku logarytmów liczby matroidów i rzadkich matroidów nawierzchniowych.

Historia

$badane$ przez Hartmanisa (1959) w ich równoważnym sformułowaniu pod względem ; Hartmanis nazwał je uogólnionymi sieciami podziału. W swojej książce Combinatorial Geometries z 1970 roku Henry Crapo i Gian-Carlo Rota zauważyli , że te struktury były matroidalne; nazwa „matroid brukowy” została wprowadzona przez Welsha (1976) zgodnie z sugestią Roty.

Prostsza struktura matroidów chodnikowych w porównaniu z arbitralnymi matroidami pozwoliła na udowodnienie pewnych faktów na ich temat, które pozostają nieuchwytne w bardziej ogólnym przypadku. Przykładem jest hipoteza bazowa Roty , stwierdzenie, że zbiór n rozłącznych baz w matroidie rangi n można ułożyć w macierz n × n tak, że rzędy macierzy są podanymi podstawami, a kolumny są również podstawami. Udowodniono, że jest to prawdą w przypadku matroidów chodnikowych, ale pozostaje otwarte dla większości innych matroidów.

Notatki

Geelen, Jim ; Humphries, Peter J. (2006), „Podstawowe przypuszczenie Roty dotyczące matroidów nawierzchniowych” (PDF) , SIAM Journal on Discrete Mathematics , 20 (4): 1042–1045 (elektroniczny), doi : 10,1137/060655596 , hdl : 10092/11877 , MR 2272246 , zarchiwizowane z oryginału (PDF) w dniu 17.06.2012 , pobrane 03.02.2013 .
Hartmanis, Juris (1959), „Teoria krat uogólnionych partycji”, Canadian Journal of Mathematics , 11 : 97–106, doi : 10.4153/CJM-1959-013-8 , MR 0099931 , Zbl 0089.37002 .
Mayhew, Dillon; Newman, Mike; walijski, Dominik; Whittle, Geoff (2011), „O asymptotycznej proporcji połączonych matroidów”, European Journal of Combinatorics , 32 (6): 882–890, doi : 10.1016/j.ejc.2011.01.016 , MR 2821559 .
Oxley, James G. (1992), teoria matroidów , Oxford Science Publications , Oxford: Oxford University Press , ISBN 0-19-853563-5 , Zbl 0784.05002
Pendavingh, Rudi; van der Pol, Jorn (2015), „O liczbie matroidów w porównaniu z liczbą rzadkich matroidów nawierzchniowych”, The Electronic Journal of Combinatorics , 22 (2), # 2.51 .
Welsh, DJA (1976), „2.3. Matroidy chodnikowe”, Matroid Theory , Courier Dover Publications, s. 40–41, 44, ISBN 9780486474397 . Przedruk 2010.