Scribd
Upload
8 views5 pages

Understanding Matroids and Their Properties

A matroid is a mathematical structure that generalizes linear independence in vector spaces, defined as a pair ⟨X,I⟩ where X is the ground set and I is the set of independent subsets. It must satisfy three axiomatic properties: the empty set is independent, any subset of an independent set is independent, and for any two independent sets, one can be enlarged by adding an element from the other without losing independence. An example illustrates a matroid on the ground set {x,y,z} with specific dependent and independent subsets.

Uploaded by

shailaja.cse
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
8 views5 pages

Understanding Matroids and Their Properties

A matroid is a mathematical structure that generalizes linear independence in vector spaces, defined as a pair ⟨X,I⟩ where X is the ground set and I is the set of independent subsets. It must satisfy three axiomatic properties: the empty set is independent, any subset of an independent set is independent, and for any two independent sets, one can be enlarged by adding an element from the other without losing independence. An example illustrates a matroid on the ground set {x,y,z} with specific dependent and independent subsets.

Uploaded by

shailaja.cse
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

• What matroid is?

• Matroid is a structure that abstracts and generalizes the notion of linear independence in
vector spaces.
Here goes the formal definition. Matroid is a pair ⟨X,I⟩
• where X is called ground set and I is set of all independent subsets of X. In other words
matroid ⟨X,I⟩ gives a classification for each subset of X to be either independent or dependent
(included in I or not included in I).
• Of course, we are not speaking about arbitrary classifications. These 3 properties must hold
for any matroid:

• Empty set is independent.


• Any subset of independent set is independent.
• If independent set A
• has smaller size than independent set B
• , there exist at least one element in B
• that can be added into A
• without loss of independency.
• These are axiomatic properties of matroid. To prove that we are
dealing with matroid, we generally have to prove these three
properties.

• For example, explicit presentation of matroid on ground set {x,y,z}


• which considers {y,z}
• and {x,y,z}
• to be dependent and marked red. Other sets are independent and
marked green.

You might also like