Matroidowa wyrocznia

W matematyce i informatyce wyrocznia matroidowa to podprogram , za pośrednictwem którego algorytm może uzyskać dostęp do matroidu , abstrakcyjnej struktury kombinatorycznej, której można użyć do opisu liniowych zależności między wektorami w przestrzeni wektorowej lub drzewami rozpinającymi wykresu , między innymi Aplikacje.

Najczęściej stosowaną wyrocznią tego typu jest wyrocznia niezależności , podprogram sprawdzający, czy zbiór elementów matroidowych jest niezależny. Zastosowano również kilka innych typów wyroczni; Wykazano, że niektóre z nich są słabsze od wyroczni niezależności, inne silniejsze, a niektóre mają równoważną moc obliczeniową.

Wiele algorytmów wykonujących obliczenia na matroidach zostało zaprojektowanych tak, aby przyjmować wyrocznię jako dane wejściowe, co pozwala im wydajnie działać bez zmian na wielu różnych rodzajach matroidów i bez dodatkowych założeń dotyczących rodzaju używanej matroidy. Na przykład, mając wyrocznię niezależności dla dowolnej matroidy, możliwe jest znalezienie minimalnej podstawy wagi matroidu poprzez zastosowanie zachłannego algorytmu, który dodaje elementy do bazy w kolejności posortowanej według wagi, używając wyroczni niezależności do sprawdzenia, czy każdy element może być dodany.

W teorii złożoności obliczeniowej model Oracle doprowadził do bezwarunkowych dolnych granic udowadniających, że pewnych problemów matroidowych nie można rozwiązać w czasie wielomianowym, bez odwoływania się do nieudowodnionych założeń, takich jak założenie, że P ≠ NP . Problemy, które okazały się trudne w tym przypadku, obejmują sprawdzanie, czy matroid jest binarny lub jednolity , lub sprawdzanie, czy zawiera pewne stałe elementy podrzędne .

Dlaczego wyrocznie?

Chociaż niektórzy autorzy eksperymentowali z komputerowymi reprezentacjami matroidów, które wyraźnie wymieniają wszystkie niezależne zbiory lub wszystkie zbiory bazowe matroidu, reprezentacje te nie są $:$ matroid z elementami może rozwinąć się do reprezentacji zajmującej miejsce $.$ w _ Rzeczywiście, liczba odrębnych matroidów na $w$ rośnie dwukrotnie wykładniczo miarę

${\ Displaystyle 2 ^ {2 ^ {n} n ^ {-3/2 + o (1)}}}$

z czego wynika, że ​​każda jawna reprezentacja zdolna obsłużyć wszystkie możliwe matroidy z konieczności wykorzystywałaby przestrzeń wykładniczą.

Zamiast tego różne typy matroidów mogą być reprezentowane bardziej efektywnie w porównaniu z innymi strukturami, na podstawie których są zdefiniowane: matroidy jednolite na podstawie ich dwóch parametrów numerycznych, matroidy graficzne , matroidy dwukołowe i gammoidy z wykresów, matroidy liniowe z macierzy itp. Jednakże algorytm wykonywania obliczeń na dowolnych matroidach wymaga jednolitej metody dostępu do argumentów, zamiast konieczności przeprojektowania dla każdej z tych klas matroidów. Model Oracle zapewnia wygodny sposób kodowania i klasyfikowania rodzajów dostępu, których może potrzebować algorytm.

Historia

Począwszy od Rado (1942) $funkcje$ „funkcje niezależności” lub „ ” były badane jako jeden z wielu równoważnych sposobów aksjomatyzacji matroidów. Funkcja niezależności odwzorowuje zbiór elementów matroidowych na liczbę, $zbiór$ jest niezależny lub jeśli jest zależny $;$ to znaczy jest to funkcja wskaźnika rodziny niezależnych zbiorów, zasadniczo to samo, co wyrocznia niezależności.

