A Finite Graph Approach to the Probabilistic Hadwiger-Nelson Problem

2020/08/18 by Haydn Gwyn, Gwyn, Haydn, Jacob Stavrianos +1
Computer Science · Economics, Econometrics and Finance · Mathematics · #05C15 #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Game Theory and Voting Systems #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2008.07987

openalex publication_date 2020/08/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We advance a probabilistic approach to the Hadwiger-Nelson problem initially developed by the Polymath16 project, in particular relating the approach to finite unit-distance graphs. We define the numerical badness of a given k-coloring of the plane to be the probability that a randomly chosen unit-distance edge is monochromatic under the coloring, and we provide lower bounds on the badness of arbitrary k-colorings using a probabilistic technique relating to finite graphs. The contrapositive of the resulting bounds lets us compute lower bounds on the order of non k-colorable unit-distance graphs, improving bounds produced by Pritikin and the Polymath16 project in the k = 4 and k = 5 cases. Additionally, we make partial progress on a probabilistic analog of the de Bruijn-Erdős compactness theorem.

Related

• A probabilistic Hadwiger-Nelson problem
• A Probabilistic Approach to Problems on Distance Graphs and Graphs of Diameters (Candidate-Degree Dissertation Author's Review, in Russian)
• The chromatic number of the plane is at least 5
• An algorithmic framework for obtaining lower bounds for random Ramsey\n problems
• A conditional approach for monochromatic unit distance in a plane for four and five coloring