Chromatic numbers for contact graphs of mutually congruent cuboids

Abstract: Motivated by a wireless channel assignment problem, Reed & Allwright proved that there is no upper bound for the chromatic numbers of contact graphs for general cuboids in Euclidean space, even when all corners fall in the integer lattice. If one dimension of the cuboids is restricted to be 1, the cuboids will be layered, and consequently the four color theorem shows that 8 colors suffice. This bound is tight by work of Bessy, Goncalves and Sereni.

We will study the situation when all cuboids must be mutually congruent, with a particular interest in what happens in cases when the rigid motion is required to preserve one or several of the directions of the cuboids. We can provide non-trivial upper and lower bounds for the maximally occuring chromatic numbers in many cases, but only in a few instances we are able to determine these numbers fully. Our most satisfying result, obtained recently with Rasmus Veber Weis Rasmussen, is the fact that for 2x1x1 cuboids with the long side restricted to the XY plane, the maximal chromatic number becomes exactly 5. We have only managed to show that 5 colors are necessary after a pointed computer search resulting in a large cuboid structure requiring 5 colors.

This problem has been used as a case study in a course "Experimental Mathematics” taught in Copenhagen for more than a decade, and as I will detail, much of what I know has been taught to me by students. My initial motivation came from outreach activities associated to LEGO bricks, and I will say a few words about that too.

computational geometrydiscrete mathematicscommutative algebracombinatorics

Audience: researchers in the topic

Copenhagen-Jerusalem Combinatorics Seminar

Series comments: There is a mailing list for talk announcements. If you want to receive the announcements, send an e-mail to the organizer to subscribe to the mailing list.

The password for the zoom room is 123456