Wyrocznie matroidowe były również częścią najwcześniejszych prac algorytmicznych nad matroidami. Zatem Edmonds (1965) $i$ badając problemy podziału matroidu, założył, że dostęp do danego matroidu odbywa się poprzez podprogram, który jako dane wejściowe przyjmuje niezależny $. }$ element i $($ obwód w i ${\ displaystyle \ scriptstyle x}$ , jeśli istnieje) lub stwierdza, że ​​taki obwód nie istnieje. Edmonds (1971) użył podprogramu sprawdzającego, czy dany zbiór jest niezależny (to znaczy, według bardziej współczesnej terminologii, wyroczni niezależności ) i zauważył, że informacje, których dostarcza, są wystarczające do znalezienia podstawy minimalnej wagi w czasie wielomianowym.

Począwszy od prac Korte i Hausmanna (1978) oraz Hausmanna i Korte (1978) , badacze rozpoczęli badanie wyroczni z punktu widzenia udowodnienia dolnych granic algorytmów dla matroidów i pokrewnych struktur. Obie te prace Hausmanna i Korte dotyczyły problemu znalezienia zbioru niezależnego od maksymalnej liczności, który jest łatwy dla matroidów, ale (jak pokazały) trudniejszy do przybliżenia lub dokładnego obliczenia dla bardziej ogólnych systemów niezależności reprezentowana przez wyrocznię niepodległościową. Ta praca zapoczątkowała lawinę publikacji pod koniec lat 70. i na początku 80. XX wieku, pokazujących podobne wyniki w zakresie twardości w przypadku problemów na matroidach i porównujących moc różnych rodzajów wyroczni matroidowych.

Od tego czasu wyrocznia niezależności stała się standardem w większości badań nad algorytmami matroidowymi. Kontynuowano również badania nad dolnymi granicami i porównaniami różnych typów wyroczni.

Rodzaje wyroczni

Rozważono następujące typy matroidalnych wyroczni.

• Wyrocznia niezależności przyjmuje na wejściu zestaw elementów matroidowych i jako wyjście zwraca wartość logiczną , true jeśli dany zestaw jest niezależny i false w przeciwnym razie. Można go łatwo zaimplementować w oparciu o podstawową strukturę, z której zdefiniowano matroidę dla matroidów graficznych , matroid poprzecznych , gammoidów i matroid liniowych, a także dla matroid utworzonych z nich za pomocą standardowych operacji, takich jak sumy bezpośrednie.
• Wyrocznia bazowa przyjmuje na wejściu zestaw elementów matroidowych i jako wyjście zwraca wartość logiczną, true, jeśli dany zestaw jest bazą, i false w przeciwnym razie.
• Wyrocznia obwodów przyjmuje na wejściu zestaw elementów matroidowych i jako wyjście zwraca wartość logiczną, true, jeśli dany zestaw jest obwodem, i false w przeciwnym razie.
• Wyrocznia Edmondsa (1965) zajmująca się znajdowaniem obwodów przyjmuje jako dane wejściowe niezależny zbiór i dodatkowy element i albo stwierdza, że ​​ich związek jest niezależny, albo znajduje obwód w związku i zwraca go.
• Wyrocznia rangi przyjmuje na wejściu zestaw elementów matroidowych i jako wynik zwraca wartość liczbową, rangę danego zestawu.
• Rozważano trzy typy wyroczni domknięć: jedną, która sprawdza, czy dany element należy do domknięcia danego zbioru, drugą, która zwraca zamknięcie zbioru i trzecią, która sprawdza, czy dany zbiór jest domknięty .
• Rozpinająca wyrocznia przyjmuje na wejściu zestaw elementów matroidu i jako wyjście zwraca wartość logiczną, true jeśli dany zestaw jest rozpinany (tj. zawiera bazę i ma tę samą rangę co cała matroida) i false w przeciwnym razie.
• Wyrocznia obwodowa przyjmuje na wejściu zbiór elementów matroidowych i jako wynik zwraca wartość liczbową, czyli rozmiar najmniejszego obwodu w tym zestawie (lub $)$ zbiór jest niezależny ).
• Port wyroczni dla stałego elementu matroidu przyjmuje na wejściu zestaw elementów matroidu i zwraca na wyjściu wartość logiczną, true jeśli dany zestaw zawiera obwód, który zawiera $}$$\scriptstyle x}$$\ displaystyle \ scriptstyle x$ i false w przeciwnym razie.

