Independence number of planar minimum-distance-1 point sets: estimate $g(n)$ and $\lim g(n)/n$ (Erdős #1066)
Statement
Let $P$ be a set of $n$ points in $\mathbb{R}^2$ with all pairwise distances at least $1$, and form the graph $G$ on $P$ that joins two points exactly when they are at distance precisely $1$ (a unit-distance graph; such graphs are always planar). Let $g(n)$ be the largest integer such that every such configuration $P$ contains an independent set of at least $g(n)$ points — that is, a subset of points no two of which are at distance exactly $1$. Estimate $g(n)$, and in particular determine $\lim_{n\to\infty} g(n)/n$ (including whether it exists).
Acceptance. FULLY RESOLVES: determine $\lim_{n\to\infty} g(n)/n$ — prove it exists and give its value — with a complete proof supplying both a family of minimum-distance-1 configurations whose independence ratio tends to the value (matching upper bound on $g$) and a proof that every configuration contains an independent set of the claimed size (matching lower bound). Machine-checkable proof preferred; otherwise a complete written proof. ADVANCES (each independently checkable): (a) improve the upper bound strictly below the best value stated in the background ($\tfrac{5}{16}n$) by exhibiting an explicit minimum-distance-1 point configuration whose independence-number-to-size ratio is smaller than the current record — deliver the coordinates, certify all pairwise distances are $\geq 1$, and certify the exact independence number by exhaustive/ILP computation; (b) improve the lower bound strictly above the best value stated in the background ($\tfrac{8}{31}n$) with a complete (ideally machine-verifiable) proof; or (c) settle the $d$-dimensional question of whether $g_d(n)\gg n/d$. Deliver the configuration + distance/independence certificate, or the improved-bound proof.
Background
Posed by Erdős [Er87b, p.171]; listed as open on erdosproblems.com/1066 (fetched 2026-07-13, status 'open', tagged 'graph theory | planar graphs'). Erdős first guessed $g(n)=n/3$, but Chung–Graham and, independently, Pach gave constructions showing $g(n)\leq\tfrac{6}{19}n$, and Pach–Tóth [PaTo96] improved the upper bound to $g(n)\leq\tfrac{5}{16}n=0.3125n$. On the lower side, Pollack [Po85] observed that the Four Colour Theorem gives $g(n)\geq n/4$ (the graph is planar; Pach noted the theorem is provable by a simple induction for unit-distance graphs). This was improved to $\tfrac{9}{35}n$ by Csizmadia [Cs98] and to $\tfrac{8}{31}n\approx 0.258n$ by Swanepoel [Sw02], so the current record is $\tfrac{8}{31}n\leq g(n)\leq\tfrac{5}{16}n$. Pollack [Po85] also records an Erdős letter posing the $d$-dimensional analogue: with $g_d(n)$ the largest guaranteed subset of pairwise distance $>1$ among $n$ points of $\mathbb{R}^d$ at minimum distance $1$, is $g_d(n)\gg n/d$? (The matching upper bound $g_d(n)\ll n/d$ is trivial via widely spaced unit simplices.) See also Erdős #1070 (erdosproblems.com/1070) on the independence number of general unit-distance graphs. There is no Erdős prize on this problem. Attacker's tool: computer construction and search — build explicit minimum-distance-1 planar configurations (e.g. triangular-lattice patches) whose independence ratio beats $\tfrac{5}{16}$ to lower the upper bound, computing the exact independence number by ILP/exhaustive search and certifying pairwise distances; and machine-assisted discharging/weighting arguments to raise the lower bound above $\tfrac{8}{31}$.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1066 (T. F. Bloom) | website |
| REF-02 | Erdős Problem #1070 — independence number of general unit-distance graphs | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.