The integer programming models known as set packing and set covering have a wide range of applications, such as pattern recognition, plant location and airline crew scheduling. Sometimes, due to the special structure of the constraint matrix, the natural linear programming relaxation yields an optimal solution that is integer, thus solving the problem. Sometimes, both the linear programming relaxation and its dual have integer optimal solutions. Under which conditions do such integrality properties hold? This question is of both theoretical and practical interest. Min-max theorems, polyhedral combinatorics and graph theory all come together in this rich area of discrete mathematics. In addition to min-max and polyhedral results, some of the deepest results in this area come in two flavors: “excluded minor” results and “decomposition” results. In these notes, we present several of these beautiful results. Three chapters cover min-max and polyhedral results. The next four cover excluded minor results. In the last three, we present decomposition results.
The last sentence of the preface gives this post some urgency
In particular, we state 18 conjectures. For each of these conjectures, we offer $5000 as an incentive for the first correct solution or refutation before December 2020.
The book starts with Konig’s theorem, the first figure is the Petersen graph, and among the other mathematical heroes mentioned in the book are Edmonds, Johnson, Seymour, Lovász, Lehman, Camion, Tutte, and Truemper.
The title of this post refers to Baker’s dozen. In the 13th century Bakers who were found to have shortchanged customers could be liable to severe punishment, and to guard against the punishment of losing a hand to an axe, a baker would give 13 for the price of 12, to be certain of not being known as a cheat. (Wikipedia) In this post we mention a 19th problem for which Gerard offered 5000 dollars. (I am not sure if there is time limit for that problem. I am thankful to Maria Chudnovsky for telling me about the problem.)
What happened to the 18 problems in the list?
Perhaps the most difficult problem on the list was solved first: two of the problems in the list were about perfect graphs and were settled with the solution of the strong perfect graph conjecture by Chudnovsky, Robertson, Seymour, and Thomas. Three of the problems were about balanced bipartite graphs. They were solved by Chudnovsky and Seymour in 2006. Conjecture 4.14 in Chapter 4 was solved by Jonathan Wang (2010) 30,000 dollars were thus collected and 60,000 dollars are still offered (until Dec 2020).
Balanced bipartite graphs and the 19th problem.
Balanced bipartite graphs are sort of bipartite analogs of perfect graphs. They are bipartite graphs so that every induced cycle have length divisible by four. Gerard’s 19the prize money problem is also about balanced bipartite graphs.
Conjecture: Let G be balanced. Then there is such that is a balanced graph.
In other words every balanced bipartite graph contains an edge which is not a unique chord in any cycle.
This conjecture is Conjecture 5.20 in
M. Conforti, G. Cornuejos, K. Vuskovic Balanced matrices
In that paper, this conjecture is attributed to:
M. Conforti and M.R Rao “Structural properties and decomposition of linear
balaced matrices”, Mathematical Programming 55 (1992) 129-168.