Pravidelný matroid - Regular matroid

V matematice, a běžný matroid je matroid to může být zastoupeny nade vše pole.

Definice

A matroid je definována jako rodina podmnožin konečné množiny, splňující určité axiomy. Sady v rodině se nazývají „nezávislé sady“. Jedním ze způsobů konstrukce matroidu je výběr konečné sady vektorů v a vektorový prostor, a definovat podmnožinu vektorů, které mají být v matroidu nezávislé, když jsou lineárně nezávislé ve vektorovém prostoru. Každá rodina sad konstruovaných tímto způsobem je matroid, ale ne každý matroid lze konstruovat tímto způsobem a vektorové prostory přes různé pole vést k různým sadám matroidů, které z nich lze sestrojit.

Matroid je běžné, když pro každé pole , může být reprezentován systémem vektorů nad .[1][2]

Vlastnosti

Pokud je matroid pravidelný, je také jeho duální matroid,[1] a tak je každý z nich nezletilí.[3] Každý přímý součet regulárních matroidů zůstává pravidelný.[4]

Každý grafický matroid (a každý co-grafický matroid) je pravidelný.[5] Naopak, každý běžný matroid může být sestaven kombinací grafických matroidů, co-grafických matroidů a určitého desetičlenného matroidu, který není ani grafický, ani co-grafický, pomocí operace pro kombinaci matroidů, která zobecňuje klika-součet operace na grafech.[6]

Počet bází v běžném matroidu lze vypočítat jako určující přidružené matice, zobecňující Kirchhoffova věta o maticovém stromu pro grafické matroidy.[7]

Charakterizace

The jednotný matroid (čtyřbodová čára) není pravidelná: nelze ji realizovat přes dva prvky konečné pole GF (2), takže to není binární matroid, i když to lze realizovat ve všech ostatních oblastech. Matroid z Fano letadlo (matroid třetí řady, ve kterém je závislých sedm z trojic bodů) a jeho dvojí také nejsou pravidelné: mohou být realizovány nad GF (2) a nad všemi poli charakteristických dvou, ale ne nad jinými poli než ty. Tak jako Tutte (1958) ukázaly, že tyto tři příklady jsou základem teorie regulárních matroidů: každý nepravidelný matroid má alespoň jeden z těchto tří jako Méně důležitý. Pravidelné matroidy jsou tedy přesně ty matroidy, které nemají jednoho ze tří zakázaných nezletilých , Fano letadlo nebo jeho duální.[8]

Pokud je matroid pravidelný, musí být jasně realizovatelný přes dvě pole GF (2) a GF (3). Opak je pravdou: každý matroid, který je realizovatelný v obou těchto dvou polích, je pravidelný. Výsledek vyplývá ze zakázané drobné charakterizace matroidů realizovatelné nad těmito poli, která je součástí rodiny výsledků kodifikovaných Rotaova domněnka.[9]

Pravidelné matroidy jsou matroidy, které lze definovat z a zcela unimodulární matice, matice, ve které má každá čtvercová submatice determinant 0, 1 nebo −1. Vektory realizující matroid lze brát jako řádky matice. Z tohoto důvodu se někdy také nazývají pravidelné matroidy unimodulární matroidy.[10] Rovnocennost regulárních matroidů a unimodulárních matic a jejich charakterizace zakázanými nezletilými osobami jsou hlubokými výsledky W. T. Tutte, původně prokázal jím pomocí Tutteova věta o homotopii.[8] Gerards (1989) později zveřejnil alternativní a jednodušší důkaz charakterizace unimodulárních matic zakázanými nezletilými.[11]

Algoritmy

Tady je polynomiální čas algoritmus pro testování, zda je matroid pravidelný, vzhledem k přístupu k matroidu prostřednictvím věštba nezávislosti.[12]

Reference

  1. ^ A b Fujishige, Satoru (2005), Submodulární funkce a optimalizace, Annals of Discrete Mathematics, Elsevier, s. 24, ISBN  9780444520869.
  2. ^ Oxley, James G. (2006), Teorie matroidů, Oxfordské postgraduální texty z matematiky, 3Oxford University Press, s. 209, ISBN  9780199202508.
  3. ^ Oxley (2006), str. 112.
  4. ^ Oxley (2006), str. 131.
  5. ^ Tutte, W. T. (1965), „Přednášky o matroidech“, Journal of Research of the National Bureau of Standards, 69B: 1–47, doi:10,6028 / jres.069b.001, PAN  0179781.
  6. ^ Seymour, P. D. (1980), „Rozklad regulárních matroidů“, Journal of Combinatorial Theory, Řada B, 28 (3): 305–359, doi:10.1016/0095-8956(80)90075-1, hdl:10338.dmlcz / 101946, PAN  0579077.
  7. ^ Maurer, Stephen B. (1976), „Maticové zobecnění některých vět o stromech, cyklech a cyklech v grafech“, SIAM Journal on Applied Mathematics, 30 (1): 143–148, doi:10.1137/0130017, PAN  0392635.
  8. ^ A b Tutte, W. T. (1958), "Homotopická věta pro matroidy. I, II", Transakce Americké matematické společnosti, 88 (1): 144–174, doi:10.2307/1993244, JSTOR  1993244, PAN  0101526.
  9. ^ Seymour, P. D. (1979), "Matroidová reprezentace nad GF (3)", Journal of Combinatorial Theory, Řada B, 26 (2): 159–173, doi:10.1016/0095-8956(79)90055-8, PAN  0532586.
  10. ^ Oxley (2006), str. 20.
  11. ^ Gerards, A. M. H. (1989), „Krátký důkaz charakterizace Tutteových zcela unimodulárních matic“, Lineární algebra a její aplikace, 114/115: 207–212, doi:10.1016/0024-3795(89)90461-8.
  12. ^ Truemper, K. (1982), „O účinnosti testů reprezentability pro matroidy“, European Journal of Combinatorics, 3 (3): 275–291, doi:10.1016 / s0195-6698 (82) 80039-5, PAN  0679212.