← All problems

Erdős Problem #1066 — Unit-distance graphs with small independence number

41 years old · traced to

For each positive integer nn, consider every set P⊂R2P\subset\mathbb{R}^2 of nn distinct points such that ∥x−y∥≥1\|x-y\|\geq 1 whenever x,y∈Px,y\in P are distinct. Let G(P)G(P) have vertex set PP, with an edge between xx and yy exactly when ∥x−y∥=1\|x-y\|=1, and write α(G(P))\alpha(G(P)) for its independence number. Define

g(n)=min⁡P⊂R2, ∣P∣=n∥x−y∥≥1 for distinct x,y∈Pα(G(P)).g(n)=\min_{\substack{P\subset\mathbb{R}^2,\ |P|=n\\ \|x-y\|\geq 1\text{ for distinct }x,y\in P}}\alpha(G(P)).

Equivalently, an independent set is a subset of points whose distinct pairwise distances are all strictly greater than 11. The question is to estimate g(n)g(n) and, in particular, to determine the value of lim⁡n→∞g(n)/n\lim_{n\to\infty}g(n)/n. Erdős Problems #1066

Background

Represent each point by a disk of radius 1/21/2 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 n/4n/4. The problem is recorded as originating with Erdős, who initially expected the stronger bound g(n)=n/3g(n)=n/3. Its geometric restriction is significant: the question concerns planar contact graphs arising from equal disks, not arbitrary planar graphs. Erdős Problems #1066

References

Progress summary

Never refreshed

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.