Sample Problems in 18.997: Topics in Combinatorial Optimization
Even though 18.997 does not have regular problem sets, problems are occasionally mentioned in lecture for people to work on. Here is a sample of such questions:
-
Petersen's theorem (Lecture 3) says that every cubic bridgeless graph contains a perfect matching. Show that for any even set T of vertices, a bridgeless cubic graph (V,E) contains a T-join of cardinality at most |V|/2 where a T-join is a subgraph with odd degree at vertices in T and even at vertices not in T.
-
Show that a graph is such that every edge is in a perfect matching if and only if it admits a bipartite ear decomposition, where a bipartite ear decomposition is one that starts from an even cycle and repeatedly adds an odd path between vertices of different colors.
-
Consider a strongly connected digraph D and a valid ordering O (lectures 7, 8). Show that a covering of the vertices by directed cycles of total minimum index can be obtained by network flows. What does network flow duality tells you here?
-
(Open.) Consider a matroid and assume S can be partitioned into k bases. Can one number cyclically be the element of S such that any sequence of k consecutive elements form a basis? Prove it when the numbering is not required to be cyclic.
- Read a proof of (the strong version of) Nash-Williams's theorem saying that any undirected graph can be oriented so as to preserve half of the local connectivity rounded down. Can you provide an elementary proof?