Miscellaneous
A chess composition
Despite the large amount of material, it is meant as a study (see the other types of chess problems). It is admittedly less elegant than a study (for one thing, it is not an endgame) but the theme that I wanted to implement (saying more would spoil it!) does require a lot of pieces.
Erdős-Szekeres theorem proven in 6 Nimmt! rules
The Erdős-Szekeres theorem states that in any sequence of n² real numbers there is a monotone subsequence of length n. Actually, it says something slightly stronger: In any sequence of (s-1)(r-1)+1 real numbers there is either an increasing subsequence of length s or a decreasing subsequence of length r. Erdős and Szekeres proved this result in 1935, Abraham Seidenberg wrote a 8-line proof in 1958, and J. Michael Steel surveyed some of the several existing proofs in 1995.
One simple proof is contained in the rule of Wolfgang Kramer's card game 6 Nimmt! (Take 5!). The important thing in the rules is how a card that you play is placed on the table: the card goes on top of the stack where the current top card is the largest among the stacks with a smaller card on top. If all the stacks have on top a higher card, then a new stack is created (well, this is not exactly true in the game). Now the proof. Take your n²-card sequence and play it out according to those rules. Each time you do not play in the first stack, draw on the table a pointer going from the card you just played to the current top card in the previous stack.
In the end, either you have a stack of height at least n, which constitutes an increasing subsequence of length n, or you have more than n stacks, and following the pointers from the last stack and reversing gives you a decreasing subsequence of length n.
Solver for Minimum Fill-In a.k.a Chordal Completion (in Python)
With R. B. Sandeep and Florian Sikora, we participated in the second edition of the PACE challenge. The goal was to solve the most of 100 instances of Minimum Fill-In, being given 30 minutes per instance, using parameterized algorithms and no (M)ILP nor SAT solvers. Minimum Fill-In, also called Chordal Completion, consists of finding a smallest set of edges to add to a graph to make it chordal; i.e., the graph does not contain an induced cycle of length at least four. This problem is surprisingly tricky. For instance, the exact optimal value is not known on graphs as simple as grids.
Around 2000, Vincent Bouchitté and Ioan Todinca developed in a series of papers a nice theory of so-called potential maximal cliques, in order to solve efficiently Treewidth and Minimum Fill-In on some classes of graphs. This theory would be later used by Fedor Fomin and Yngve Villanger to design a parameterized subexponential time algorithm running in 2O(√ k log k). Sandeep together with Yixin Cao showed that this algorithm is essentially optimal under the Exponential Time Hypothesis.
We implemented the approach of Bouchitté and Todinca based on listing the potential maximal cliques and some home-made heuristics to compute upper bounds on the size of the solution to prune the search. Obtaining good lower bounds would speed up our code but appear really challenging. Here is a general presentation of the algorithm and the code can be downloaded there.