Coloring matrix 17х17 in four colors without monochromatic rectangles
What is surprising about this picture?
In fact, it is unique. A matrix of 17 x 17 in size is painted in four colors, while it is impossible to construct a single (!) Rectangle on it so that all its corners are the same color. This refers to rectangles of any size with vertices at different points and edges parallel to the x and y axes.
For comparison, if you replace the color in any cell, then immediately appears a lot of monochromatic rectangles. For example, if the color of the upper left cell is changed from blue to red.
')
Similarly, if you change one random cell from the middle.
This task from the field of combinatorial analysis was put on November 20, 2009 by William Gasarch of the Clay Mathematical Institute, who previously published the fundamental work on coloring matrices, and proved in it that colors of almost all sizes are colored by four colors without multi-chromatic rectangles. Only a few sizes remained unknown in his table : 17x17, 18x18 and 12X21.
Mathematicians Brand Berin Steinbach from the Institute of Computer Science at the Technical University of the Freiberg Mining Academy (Germany), and Christian Posthoff (Christian Posthoff), a former employee of the Computer and Information Technology Department of the University of the West Indies (Trinidad and Tobago), managed to color the graph 17x17 four flowers without a single monochromatic rectangle! Moreover, they also managed to paint a 18x18 matrix. Thus, the only unresolved format for today is 21x12.
The results of the "Most Complex Four-Colored Rectangle-free-Grids - Solution of an Open Multiple-Valued Problem" and the Steinbach-Posthoff algorithm will be published at the International Symposia on Multiple-Valued Logic on May 14, 2012 in Victoria (Canada).
Note that coloring graphs is of great practical importance and is used in scheduling, register allocation in microprocessors, cache distribution of executable code, radio frequency distribution to maximize channel capacity and minimize interference, parallelizing numerical methods, calculating derivatives, digital watermarks, cluster analysis and many other areas.
In fact, it is unique. A matrix of 17 x 17 in size is painted in four colors, while it is impossible to construct a single (!) Rectangle on it so that all its corners are the same color. This refers to rectangles of any size with vertices at different points and edges parallel to the x and y axes.
For comparison, if you replace the color in any cell, then immediately appears a lot of monochromatic rectangles. For example, if the color of the upper left cell is changed from blue to red.
')
Similarly, if you change one random cell from the middle.
This task from the field of combinatorial analysis was put on November 20, 2009 by William Gasarch of the Clay Mathematical Institute, who previously published the fundamental work on coloring matrices, and proved in it that colors of almost all sizes are colored by four colors without multi-chromatic rectangles. Only a few sizes remained unknown in his table : 17x17, 18x18 and 12X21.
Mathematicians Brand Berin Steinbach from the Institute of Computer Science at the Technical University of the Freiberg Mining Academy (Germany), and Christian Posthoff (Christian Posthoff), a former employee of the Computer and Information Technology Department of the University of the West Indies (Trinidad and Tobago), managed to color the graph 17x17 four flowers without a single monochromatic rectangle! Moreover, they also managed to paint a 18x18 matrix. Thus, the only unresolved format for today is 21x12.
The results of the "Most Complex Four-Colored Rectangle-free-Grids - Solution of an Open Multiple-Valued Problem" and the Steinbach-Posthoff algorithm will be published at the International Symposia on Multiple-Valued Logic on May 14, 2012 in Victoria (Canada).
Note that coloring graphs is of great practical importance and is used in scheduling, register allocation in microprocessors, cache distribution of executable code, radio frequency distribution to maximize channel capacity and minimize interference, parallelizing numerical methods, calculating derivatives, digital watermarks, cluster analysis and many other areas.
Source: https://habr.com/ru/post/138076/
All Articles