Erdős Problem a Daythe open tracker
The board / graph theory / #1066

Erdős Problem #1066

OPENdatabase updated 2025-10-01

No proof or disproof is known, and it isn't known whether a finite computation could settle it.

What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).

\(g(n)\): the largest \(m\) such that, for every set \(X\) of \(n\) points of \(\mathbb{R}^2\) with any two distinct points at distance at least \(1\), the graph on \(X\) joining points at distance exactly \(1\) has an independent set with at least \(m\) vertices. The set of such \(m\) contains \(0\) and is bounded by \(n\), so `sSup` is a true maximum.

\(g_d(n)\): the largest \(m\) such that every set \(X\) of \(n\) points of \(\mathbb{R}^d\) with any two distinct points at distance at least \(1\) contains at least \(m\) points with pairwise distances greater than \(1\). For \(d \geq 1\) the set of such \(m\) contains \(0\) and is bounded by \(n\), so `sSup` is a true maximum.

Let \(G\) be a graph given by \(n\) points in \(\mathbb{R}^2\), where any two distinct points are at least distance \(1\) apart, and we draw an edge between two points if they are distance \(1\) apart. Let \(g(n)\) be maximal such that any such graph always has an independent set on at least \(g(n)\) vertices. Estimate \(g(n)\), or perhaps \(\lim \frac{g(n)}{n}\). We ask for \(\lim g(n)/n\). The limit exists by Fekete's lemma, since placing two configurations far apart shows \(g(a+b) \leq g(a)+g(b)\).
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open · 4 further variants / known partial results in the Lean file. The authoritative wording is on erdosproblems.com/1066.
Prizenone
Topicsgraph theory, planar graphs
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/1066

Attempts

submit one →
WORKING REPORT BY THIS SITE · JUL 29, 2026

Read our working report →

Live page status is OPEN with 0 claimed proofs, but “Currently working on this problem” lists Tomodovodoo (accessed 2026-07-29); the mandatory collision-avoidance rule requires stopping.

SKIPPED
← #1065the board#1067 →