Względna moc różnych wyroczni

Chociaż znanych jest wiele typów wyroczni, wybór, które można zastosować, można uprościć, ponieważ wiele z nich ma równoważną moc obliczeniową. Mówi się, że wyrocznia jest wielomianowo redukowalna do innej wyroczni , jeśli dowolne wywołanie $może$${\ displaystyle \ scriptstyle X}$ być symulowane przez algorytm uzyskujący dostęp do matroidu za pomocą ${\ displaystyle \ scriptstyle X$ tylko wyrocznia $wielomianowy$ zajmuje czas mierzone liczbą elementów matroidu; w kategoriach teorii złożoności jest to redukcja Turinga . Mówi się, że dwie wyrocznie są wielomianowo równoważne , jeśli można je do siebie wielomianowo redukować. Jeśli i są równoważne wielomianowo, to $każdy wynik potwierdzający istnienie lub$$nieistnienie$ algorytmu czasu wielomianowego dla problemu matroidowego przy użyciu Oracle $displaystyle \ scriptstyle X}$ dowodzi również tego samego dla Oracle ${\ Displaystyle \ scriptstyle Y}$ .

Na przykład wyrocznia niepodległości jest wielomianem równoważna wyroczni Edmondsa (1965) odkrywającej obwody . Jeśli dostępna jest wyrocznia znajdująca obwody, zestaw można przetestować pod kątem niezależności, używając co najwyżej wywołań do wyroczni, zaczynając od pustego zestawu , dodając elementy danego zestawu po jednym elemencie na raz, n $\ displaystyle \ scriptstyle n}$ oraz użycie wyroczni do wyszukiwania obwodów w celu sprawdzenia, czy każde dodanie zachowuje niezależność zbioru, który został dotychczas skonstruowany. W drugą stronę, jeśli dostępna jest wyrocznia niezależności, obwód w zestawie ${\ Displaystyle \ scriptstyle I \ puchar \ {x \}}$ można znaleźć przy użyciu co najwyżej $y$ do wyroczni poprzez testowanie dla każdego elementu $\ displaystyle \ scriptstyle y \ w ja}$ , czy ${\ displaystyle \ scriptstyle I \ setminus \ {y \} \ puchar \ {x \}}$ jest niezależny i zwraca elementy, dla których odpowiedź brzmi „nie”. Wyrocznia niepodległości jest również wielomianowym odpowiednikiem wyroczni rangowej, wyroczni rozpinającej, pierwszych dwóch typów wyroczni zamykającej i wyroczni portowej.

Wyrocznia podstawowa, wyrocznia obwodowa i wyrocznia sprawdzająca, czy dany zbiór jest zamknięty, są słabsze niż wyrocznia niezależności: można je symulować w czasie wielomianowym za pomocą algorytmu, który uzyskuje dostęp do matroidu za pomocą wyroczni niezależności, ale nie odwrotnie . Ponadto żadna z tych trzech wyroczni nie może symulować się nawzajem w czasie wielomianowym. W tym samym sensie wyrocznia obwodu jest silniejsza niż wyrocznia niepodległości.

Oprócz wielomianowych redukcji Turinga w czasie, rozważono również inne typy redukowalności. W szczególności Karp, Upfal i Wigderson (1988) wykazali, że w algorytmach równoległych wyrocznie rangi i niezależności znacząco różnią się mocą obliczeniową. Wyrocznia rangi pozwala na zbudowanie podstawy minimalnej wagi przez ${\ displaystyle \ scriptstyle n}$ jednoczesne zapytania o przedrostki posortowanej kolejności elementów matroidu: element należy do bazy optymalnej wtedy i tylko wtedy, gdy ranga jego przedrostka różni się od rangi poprzedniego przedrostka. W przeciwieństwie do tego, $wolniejsze :$ je rozwiązać deterministycznie w krokach czasowych i istnieje dolna granica z nawet w przypadku losowych algorytmów równoległych ${\ displaystyle \ scriptstyle \ Omega ((n/\ log n) ^ {1/3})}$

Algorytmy

