Erdős Problem #1066 — Unit-distance graphs with small independence number
For each positive integer , consider every set of distinct points such that whenever are distinct. Let have vertex set , with an edge between and exactly when , and write for its independence number. Define
Equivalently, an independent set is a subset of points whose distinct pairwise distances are all strictly greater than . The question is to estimate and, in particular, to determine the value of . Erdős Problems #1066
Background
Represent each point by a disk of radius centered there. The separation condition makes the disk interiors disjoint, and edges correspond to tangencies; these contact graphs are planar. Thus the four-colour theorem gives an independent set of size at least . The problem is recorded as originating with Erdős, who initially expected the stronger bound . Its geometric restriction is significant: the question concerns planar contact graphs arising from equal disks, not arbitrary planar graphs. Erdős Problems #1066
References
UnsolvedMath, Erdős Problems set, ULAM AI, licensed CC BY 4.0.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.