Gérard Cornuéjols’s baker’s eighteen 5000 dollars conjectures

Gérard Cornuéjols

Gérard Cornuéjols‘s beautiful (and freely available) book from 2000 Optimization: Packing and Covering is about an important area of combinatorics which is lovely described in the preface to the book

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 $e \in E(G)$ such that $G\backslash e$ 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.

This entry was posted in Combinatorics, Computer Science and Optimization, Open problems and tagged , , , , . Bookmark the permalink.

3 Responses to Gérard Cornuéjols’s baker’s eighteen 5000 dollars conjectures

1. Gil Kalai says:

Let me share with you (with the writer’s permission) an email I received regarding the post:

Hi Prof. Kalai,

My name is Jourdain Lamperski, and I am PhD student at MIT. I hope all is well!

I just enjoyed reading your recent blog post on Gerard’s book. I have two remarks that you might find interesting:

1. The 19th problem to some extent appears as a conjecture in Gerard’s book (Conjecture 6.11, pg. 80), but it is stated in terms of balanced matrices.

2. Very coincidentally, two days before your blog post, I posted a solution to the 19th conjecture for the case of linear balanced graphs (the context in which it was originally conjectured in the cited 1992 paper by Conforti and Rao). Here is a link http://www.mit.edu/~jourdain/balanced.pdf if interested. I have actually already gone through the result with Gerard in person and he thought it was nice.

I thought the timing of our posts was unusually coincidental so I just thought I’d reach out!

Best,

Jourdain