# 11 Aug, 2021

Courses βΈ± Algorithms
You can also access the quiz on Itempool here if you want to practice, or see the notes below for more context.

#### In-class Quiz Questions

π
We defined a matroid as a family over a fixed finite universe with the following properties:
1. (Empty set axiom.) .
1. (Hereditary property.) If and then .
1. (Exchange axiom.) If and , then there exists an element such that also belongs to .
1. 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?
1. Yes, it is a matroid
2. No, it violates the first axiom (empty set membership)
3. No, it violates the second axiom (heriditary)
4. No, it violates the third axiom (exchange property)
β
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.
1. 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?
1. Yes, it is a matroid
2. No, it violates the first axiom (empty set membership)
3. No, it violates the second axiom (heriditary)
4. No, it violates the third axiom (exchange property)