Wiadomo, że wiele problemów dotyczących matroidów można rozwiązać w czasie wielomianowym za pomocą algorytmów, które uzyskują dostęp do matroidu jedynie poprzez wyrocznię niezależności lub inną wyrocznię o równoważnej mocy, bez potrzeby jakichkolwiek dodatkowych założeń dotyczących rodzaju matroidu, jaki został im dany. Te problemy rozwiązywane wielomianowo obejmują:

• Znalezienie minimalnej lub maksymalnej wagi ważonej matroidy przy użyciu algorytmu zachłannego .
• Podział elementów matroidy na minimalną liczbę niezależnych zbiorów i znalezienie największego zbioru, który jest jednocześnie niezależny w dwóch danych matroidach. Ten ostatni problem nazywa się przecięciem matroidowym , a rozwiązania obu problemów są ze sobą ściśle powiązane.
• $,$ czy matroid jest podłączony (w sensie Tutte 1966 ) dla $scriptstyle k \ równoważnik 3}$ .
• Testowanie czy dany matroid jest graficzny czy regularny .
• Znalezienie rozkładu ucha danej matroidy, ciągu obwodów, których związkiem jest matroid i w którym każdy obwód pozostaje obwodem po skurczeniu wszystkich poprzednich obwodów w sekwencji. Taki rozkład można spotkać także z dodatkową właściwością, że do każdego obwodu należy wybrany element matroidowy.
• Znalezienie rozkładu rozgałęzień danej matroidy, gdy szerokość jej rozgałęzień jest nie większa niż stała stała.
• Lista wszystkich zasad, mieszkań lub obwodów matroidy w czasie wielomianowym na zestaw wyjściowy.
• Przybliżanie liczby zasad za pomocą losowego schematu aproksymacji w pełni wielomianowego w czasie dla matroidy z $displaystyle$ i stopniem , przy dodatkowym założeniu, że liczba zasad mieści się w zakresie $\ scriptstyle n} współczynnik$$-zestawów$ liczby elementów.

Dowody na niemożliwość

W przypadku wielu problemów matroidowych można wykazać, że wyrocznia niezależności nie zapewnia wystarczającej mocy, aby umożliwić rozwiązanie problemu w czasie wielomianowym. Główną ideą $. W$ dowodów jest znalezienie dwóch matroidów i $się$ które są trudne do rozróżnienia przez algorytm $\ displaystyle \ scriptstyle M'}$ , jeśli ma wysoki stopień symetrii i różni się od $M$ tylko w odpowiedziach na niewielką liczbę zapytań, wówczas algorytm może potrzebować bardzo dużej liczby zapytań, aby mieć pewność odróżnienia danych wejściowych typu od danych wejściowych utworzonych za $jednego$ z symetrie permutacji $}$$\ displaystyle \ scriptstyle M'$ .

