Description
Absztrakt:
Egy gráf maximális matroidjának fogalmát dolgozza ki Meera Sitharam és Andrew Vince cikke, melyet a következőképpen definiálhatunk. A matroid alaphalmaza egy (nagy) teljes gráf élhalmaza, E(K_n), és adott továbbá egy (kicsi) G gráf. Olyan matroidok érdekelnek minket melyeknek alaphalmaza E(K_n), és a G gráf minden izomorf példánya matroidelméleti értelemben vett kört alkot. Nevezzük ezeket G-körű matroidoknak, bár a cikkben erre nem vezettek be elnevezést.
A cikk egyik fő eredménye, hogy a G-körű matroidok között létezik egy egyértelmű maximális, azaz egy olyan G-körű matroid, melynek rangfüggvénye mindenhol nagyobb vagy egyenlő bármely más G-körű matroid rangfüggvényénél. Ezt nevezzük a G gráf maximum matroidjának.
A cikk megvizsgálja konkrét G gráfok esetét, így például belátja azt, hogy ha G=C_3 akkor a teljes gráf körmatroidját kapjuk. A G=K_{1,3}, G=C_4, G=K_4 eseteket is külön vizsgálja, ahol különösen érdekes a K_4 esete, ugyanis annak bázisai pontosan a kétdimenziós merevség témaköréből ismert Laman-gráfokat adja meg. A cikk arra következtet, hogy G=K_5 esetén a háromdimenziós merevségi matroidot kapjuk, azonban a cikk bonyolultsága miatt egyelőre nem tudni biztosan igaz-e ez az állítása.