0
$\begingroup$

My question is a follow up to How to find n points on a plane so that as many pair of points as possible have the same distance? -- see the conjecture at the bottom of this post.



Let $\ n\ $ be a positive integer. Let $\ e(A)\ $ be the maximal cardinality of set $\ P\subseteq\binom A2\ $ such that distance $\ d(x\ y)\ $ is constant over all $\ \{x\ y\}\in P.$

Let $\ D_n\in\binom{\Bbb R^2}n\ $ be such that $$ \forall_{A\in\binom{\Bbb R^2}n}\quad e(D_n)\ge e(A) $$

Set $\ \Delta\subseteq\binom{D_n}2\ $ such that distance $\ d(x\ y)\ $ is constant over all $\ \{x\ y\}\in \Delta\ $ and $\ |\Delta|=e(D_n)\ $ is called critical.

CONJECTURE:  Let $\ n>2.\ $ Let $\ \Delta\in\binom{D_n}2\ $ be critical. Then for every $\ \{x\ y\}\in\Delta\ $ there exists $\ z\in D_n\ $ such that $\ \{x\ z\}\,\text{and}\, \{y\ z\}\,\in\,\Delta.$



I am sure that the following weaker version is indeed true. Namely, only cardinalities $\ e(D_n)\ $ are defined uniquely but not sets $\ D_n.\ $ Thus I am confident that the conjecture is true for at least one $\ D_n\ $ (for every $n$) but -- who knows -- the conjecture fails for some $\ D_n.$

$\endgroup$
1

1 Answer 1

2
$\begingroup$

Following up on Gerry Myerson's suggestion, the following graph from Ágoston and Pálvölgyi's Improved constant factor for the unit distance problem may be a counterexample.

13 vertex graph with counterexample vertex pair

This is the $n=13$ example illustrating the maximum number (30) of unit distances among 13 points in the plane. Schade's 1993 thesis establishes that this is the unique maximal "unit distance graph" for 13 points. Looking at the 3 neighbors of the lefthand marked vertex $x$ and the 5 neighbors of the righthand marked vertex $y$, you can see that there is no vertex $z$ adjacent to both $x$ and $y$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.