Prosty przykład takiego podejścia można wykorzystać do pokazania, że ​​trudno jest sprawdzić, czy matroida jest jednorodna . Dla uproszczenia ekspozycji, niech $parzysty$ , niech będzie jednolitym matroidem $}$$scriptstyle U {} _ {n}$${n / 2$$}$ i niech będzie matroidem utworzonym z ${\ displaystyle \ scriptstyle M'$$uczynienie$ jednego z $niezależnych$ bazowych zamiast Aby algorytm mógł poprawnie sprawdzić, czy jego dane wejściowe są jednolite, musi być w $odróżnić$$każdej$ permutacji . Aby jednak algorytm deterministyczny mógł to zrobić, musi przetestować każdy z $podzbiory$ elementów: jeśli pominął jeden zestaw, mógłby zostać oszukany przez wyrocznię, która wybrała ten sam zestaw jako ten, który ma być zależny. Dlatego może być konieczne sprawdzenie, czy matroid jest jednolity

${\ Displaystyle {\ binom {n} {n/2}} = \ Omega \ lewo ({\ Frac {2 ^ {n}} {\ sqrt {n} }}\Prawidłowy)}$

zapytania o niezależność, znacznie wyższe niż wielomian. Nawet losowy algorytm musi wykonać prawie tyle samo zapytań, aby mieć pewność rozróżnienia tych dwóch matroidów.

i Korte (1982) formalizują to podejście, udowadniając, że ilekroć istnieją dwie matroidy i $′ {\ displaystyle \$$scriptstyle M'}$ na tym samym zestawie elementów, ale z różnymi odpowiedziami na problemy, algorytm, który poprawnie rozwiązuje zadany problem na tych elementach, musi zastosować co najmniej

${\ Displaystyle {\ Frac {|\ nazwa operatora {aut} (M) |} {\ suma _ {i} |\ nazwa operatora {poprawka} (M, Q_ {i}) |}}}$

zapytania $}$ gdzie $,$ oznacza grupę automorfizmu Q $\ displaystyle \ scriptstyle Q_ {i$ } rodzina zbiorów, których niezależność różni się od do $\$$scriptstyle M'$ i $samą$ podgrupę automorfizmów, $odwzorowuje$ siebie Na przykład grupa automorfizmu jednolitej matroidy jest po prostu grupą symetryczną o rozmiarze $zestaw$$a$ problemie testowania jednolitych matroidów był tylko z ${\ Displaystyle \ scriptstyle |\ operatorname {fix} (M, Q_ {i}) | = (n/2)! ^ {2}}$ , mniejszy o współczynnik wykładniczy niż ${\ displaystyle \ scriptstyle n!$ }

Problemy, które okazały się niemożliwe do obliczenia w czasie wielomianowym przez algorytm matroidowej wyroczni, obejmują:

• Badanie, czy dana matroida jest jednorodna.
• $koranką$ stałą matroidę jako element podrzędny, z wyjątkiem specjalnych przypadków, gdy $jest jednolity z$ co najwyżej jeden. Mówiąc bardziej ogólnie, jeśli jest ustalonym, skończonym zbiorem matroidów i nie ma jednolitego matroidu, to H. ${$$}}$ nie jest możliwe sprawdzenie w czasie wielomianowym, czy dana matroida zawiera jedną, czy więcej matroidów w ${\ displaystyle \ scriptstyle {\ mathcal {H}}}$ jako nieletni.
• Sprawdzanie, czy dana matroida jest binarna , czy można ją reprezentować za pomocą dowolnego określonego stałego pola lub czy istnieje pole, nad którym można ją reprezentować.
• Rozwiązywanie problemu dopasowania matroidu, w którym danymi wejściowymi jest graf i matroid na jego wierzchołkach, a celem jest znalezienie jak największego dopasowania na grafie, pod warunkiem, że dopasowane wierzchołki tworzą niezależny zbiór .
• Sprawdzanie, czy dana matroida jest samodualna , poprzeczna , dwudzielna , eulerowska lub orientowalna .
• Obliczanie obwodu (rozmiar najmniejszego obwodu), rozmiaru największego obwodu, liczby obwodów, liczby zasad, liczby mieszkań, liczby mieszkań o najwyższym stopniu, wielkości największego mieszkania, wielomianu Tutte'a lub łączności danego matroid.

Spośród zbioru wszystkich właściwości $-elementowych$ , część właściwości, które nie wymagają wykładniczego czasu do przetestowania, spada do zera w limicie, gdy idzie ${\ displaystyle \ scriptstyle n}$ do nieskończoności.

Zobacz też

• Grupa czarnej skrzynki , model przypominający wyrocznię dla teorii grup
• Ukryty wykres , model podobny do Oracle dla algorytmów grafowych

Notatki

