Skip to content

Erdős Problem #1066

Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
Snapshot classification: open (not automatically the live result).
Subject areas: graph theory, planar graphs.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

UNACCEPTED DRAFT — mathematical editorial review pending

This material is a provisional, source-qualified manuscript published for line-by-line scrutiny and real HTML/LaTeX testing. It has NOT received separate GCL editorial acceptance or independent mathematical certification. Its presence on this website is not evidence of a solution, reviewed coverage, or final publication.

Review the underlying draft on GitHub.

The question in plain language

Place \(n\) points in the plane so that no pair is less than unit distance apart. Connect two points when they are exactly unit distance apart. We obtain a graph whose independent sets are collections of points with all mutual distances greater than \(1\).

Let \(g(n)\) be the largest number of vertices guaranteed to be independent, regardless of the permitted point arrangement. Erdős Problem #1066 asks for the true growth of \(g(n)\) and possibly the limiting ratio \(g(n)/n\).

A small example

An equilateral triangle of side length \(1\) gives the complete graph \(K_3\). Every pair of its three points is connected, so its largest independent set has size \(1\). Put two such triangles far apart, making every cross-triangle distance greater than \(1\). The resulting six-point graph consists of two disjoint triangles and has independence number \(2\). Thus \(g(6)\le2\).

Repeating this construction shows \(g(3m)\le m\) for all positive \(m\). This is an elementary finite construction, not a sharp asymptotic upper bound.

What is known

Unit-distance graphs subject to minimum pairwise separation are planar, so the four-colour theorem guarantees an independent set of size at least \(\lceil n/4\rceil\). The maintained catalogue reports stronger results: Swanepoel's bound of \(8n/31\) below and the Pach–Tóth construction of \(5n/16\) above, with suitable interpretation of integer rounding:

\[ \frac{8n}{31}\le g(n)\le\frac{5n}{16}. \]

The published asymptotic coefficients and their hypotheses come from external research; their complete proofs have not yet been independently replayed by GCL. The optimal asymptotic fraction remains undetermined.

GCL's current state

Authenticated source audit #2337 identifies the geometric definition, reports the original and later literature, and verifies the equilateral-triangle example. Unlike some neighboring problems, #1066 does not have a statement in the pinned admitted formal-conjectures provider snapshot. Formal metadata must therefore not substitute for original mathematical statement capture.

What remains

The mathematical goal is to tighten the asymptotic bounds or determine the limiting fraction. The source-fidelity task is to hash-lock the relevant Erdős, Pach–Tóth and Swanepoel texts, check their exact constructions and hypotheses, and separate general planar-graph reasoning from special properties of minimum-separation unit-distance graphs.

Sources and claim boundaries

  • Erdős Problem #1066, maintained question and reference list.
  • Pach and Tóth (1996), published upper-bound construction; precise source page still under review.
  • Swanepoel (2002), improved lower bound; proof not independently reproduced here.
  • Authenticated GCL audit #2337, elementary geometry and source review, not proof certification or editorial admission.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #2337 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: STATEMENT_CAPTURE_REQUIRED.
  • Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction