ISSN 2148-838Xhttps://doi.org/10.13069/jacodesmath.1000784 J. Algebra Comb. Discrete Appl. 8(3) • 161–166 Received: 04 August 2020 Accepted: 31 March 2021 Journal of Algebra Combinatorics Discrete Structures and Applications Finite �-unit distance graphs Research Article Mike Krebs Abstract: In 2005, Exoo posed the following question. Fix � with 0 ≤ � < 1. Let G� be the graph whose vertex set is the Euclidean plane, where two vertices are adjacent iff the Euclidean distance between them lies in the closed interval [1 − �,1 + �]. What is the chromatic number χ(G�) of this graph? The case � = 0 is precisely the classical “chromatic number of the plane” problem. In a 2018 preprint, de Grey shows that χ(G0) ≥ 5; the proof relies heavily on machine computation. In 2016, Grytczuk et al. proved a weaker result with a human-comprehensible but nonconstructive proof: whenever 0 < � < 1, we have that χ(G�) ≥ 5. (This lower bound of 5 was later improved by Currie and Eggleton to 6.) The De Bruijn - Erdős theorem (which relies on the axiom of choice) then guarantees the existence, for each �, of a finite subgraph H� of G� such that χ(H�) ≥ 5. In this paper, we explicitly construct such finite graphs H�. We find that the number of vertices needed to create such a graph is no more than 2π(15 + 14�−1)2. Our proof can be done by hand without the aid of a computer. 2010 MSC: 05C15, 05C10 Keywords: Chromatic number of the plane, �-unit distance graph 1. Introduction The much-studied “chromatic number of the plane” problem asks for the smallest number of colors needed to color every point in the plane in such a way that no two points of unit distance apart from each other have the same color. One can easily think of this as a graph coloring problem by forming a graph G0 whose vertex set is R2, where two vertices p and q are adjacent if and only if d(p,q) = 1. What is χ(G0)? Here d(p,q) denotes the Euclidean distance from p to q, and χ(G) denotes the chromatic number of a graph G. The best known bounds are 5 ≤ χ(G0) ≤ 7. (1) The book [7] thoroughly details the history of this problem up to 2009. For many decades the best- known lower and upper bounds were 4 and 7, respectively. The lower bound of 5 was first proved in Mike Krebs; Department of Mathematics, California State University - Los Angeles, 5151 State University Drive, Los Angeles, California 90032, USA (email: mkrebs@calstatela.edu) 161 https://orcid.org/0000-0002-5097-2647 M. Krebs / J. Algebra Comb. Discrete Appl. 8(3) (2021) 161–166 [4], in which de Grey explicitly constructs a finite unit-distance graph that cannot be properly 4-colored. Unfortunately, the proof requires extensive machine computation. In [2], Exoo formulates the following variation on this problem. Let � be a real number with 0 < � < 1, and let G� be the graph whose vertex set is R2, where two vertices p and q are adjacent if and only if 1− � ≤ d(p,q) ≤ 1 + �. We now seek χ(G�). One immediately has the inequality χ(G0) ≤ χ(G�), and so by (1) we have that χ(G�) ≥ 5 for all � > 0. Exoo conjectures that in fact χ(G�) = 7 for all �. In [2], Exoo shows that χ(G�) is finite whenever 0 < � < 1. In [5], Grytczuk et al. prove that whenever 0 < � < 1, we have that χ(G�) ≥ 5. (We note that the stronger result χ(G�) ≥ 6 was proved in [1].) Their proof is indirect and nonconstructive; in Section 2, we present a simplified version of their (rather elegant) proof. The classical De Bruijn - Erdős theorem states that any graph K with finite chromatic number ` must possess a finite subgraph with chromatic number `. This theorem depends on the axiom of choice. Following [2], we define an �-unit distance graph to be a subgraph of G�. (This mirrors the use of the term unit distance graph to refer to a subgraph of G.) Together, the three theorems mentioned in this paragraph imply the existence, for each �, of a finite �-unit distance graph H� with χ(H�) ≥ 5. In Section 3, we present our main theorem (Theorem 3.2), which gives an explicit construction of finite �-unit distance graphs H� with χ(H�) ≥ 5. We thereby obtain an upper bound of 2π(15+14�−1)2 for the number of vertices in H�. This upper bound is O(n2), where � = n−1 and n ranges over the positive integers. The results of this paper and of [5] are, of course, inferior to de Grey’s landmark theorem, but to their credit the proofs do not require machine computation. It would be tempting to use some sort of limiting argument, letting � → 0 in the inequality χ(G�) ≥ 5, to try to obtain a proof (one that does not require computer assistance) that χ(G0) ≥ 5. The following example illustrates the difficulties in such a line of attack. Let J be the graph whose vertex set is R, where two vertices p and q are adjacent if and only if |p − q| = 1. Note that χ(J) = 2, because the mapping x 7→ bxc modulo 2 is a proper 2-coloring of J. Here bxc denotes the largest integer less than or equal to x. Whenever 0 < � < 1, let J� be the graph whose vertex set is R, where two vertices p and q are adjacent if and only if 1−� ≤ |p−q| ≤ 1 +�. For any �, let n be a positive integer such that n−1 ≤ �. Then J� has a (2n + 1)-cycle with vertices 0,1 + n−1,2(1 + n−1), . . . ,(n−1)(1 + n−1),n + 1,n,n−1,n−2, . . . ,2,1. It follows that χ(J�) ≥ 3. 2. A lower bound of 5 for the chromatic number of G� We begin by establishing a basic lemma that will be used twice later on. Given a coloring of a graph, we say that a set of three distinct vertices is a monochromatic triangle if any two of them are adjacent to each other (that is, they induce a complete graph K3), and they all have the same color. Lemma 2.1. Let G be a graph. Suppose that for any 2-coloring of G, there is a monochromatic triangle in G. Then χ(G) ≥ 5. Proof. Assume that there is a proper 4-coloring c: V (G) →{1,2,3,4} of G. Define c′ : V (G) →{1,2} by c′(v) = 1 if c(v) ∈{1,2} and c′(v) = 2 if c(v) ∈{3,4}. Then G has a monochromatic triangle {p,q,r} with respect to c′. But then {p,q,r} uses only two colors from the coloring c, which is impossible. The fact that χ(G�) ≥ 5 for all � > 0 appears as Theorem 2 in [5]. The proof given in [5] invokes Theorem 2 from [6], from which the desired bound follows quickly. In fact, a less powerful tool—namely, a special case of Theorem 1 from [6]—suffices. We present here a slightly simplified proof. We do so not only to keep this paper more self-contained but also to motivate the idea of the proof of our main theorem in Section 3. 162 M. Krebs / J. Algebra Comb. Discrete Appl. 8(3) (2021) 161–166 Theorem 2.2 ([5], Theorem 2). Let � be a real number such that 0 < � < 1. Then χ(G�) ≥ 5. Proof. Partition R2 into two sets W and B. Vertices in W we call white; those in B we call black. By Lemma 2.1, it suffices to show that either W or B contains a monochromatic triangle. This clearly holds if either W = R2 or B = R2, so assume that W and B are both proper and nonempty. Because R2 is connected in the Euclidean topology, W has a boundary point p. Then there exists a point q with d(p,q) ≤ �/2 such that p and q have opposite colors. Let C be the circle of radius 1 with center p. If C ⊂ W or C ⊂ B, then the points p + (1,0) and p + (1/2, √ 3/2), together with either p or q, form a monochromatic triangle. Otherwise, because C is connected as a topological subspace of R2, it follows that W has a boundary point r with r ∈ C. Then there exists a point s with d(r,s) ≤ �/2 such that r and s have opposite colors. Choose a point t of distance 1 from both p and r. Then t shares a color with one of p and q and one of r and s; these three points form a monochromatic triangle. 3. Finite �-unit distance graphs with chromatic number ≥ 5 Carefully reading the proof of Theorem 2.2, we see that we do not require the full power of the point p being in the boundary of W . For we do not need to find points of color opposite to that of p arbitrarily close to p; we need only find a single such point of distance ≤ �/2 from p. The same goes for r. This observation allows us to discretize the argument, replacing topological connectedness with graphical connectedness. We now make this precise. Lemma 3.1. Let H and L be graphs with a common vertex set V such that |V | ≥ 2. Suppose that L is connected. Moreover, suppose that for any two L-adjacent vertices x and y, there exists a connected induced subgraph J of L with order ≥ 2 such that: 1. Every vertex in J is H-adjacent to both x and y, and 2. Whenever a and b are L-adjacent vertices in J, there exists a vertex z of J such that z is H-adjacent to both a and b. Then χ(H) ≥ 5. Proof. Partition V into two sets W and B, as in the proof of Theorem 2.2. By Lemma 2.1, it suffices to show that either W or B contains a monochromatic triangle with respect to H. If V ⊂ W or V ⊂ B, then we are done, because H contains K3 as a subgraph. So assume that W and B are both proper and nonempty. Because L is connected, there must be two L-adjacent vertices x and y of opposite colors. Take J as in the statement of the lemma. First suppose that J ⊂ W . Because J is a connected induced subgraph of L with order ≥ 2, we know that there exist L-adjacent vertices a and b in J. Let z be as in (2). Then z, a, and one of x and y form a monochromatic triangle with respect to H. A similar argument works if J ⊂ B. So we now assume that J contains both black and white points. Because J is a connected induced subgraph of L with order ≥ 2, it follows that there exist L-adjacent vertices a and b in J of opposite color. Let z be as in (2). Figure 1 illustrates the situation. Then z, one of a and b, and one of x and y form a monochromatic triangle with respect to H. Theorem 3.2. Let � be a real number such that 0 < � < 1. Let s = � 14 √ 2 . Let V = {(as,bs) | a,b ∈ Z and (as)2 + (bs)2 ≤ (1 + �)2}. Define H� to be the graph with vertex set V where two vertices p and q are adjacent if and only if 1− � ≤ d(p,q) ≤ 1 + �. Then χ(H�) ≥ 5. Moreover, H� has no more than 2π(15 + 14�−1)2 vertices. 163 M. Krebs / J. Algebra Comb. Discrete Appl. 8(3) (2021) 161–166 Figure 1. The points x,y,a,b, and z. Edges are solid in L, dashed in H. Proof. Let L be the graph with vertex set V where two vertices p and q are adjacent if and only if 0 < d(p,q) ≤ 4�/7. We will show that H� and L satisfy the conditions of Lemma 3.1. The set V contains the points (0,0) and (s,0), so |V | ≥ 2. Note that L is connected, for the following reason: If b > 0, then (as,bs) is L-adjacent to (as,(b−1)s). If b < 0, then (as,bs) is L-adjacent to (as,(b + 1)s). If a > 0, then (as,0) is L-adjacent to ((a− 1)s,0). And if a < 0, then (as,0) is L-adjacent to ((a + 1)s,0). So we can find a path in L from any vertex to (0,0) by first traveling vertically until we reach the x-axis, then moving horizontally until we reach the origin. Given two L-adjacent vertices x and y, we now construct an induced subgraph J with the properties required in Lemma 3.1. Take x = (as,bs). Without loss of generality, we may assume that x 6= (0,0). Let p1 be the unique point of distance 1 from x such that p1 lies on the ray from x to (0,0). For any point q in the plane other than x, let α(q) be the signed measure of the angle ∠qxp1. Let p2 and p3 be the unique points in the plane of distance 1 from x such that α(p2) = −π/3 and α(p3) = π/3. Let A be the arc, running from p2 to p3, of the circle of radius 1 centered at x. Note that A subtends an angle of 2π/3. To construct J, the essential idea is to find a set of vertices of V that discretely approximates A. We now make this precise. Let O = (0,0). Let B(O,1 + �) be the open disk of radius 1 + � centered at (0,0). Observe that if an open disk D of radius �/7 is contained in B(O,1 + �), then D contains an element of V . (The value of s was chosen for this reason. Indeed, we could have taken s to be any positive real number less than � 7 √ 2 .) Let Q be any point on the arc A. Applying the Law of Cosines to the triangle QxO, we find that (1 + �) − d(Q,O) > �/7. Thus the open disk of radius �/7 centered at Q is contained in B(O,1 + �). Cover A with finitely many open disks of radius �/7, each centered at a point of A. For each disk in this covering, choose an element of V . Let J be the subgraph of L induced by this collection of elements, as shown in Figure 2. The union of two intersecting disks of radius �/7 has diameter no greater than 4�/7. This fact, together with the fact that the disks used to define J cover A, imply that J is connected. We have that d(p1,p2) = 1. Let v1,v2 be vertices of J such that d(v1,p1) < 2�/7 and d(v2,p2) < 2�/7. Hence v1 6= v2, so J contains at least two distinct vertices. Let v be any vertex of J. Then there is some point q ∈ A such that d(v,q) < �/7. Hence 1− � < 1− �/7 < d(x,v) < 1 + �/7 < 1 + �, so x and v are H�-adjacent. Then using that d(x,y) < 4�/7, together with triangle inequality, we see that y and v are also H�-adjacent. Finally, let a and b be L-adjacent vertices in J. We know that there is some point q ∈ A such that d(a,q) < �/7. Because A subtends an angle of 2π/3, there exists a point r ∈ A such that d(q,r) = 1. (To find r, move either clockwise or counterclockwise along A by an angle of π/3.) Let z be a vertex of 164 M. Krebs / J. Algebra Comb. Discrete Appl. 8(3) (2021) 161–166 Figure 2. Construction of J J with d(r,z) < 2�/7. Then 1 − 3�/7 ≤ d(a,z) ≤ 1 + 3�/7, so a and z are H�-adjacent. The fact that d(a,b) ≤ 4�/7 then implies that b and z are H�-adjacent, too. Therefore, by Lemma 3.1, we have that χ(H�) ≥ 5. Estimating |H�| (the number of vertices in H�) is essentially the Gauss circle problem. We obtain the simple upper bound in the statement of the theorem via a standard method. For each vertex (as,bs) in H�, consider the square with vertices (as,bs),((a+1)s,bs),(as,(b+1)s),((a+1)s,(b+1)s). The union U of all such squares has area |H�|s2. But U is contained in the disk of radius 1 + � + s √ 2 centered at the origin, so |H�|s2 ≤ π(1 + � + s √ 2)2. From this we get that |H�| ≤ 2π(15 + 14�−1)2. We remark that the graph H� cannot be realized as a unit distance graph, because it contains a complete bipartite graph K2,3 as a subgraph. Indeed, no graph H satisfying the conditions of Lemma 3.1 is a unit distance graph, for the same reason: The vertices a,b in the statement of the lemma have x,y, and z as common neighbors, but in a unit distance graph two distinct vertices can have no more than 2 common neighbors. 4. Future directions Many possible approches to the chromatic number of the plane problem remain to be investigated. Denote by χc(R2) the “closure chromatic number of the plane,” that is, the smallest number of sets into which R2 can be partitioned such that the closure of none of these sets contains two points of distance 1 from each other. Nielsen’s argument (the proof of Theorem 2.2) shows that χc(R2) ≥ 5. Does the argument in [1] show that χc(R2) ≥ 6? More generally, if χ(G�) ≥ k for all � > 0, does this imply that χc(R2) ≥ k? We remark Nielsen’s argument holds for any topology in which every unit circle (and hence the entire plane) is connected. The definition of χc(R2) extends to arbitrary topologies. If χc(R2) ≤ k for every 165 M. Krebs / J. Algebra Comb. Discrete Appl. 8(3) (2021) 161–166 topology in some suitable collection of topologies on R2, does this imply that χ(R2) ≤ k? The closure chromatic number of the plane is related to the “measurable chromatic number of the plane,” denoted χm(R2), which equals the smallest number of Lebesgue measurable sets into which R2 can be partitioned such that none of these sets contains two points of distance 1 from each other. In [3], Falconer showed that χm(R2) ≥ 5 — yet another result superseded by [4]. The fact that χm(R2) ≤ χc(R2) follows immediately from the facts that closed sets are measurable and that the set difference of measurable sets is measurable. It may be worth looking into whether the arguments of Nielsen or of Currie and Eggleton shed any light on further connections between χc(R2) and χm(R2). In Section 1, we discussed the difficulties in simply taking the limit of the chromatic numbers as � → 0. We can view this set-up as starting with too many edges (those that correspond to distances 6= 1), then gradually removing edges until we are left only with those edges we wish to keep (those that correspond to distance 1). One way to rectify the situation is to instead start with too few edges, then gradually add edges until all desired edges appear. The corresponding limit-of-the-chromatic numbers argument will go through in this case. For example, rather than expand the set of allowable distances, we can contract the set of allowable angles, perhaps as follows. Let θ ∈ [0,π/2). Given two distinct points p and q in R2, let ` be the line that contains both. We declare p and q to be adjacent if and only if the distance between them is 1 and 0 ≤ α ≤ θ, where α is the unique angle ≤ π/2 formed by ` and the x-axis. Then the chromatic number of the plane equals the limit as θ → π/2 of the chromatic number of the “angle-restricted graph” corresponding to θ. Acknowledgment: The author would like to thank the referee for many helpful suggestions. References [1] J. D. Currie and R. B. Eggleton, Chromatic properties of the Euclidean plane, arXiv:1509.03667 11 Sep 2015. [2] G. Exoo, �-unit distance graphs, Discrete Comput. Geom. 33(1) (2005) 117-123. [3] K. J. Falconer, The realization of distances in measurable subsets covering Rn, J. Combin. Theory Ser. A 31(2) (1981) 184-189. [4] A. D. de Grey, The chromatic number of the plane is at least 5, Geombinatorics 28(1) (2018) 18–31. [5] J. Grytczuk, K. Junosza-Szaniawski, J. Sokół, K. Węsek, Fractional and j-fold coloring of the plane, Discrete Comput. Geom. 55(3) (2016) 594-609. [6] M. J. Nielsen, Approximating monochromatic triangles in a two-colored plane, Acta Math. Hungar. 74(4) (1997) 279-286. [7] A. Soifer, The mathematical coloring book, Springer, New York (2009). 166 https://arxiv.org/abs/1509.03667 https://arxiv.org/abs/1509.03667 https://doi.org/10.1007/s00454-004-1092-8 https://doi.org/10.1016/0097-3165(81)90014-5 https://doi.org/10.1016/0097-3165(81)90014-5 https://doi.org/10.1007/s00454-016-9769-3 https://doi.org/10.1007/s00454-016-9769-3 https://doi.org/10.1023/A:1006520219668 https://doi.org/10.1023/A:1006520219668 Introduction A lower bound of 5 for the chromatic number of G Finite -unit distance graphs with chromatic number 5 Future directions References