Courses βΈ± Algorithms
You can also access the quiz on Itempool here if you want to practice, or see the notes below for more context.
Lecture Recording
In-class Quiz Questions
We defined a matroid as a family over a fixed finite universe with the following properties:
- (Empty set axiom.) .
- (Hereditary property.) If and then .
- (Exchange axiom.) If and , then there exists an element such that also belongs to .
- Let be an arbitrary undirected graph. Let E be the ground set. A subset is independent if the subgraph of is connected. Does this collection of independent sets form a matroid?
- Yes, it is a matroid
- No, it violates the first axiom (empty set membership)
- No, it violates the second axiom (heriditary)
- No, it violates the third axiom (exchange property)
Reveal answer
Violates the second and third axioms.
For a violation of (c) consider a star. For a violation of (d) consider a graph that has a small star (say five leaves) and a large star (say ten leaves) whose centers are connected by an edge, and let and be the set of edges on the small and large star, respectively.
- Consider a ground set that consists of colored elements. Each element has exactly one color. Let a set of elements be independent if no pair of included elements share a color. Is this collection of independent sets a matroid?
- Yes, it is a matroid
- No, it violates the first axiom (empty set membership)
- No, it violates the second axiom (heriditary)
- No, it violates the third axiom (exchange property)
Reveal answer
Yes
Straightforward to verify the first two axioms. Use the pigeon-hole principle to show the exchange axiom.
Β