Matroids

Ein Matroid hat verschiedene äquivalente Definitionen

• indepent sets: {`(E, I): E`} die Grundmenge, {`I sube 2^E`} mit
  • {`I != {}`}
  • hereditary property: {`A sube B in I rArr A in I`}
  • Austausch: {` A, A' in I, |A| < |A'| rArr EE a' in A': A uu a' in I`}
• Basen: maximale independent sets >===> {`(E, B), B sube 2^E`} mit
  • {`B != {}`}
  • Austausch: {` A, A' in B, a in A \\ A' rArr EE a' in A' \\ A: A \\ a uu a' in B`} (insbesondere ist ein echtes Subset einer Basis keine Basis)
• Circuit: minimale dependet set, d.h. jede echte Untermenge is indepent >===> {`(E, C), C sube 2^E`} mit
  • {`{} !in C`}
  • {`A' in C, A sub A', A != A' rArr A !in C`}
  • Austausch: {` A' != A'' in C, a in A' nn A'' rArr EE A in C, A sub A' uu A'' \\ a`}
• rank: maximal Kardinalität eines independent sets {`(E,r): r: 2^E rarr NN`} mit
  • submodular: {`A', A'' sub E: r(A' uu A'') + r(A' nn A'') <= r(A') + r(A'')`}
  • monoton: {`A sub E, a in E: r(A) <= r(A uu a) <= r(A) + 1 `}
• Hüllenoperator: alle Elemente, die Rank nicht erhöhen >===> {`cl: 2^E rarr 2^E`}, mit {`AA A, A' sube E, a,a' in E`}:
  • {`A sube cl(A)`}
  • {`cl(A) = cl(cl(A))`}
  • {`A sube A' rArr cl(A) sube cl(A')`}
  • {`a in cl(A uu a') \\ A rArr a' in cl(A uu a) \\ A`}
• Flats = closed subsets des Hüllenoperators >===> {`(E, F), F sube 2^E`} mit
  • {`E in F`}
  • {`A, A' in F rArr A nn A' in F`}
  • the flats that cover (enthalten ohne Zwischenelement) flat A partition E\A
    • {`cover(A) = {A' in F | A' supe A and !EE A'' in F: A sub A'' sub A}`}
    • {`A in F rArr uuu cover(A) = E and AA A', A'' in cover(A): A' nn A'' = A`}
• Hyperplanes: maximale flats, rank = r-1 >===> {`(E, H), H sube 2^E`} mit
  • {`not EE A, A' in H: A sub A'`}
  • {`A', A'' in H, a in E: a !in A' uu A'' rArr EE A in H: A supe A' nn A'' uu a`}
• und zurück: Mengen aus E, sodass jedes Subset eine andere Hyperebenenbüdel bestimmt (?)

weiteres

• Matroid Lattice: Flats ordered by set inclusion, mit rank Funktion
• orthogonal: {` e', e'' sube E: e' _|_ e'' iff | e' nn e' | <> 1 `}
• cocircuits: inklusions minimale Elemente aus {`{{} != x sube E | AA c in C: x _|_ c} `}
• cocircuits erfüllen Circuit Axiome: bilden Duales Matroid

Beispiele:

• Menge von Vektoren: independent set: linear unabhängige, rank = dimension
• Graphen: independent = zyklenfrei, Circuit = Zyklus