Matroid Theory Assignments
Fall 2023

This page will be updated gradually.

To the main course page | extra material | corrections page

Readings and Problems

The readings are from James Oxley, Matroid Theory, second edition, Oxford University Press, 2011.

Readings

Read these lightly first, then carefully.
Read and think about the recommended problems and hand-in problems.
Hand in the specified problems; I accept partial solutions and I don't expect you to answer every single one.
Extra problems and some definitions are on a separate page.
There are a few errors in the book. Check the corrections page often.

Weekly Assignments

Check the main page outline for exact readings.
Read every assigned problem, both recommended and hand-in. Even the ones you don't solve usually have useful information about matroids.
I do not expect you to solve all the problems. Solve as many as you can do a good job on. A few good solutions are worth much more than many bad solutions.

* = an especially important problem to learn, whether or not you solve it.

No. Week of: Reading: Recommended problems: Hand in: Notes:

0 All term: Oxley's Preliminaries It has essential background on graphs and more, that you should keep constantly in mind (while sleeping?).

A 8/23-9/1: §§1.1-1.3 1.1#1,4,9; 1.2#1,2,5; 1.3#1,2 M 9/1: 1.1#2,5,11; 1.2#3,4; 1.3#3 1.2#1,2,3,5 are worthwhile theorems to learn.

B 9/1-6: §§1.4-5,7 1.3#7; 1.4#3,4 F 9/5: 1.1#*14; 1.3#6(a); 1.4#1,2 1.1#14 is a theorem you should learn, called "strong circuit elimination".

C 9/6-11: §§2.1-3 1.3#5; 1.4#6,*11; 1.5#2,6,15; 2.1#2,5 M 9/18: 1.4#*5,8; 1.5#1,3,16; 1.7#2(a); 2.1#1(a),4,10 Omit clutters, m-partitions, spikes.
1.4#5,11 are worthwhile theorems to learn.

D 9/13-22: §§3.1-3 2.1#6; 2.2#2,4; 2.3#1(b); 3.1#4; 3.2#2(c),3 W 9/27: 2.2#1,3,*6,8; 2.3#2,8; 3.1#*1,*3; 3.2#1,6 Omit transversal matroids, gammoids, spikes.

E 9/22-29: §§4.1-2; 4.3.1, 4.3.7-8 in §4.3 1.7#7; 3.2#1,3,7; 3.3#2; 4.1#3,*8 M 10/9: 2.2#7; 3.1#2,8,*17; 3.2#11(a,b); 4.1#*1 Omit transversal matroids, gammoids, spikes.

F (6) 9/29-10/6: §§5.1-3 4.2#5,9; 4.3#3; 5.1#2,6,*7 M 10/16: 4.1#2; 4.2#4,7; 4.3#1,*5; 5.1#1,3; 5.2#*5 Representation of M(G), Prop. 5.2.7, and Whitney’s 2-Isomorphism Theorem are essential.
Omit transversal matroids, gammoids, spikes.

G (7) 10/9-13: §§5.4(part), 6.1-3 6.1#3; 6.2#3,4; 6.3#1 M 10/23: 6.1#1,4,5; 6.2#1,2,6; 6.3#3 In §5.4, learn the definition of a series-parallel network (p. 153) and results 5.4.10 and 5.4.12 (statements).
Ch. 6: Projective and affine geometry and their representable matroids.

H (8) 10/16: §§6.4-6(parts), 6.9 (part) 6.4#8; 6.5#*9; 6.9#*1 M 10/30: 6.2#5,7; 6.4#3; 6.6#2,6 In §6.4, read about the Fano and non-Fano matroids in p. 183, middle (one paragraph and the statement of Lemma 6.4.4) and Proposition 6.4.8.
In §§6.4-6, 6.9, see the main page for the exact parts.

I (9) 10/23-27: Chapter on Möbius function Möbius chapter #1,11. M 11/6: Möbius chapter #13,17-19; Extra VII #1; IX #1. Characteristic and chromatic polynomials. See the main page for the exact readings. "Combinatorial geometry" means simple matroid.

J (10) 10/30-11/10: Paper on arrangements; GRS paper Extra VIII #3,4. M 11/13: Extra I #2; VIII #1,2,5,6; IX #3,4. Arrangements of hyperplanes. Signed graphs and their hyperplane arrangements.

K (11) 11/13-21: SG paper;
SGC (coloring) paper Problems on signed graphs: IX #9(c,d). Tu 11/21: Problems on signed graphs: VIII #4; IX #2,5-6,9(a,b),11. Signed graphs and their frame matroids.

L (12) 11/21-11/29: §6.10,
BG1 paper Problems on signed graphs: IX #10(c),13,14,17. W 11/29: Problems on signed graphs: IX #7,10(a,b),12,15.
Biased graphs: X #2. Gain and biased graphs, frame matroid, and hyperplane arrangements.

M (13) 12/1-4: §6.10,
BG2 paper Biased graphs: X #1,4. W 12/6: Problems on biased graphs: X #3,5,7(a,b),8,9. Frame and lift matroids and hyperplane arrangements of gain and biased graphs.

N (14) 12/4-6: Biased graphs: X #13,15,22,23. M 12/11: Biased graphs: X #10,11,12. Gain graph coloring, frame matroid, and Dowling geometries.

