read

In conferences held at the Oberwolfach Institute, participants usually dine together in a room witg tables of different sizes, and each participant has an assigned seat. Gerhard Ringel asked whether there exists a seating arrangement for an odd number \(v\) of people and \((v−1)/2\) meals so that all pairs of participants are seated next to each other exactly once.

The full pre-print is available on Arxiv here, while the published version is on Australasian Journal of Combinatorics

Keynotes

  • OP Jopt: JOPT 2019 Optimization Days in Montreal

Resources

  • GitHub repository for the OberSolver
  • GitHub repository for the brute-force Constraing Programming solver for the OP
  • GitHub repository for the proof of \(OP(23,5)\)

Combinatorial Mysteries

For the specific case of \(OP(23,5)\), it is likely that no solution exists. Despite this fact, apparently no proof (either computational or analytical) has been published.

If you are wondering, the dog is Courage the Cowardly Dog

All the references loop around this, and this. Finally, here Piotrowski says the non-existence has been proven with a computer calculation around the 80s, and the result is safely stored inside an unpublished paper in German.

Well, thanks to Integer Programming there is now a citable proof :)

Image
Take me back