•   Azar, Y.; Broder, Arizona ; Frieze, AM (1994), „O problemie przybliżenia liczby baz matroidu”, Information Processing Letters , 50 (1): 9–11, doi : 10.1016/0020-0190(94)90037-X , MR 1279491 .
• Bansal, N.; Pendavingh, R.; van der Pol, J. (2012), O liczbie matroidów , arXiv : 1206.6270 , Bibcode : 2012arXiv1206.6270B .
•   Bixby, Robert E.; Cunningham, William H. (1979), „Matroids, graphs, and 3-connectivity”, Teoria grafów i tematy pokrewne (Proc. Conf., Univ. Waterloo, Waterloo, Ont., 1977) , New York: Academic Press, s. 91–103, MR 0538038 .
•   Chávez Lomelí, Laura; Welsh, Dominic (1996), „Randomised przybliżenie liczby zasad”, Matroid Theory (Seattle, WA, 1995) , Contemporary Mathematics, tom. 197, Providence, RI: American Mathematical Society, s. 371–376, doi : 10.1090/conm/197/02534 , MR 1411698 .
•   Coullard, Collette R .; Hellerstein, Lisa (1996), „Niezależność i wyrocznie portowe dla matroidów, z zastosowaniem do teorii uczenia się obliczeniowego”, Combinatorica , 16 (2): 189–208, doi : 10.1007/BF01844845 , MR 1401892 .
•   Cunningham, William H. (1986), „Poprawione granice algorytmów partycji i przecięcia matroidów”, SIAM Journal on Computing , 15 (4): 948–957, doi : 10.1137/0215066 , MR 0861361 .
•   Edmonds, Jack (1965), „Minimalna partycja matroidu na niezależne podzbiory” , Journal of Research of the National Bureau of Standards , 69B : 67–72, doi : 10.6028/jres.069b.004 , MR 0190025 .
•   Edmonds, Jack (1971), „Matroids i zachłanny algorytm”, Programowanie matematyczne , 1 : 127–136, doi : 10.1007/BF01584082 , MR 0297357 .
•   Fujishige, Satoru; Zhang, Xiaodong (1995), „Efektywny algorytm skalowania kosztów dla problemu niezależnego przypisania”, Journal of the Operations Research Society of Japan , 38 (1): 124–136, MR 1337446 .
•   Hausmann, Dirk; Korte, Bernhard (1978), „Dolne granice najgorszej złożoności niektórych algorytmów Oracle”, Discrete Mathematics , 24 (3): 261–276, doi : 10.1016/0012-365X (78) 90097-3 , MR 0523316 .
•   Hausmann, D.; Korte, B. (1981), „Algorytmiczne a aksjomatyczne definicje matroidów”, Programowanie matematyczne w Oberwolfach (Proc. Conf., Math. Forschungsinstitut, Oberwolfach, 1979) , Mathematical Programming Studies, tom. 14, s. 98–111, doi : 10.1007/BFb0120924 , MR 0600125 .
•   Ingleton, AW (1959), „Notatka o funkcjach i randze niezależności”, Journal of the London Mathematical Society , Second Series, 34 : 49–56, doi : 10.1112/jlms/s1-34.1.49 , MR 0101848 .
•   Jensen, Per M.; Korte, Bernhard (1982), „Złożoność algorytmów właściwości matroidów”, SIAM Journal on Computing , 11 (1): 184–190, doi : 10.1137/0211014 , MR 0646772 .
•   Karp, Richard M .; Upfal, Eli ; Wigderson, Avi (1988), „Złożoność wyszukiwania równoległego”, Journal of Computer and System Sciences , 36 (2): 225–253, doi : 10.1016/0022-0000(88)90027-X , MR 0950432 .
•   Kelmans, AK; Polesskiĭ, VP (1994), „Zbiory ekstremalne oraz problemy pokrywania i pakowania w matroidach”, Wybrane zagadnienia z matematyki dyskretnej (Moskwa, 1972–1990) , Amer. Matematyka. Towarzystwo Tłumacz. Ser. 2, tom. 158, Providence, RI: Amer. Matematyka. Soc., s. 149–174, MR 1269136 .
•    Khachiyan, L .; Boros, E.; Elbassioni, K.; Gurvich, V.; Makino, K. (2005), „O złożoności niektórych problemów wyliczeniowych dla matroidów”, SIAM Journal on Discrete Mathematics , 19 (4): 966–984, CiteSeerX 10.1.1.124.4286 , doi : 10.1137/S0895480103428338 , MR 2206374 .
•   Knuth, Donald E. (1974), „Asymptotyczna liczba geometrii”, Journal of Combinatorial Theory , Series A, 16 : 398–400, doi : 10.1016/0097-3165(74)90063-6 , MR 0335312 .
•   Korte, Bernhard; Hausmann, Dirk (1978), „Analiza zachłannej heurystyki dla systemów niezależności”, Algorithmic Aspects of Combinatorics (Conf., Vancouver Island, BC, 1976) , Annals of Discrete Mathematics, tom. 2, s. 65–74, doi : 10.1016/S0167-5060(08)70322-4 , MR 0500689 .
•   Korte, B.; Schrader, R. (1981), „Ankieta na temat technik wyroczni”, w: Gruska, Józef; Chytil, Michal (red.), Matematyczne podstawy informatyki 1981, Proceedings, 10. Sympozjum Štrbské Pleso, Czechosłowacja 31 sierpnia – 4 września 1981 , Notatki z wykładów z informatyki, tom. 118, Berlin: Springer, s. 61–77, doi : 10.1007/3-540-10856-4_74 , MR 0652740 .
•   Lazarson, T. (1958), „Problem reprezentacji funkcji niezależności”, Journal of the London Mathematical Society , Second Series, 33 : 21–25, doi : 10.1112/jlms/s1-33.1.21 , MR 0098701 .
•   Lovász, L. (1981), „Problem dopasowywania matroidów”, Metody algebraiczne w teorii grafów, tom. I, II (Szeged, 1978) , zob. Matematyka. Towarzystwo János Bolyai, tom. 25, Amsterdam: North-Holland, s. 495–517, MR 0642059 .
•   Mayhew, Dillon (2008), „Matroid complex and nonsuccinct opisy”, SIAM Journal on Discrete Mathematics , 22 (2): 455–466, arXiv : math/0702567 , doi : 10.1137/050640576 , MR 2399359 .
•   Oum, Sang-il ; Seymour, Paul (2007), „Testing Branch-width”, Journal of Combinatorial Theory , seria B, 97 (3): 385–393, doi : 10.1016/j.jctb.2006.06.006 , MR 2305892 .
•   Piff, MJ (1973), „An Upperbound for the number of matroids”, Journal of Combinatorial Theory , Series B, 14 : 241–245, doi : 10.1016/0095-8956(73)90006-3 , MR 0316282 .
•   Piff, MJ; Welsh, DJA (1971), „Liczba geometrii kombinatorycznych”, The Bulletin of the London Mathematical Society , 3 : 55–56, doi : 10.1112/blms/3.1.55 , MR 0282867 .
•   Rado, R. (1942), „Twierdzenie o relacjach niezależności”, The Quarterly Journal of Mathematics , Second Series, 13 : 83–89, Bibcode : 1942QJMat..13...83R , doi : 10.1093/qmath/os- 13.1.83 , MR 0008250 .
•   Rado, R. (1957), „Notatka o funkcjach niezależności”, Proceedings of the London Mathematical Society , Third Series, 7 : 300–320, doi : 10.1112/plms/s3-7.1.300 , MR 0088459 .
•   Robinson, GC; Welsh, DJA (1980), „The computational complex of matroid Properties”, Mathematical Proceedings of the Cambridge Philosophical Society , 87 (1): 29–45, Bibcode : 1980MPCPS..87...29R , doi : 10.1017/S0305004100056498 , MR 0549295 .
•   Seymour, PD (1981), „Rozpoznawanie graficznych matroidów”, Combinatorica , 1 (1): 75–78, doi : 10.1007/BF02579179 , MR 0602418 .
•   Seymour, PD ; Walton, PN (1981), „Detecting matroid minors”, Journal of the London Mathematical Society , druga seria, 23 (2): 193–203, doi : 10.1112/jlms/s2-23.2.193 , MR 0609098 .
•   Truemper, K. (1982), „O efektywności testów reprezentowalności dla matroidów”, European Journal of Combinatorics , 3 (3): 275–291, doi : 10.1016/s0195-6698(82)80039-5 , MR 0679212 .
• Truemper, K. (1998), Matroid Decomposition (PDF) (poprawiona red.) .
•   Tutte, WT (1966), „Łączność w matroidach”, Canadian Journal of Mathematics , 18 : 1301–1324, doi : 10.4153/CJM-1966-129-2 , MR 0205880 .