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.

Β