MATROIDELMÉLETI FELADATOK

1. Keressünk olyan matroidot, amelyik semmilyen vektortér felett sem reprezentálható.

2. Legyenek B_{1} és B_{2} egy M matroid bázisai.

(a) Bizonyítsuk be, hogy létezik egy olysn f bijekció B_{1} és B_{2} között, amelyikre B_{1} − x + f(x) minden x ∈ B_{1} esetén bázis M-ben.

(b) Bizonyítsuk be az erős bázisaxiómát:

Legyen x ∈ B_{1} − B_{2}. Ekkor létezik olyan y ∈ B_{2} − B_{1}, hogy B_{1} − x + y és B_{2} − y + x is bázisok M-ben.

3. Legyenek C_{1}, …, C_{m} egy M matroid körei, melyekre

C_{i} ⊈ ⋃_{j≠i} C_{j}.

és D ⊆ S, |D| < m. Bizonyítsuk be, hogy létezik olyan C kör M-ben, melyre

C ⊆ ⋃_{i=1}^{m} C_{i} − D.

4. Legyen M egy matroid S-n az r rangfüggvénnyel és f egy szürjekció S-ről T - re. Bizonyítsuk be, hogy a T -n kapott matroid (az S-beli függetlenbe párosítható halmazok függetlenek) rangfüggvénye teljesíti az

r_{f}(A) = min_{Y ⊆A}(r(f^{−1}(Y)) + |A − Y |) (A ⊆ T)

azonosságot.

5. Legyenek M_{1} és M_{2} matroidok S-n az r_{1} ill. r_{2} rangfüggvénnyel. Ekkor az uniómatroid rangfüggvénye teljesíti az

r(X) = max_{Y ⊆X}(r_{1}(Y) + r_{2}(X − Y)) (X ⊆ S)

azonosságot.

6. Egy G gráf körmatroidja akkor és csak akkor irreducibilis (nem áll elő nem triviális módon két matroid uniójaként), ha minden e élre G − e 2-összefüggő.