* F 12/8: Cobiased graphs: Guest lecture by Dan Slilaty (Wright State) online (WebEx) via Combinatorics Seminar.

O (15) Dec. 11-22: Finals week +. Biased graphs: X #13,15,16(ternary),28(!). W 12/20: Biased graphs: X #14,16(binary),24,25,26a,27. There will not be a final exam.

No.	Week of:	Reading:	Recommended problems:	Hand in:	Notes:
0	All term:	Oxley's Preliminaries			It has essential background on graphs and more, that you should keep constantly in mind (while sleeping?).
A	8/23-9/1:	§§1.1-1.3	1.1#1,4,9; 1.2#1,2,5; 1.3#1,2	M 9/1: 1.1#2,5,11; 1.2#3,4; 1.3#3	1.2#1,2,3,5 are worthwhile theorems to learn.
B	9/1-6:	§§1.4-5,7	1.3#7; 1.4#3,4	F 9/5: 1.1#*14; 1.3#6(a); 1.4#1,2	1.1#14 is a theorem you should learn, called "strong circuit elimination".
C	9/6-11:	§§2.1-3	1.3#5; 1.4#6,*11; 1.5#2,6,15; 2.1#2,5	M 9/18: 1.4#*5,8; 1.5#1,3,16; 1.7#2(a); 2.1#1(a),4,10	Omit clutters, m-partitions, spikes. 1.4#5,11 are worthwhile theorems to learn.
D	9/13-22:	§§3.1-3	2.1#6; 2.2#2,4; 2.3#1(b); 3.1#4; 3.2#2(c),3	W 9/27: 2.2#1,3,6,8; 2.3#2,8; 3.1#1,*3; 3.2#1,6	Omit transversal matroids, gammoids, spikes.
E	9/22-29:	§§4.1-2; 4.3.1, 4.3.7-8 in §4.3	1.7#7; 3.2#1,3,7; 3.3#2; 4.1#3,*8	M 10/9: 2.2#7; 3.1#2,8,17; 3.2#11(a,b); 4.1#1	Omit transversal matroids, gammoids, spikes.
F (6)	9/29-10/6:	§§5.1-3	4.2#5,9; 4.3#3; 5.1#2,6,*7	M 10/16: 4.1#2; 4.2#4,7; 4.3#1,5; 5.1#1,3; 5.2#5	Representation of M(G), Prop. 5.2.7, and Whitney’s 2-Isomorphism Theorem are essential. Omit transversal matroids, gammoids, spikes.
G (7)	10/9-13:	§§5.4(part), 6.1-3	6.1#3; 6.2#3,4; 6.3#1	M 10/23: 6.1#1,4,5; 6.2#1,2,6; 6.3#3	In §5.4, learn the definition of a series-parallel network (p. 153) and results 5.4.10 and 5.4.12 (statements). Ch. 6: Projective and affine geometry and their representable matroids.
H (8)	10/16:	§§6.4-6(parts), 6.9 (part)	6.4#8; 6.5#9; 6.9#1	M 10/30: 6.2#5,7; 6.4#3; 6.6#2,6	In §6.4, read about the Fano and non-Fano matroids in p. 183, middle (one paragraph and the statement of Lemma 6.4.4) and Proposition 6.4.8. In §§6.4-6, 6.9, see the main page for the exact parts.
I (9)	10/23-27:	Chapter on Möbius function	Möbius chapter #1,11.	M 11/6: Möbius chapter #13,17-19; Extra VII #1; IX #1.	Characteristic and chromatic polynomials. See the main page for the exact readings. "Combinatorial geometry" means simple matroid.
J (10)	10/30-11/10:	Paper on arrangements; GRS paper	Extra VIII #3,4.	M 11/13: Extra I #2; VIII #1,2,5,6; IX #3,4.	Arrangements of hyperplanes. Signed graphs and their hyperplane arrangements.
K (11)	11/13-21:	SG paper; SGC (coloring) paper	Problems on signed graphs: IX #9(c,d).	Tu 11/21: Problems on signed graphs: VIII #4; IX #2,5-6,9(a,b),11.	Signed graphs and their frame matroids.
L (12)	11/21-11/29:	§6.10, BG1 paper	Problems on signed graphs: IX #10(c),13,14,17.	W 11/29: Problems on signed graphs: IX #7,10(a,b),12,15. Biased graphs: X #2.	Gain and biased graphs, frame matroid, and hyperplane arrangements.
M (13)	12/1-4:	§6.10, BG2 paper	Biased graphs: X #1,4.	W 12/6: Problems on biased graphs: X #3,5,7(a,b),8,9.	Frame and lift matroids and hyperplane arrangements of gain and biased graphs.
N (14)	12/4-6:		Biased graphs: X #13,15,22,23.	M 12/11: Biased graphs: X #10,11,12.	Gain graph coloring, frame matroid, and Dowling geometries.
*	F 12/8:	Cobiased graphs: Guest lecture by Dan Slilaty (Wright State) online (WebEx) via Combinatorics Seminar.
O (15)	Dec. 11-22:	Finals week +.	Biased graphs: X #13,15,16(ternary),28(!).	W 12/20: Biased graphs: X #14,16(binary),24,25,26a,27.	There will not be a final exam.

To the main course page | extra material | corrections page

Matroid Theory AssignmentsFall 2023

Readings and Problems

Readings

Weekly Assignments

Matroid Theory Assignments
Fall 2023