Wolfram Demonstrations Project

13,000+ Open Interactive Demonstrations
Powered by Notebook Technology »

The Packing Chromatic Number Is 15

Initializing live version
Download to Desktop

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

On a square lattice, place 1s so that all 1s have a taxicab distance greater than 1 from each other. Next, add 2s so that the 2s all have a taxicab distance greater than 2 from each other. And so on. If the entire square lattice is filled with values, what is the maximal value in the lattice?

[more]

The taxicab distance between two points and is .

This problem is known as the packing chromatic number of the infinite square lattice. It turns out the answer is 15. This Demonstration shows that the upper bound of 15 works in a grid, as seen in [1]. In a subsequent paper [2], the lower bound was proven to be 15.

You can select a value using the slider.

The display options are "numbers", a grid of numbers; "lattice", a grayscale version of the numbers; and "circles", with circles around the chosen values.

[less]

Contributed by: Ed Pegg Jr (June 13)
Open content licensed under CC BY-NC-SA

Details

References

[1] B. Martin, F. Raimondi, T. Chen and J. Martin, "The Packing Chromatic Number of the Infinite Square Lattice Is between 13 and 15." arxiv.org/abs/1510.02374.

[2] B. Subercaseaux and M. J. H. Heule, "The Packing Chromatic Number of the Infinite Square Grid Is 15." arxiv.org/abs/2301.09757.

Snapshots

Embed Code

Take advantage of the Wolfram Notebook Emebedder for the recommended user experience.

Related Demonstrations More by Author
Browse all topics
Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send