6
$\begingroup$

This question has been bugging me since last 3 years.

Prove or disprove that Hoffman Singleton is an unit distance graph in $\mathbb R^2$. For those who are new to unit distance graphs, A graph is said to be unit distance if all its edges are unit length long.

This question just needs good visualization skills and can be even solved by a clever undergrad. Still, it eludes me.

$\endgroup$
7
  • 1
    $\begingroup$ There are known unit-distance embeddings of the Heawood Graph (none particularly nice), the Petersen graph, and the Coxeter graph. Whether the odd-4 graph and the Sylvester Graph are unit-distance is unknown. The existence of HS as unit distance seems unlikely. $\endgroup$
    – Ed Pegg
    Mar 21, 2013 at 20:01
  • $\begingroup$ I also feel that HS doesn't have a unit distance structure. But proving that a graph doesn't have a unit distance structure turns out to be real hard. All I do is search for some forbidden structure like $Q_3-e$, or see if some algebraic property is violated. I have tried with all known constructions of HS for ex. const. But still can't figure it out. And thanks for replying (thought - and been told - this part of maths is dying). Highly appreciate Numb3rs and your works. $\endgroup$
    – user67773
    Mar 22, 2013 at 2:54
  • 1
    $\begingroup$ I thought of using the Hadwiger–Nelson problem 7 coloring of the plane. Toss a UD HS onto it. Then by the pigeonhole principle, at least one color will get 8 vertices. But that's okay, one color could get up to 15 vertices. Can we prove that the UD HS would always cover all 7 colors? $\endgroup$
    – Ed Pegg
    Mar 22, 2013 at 4:00
  • 1
    $\begingroup$ Use the triplets/Fano HS. Then 15 Fanos, 15 triplets with 7, 10 triplets with 6, and 10 other triplets. With 4 heavily overlapping vertices, HS is a unit distance graph in 3-space as a tetrahedron. So... possibly the UD HS would fit into 4 hexagons of the Hadwiger-Nelson 7-coloring of the plane, with a 15-15-10-10 distribution. Can this case be ruled impossible? Any oddities/impossiblities if the hypothetical UD HS is moved around? Also -- we have a boring 3-space embedding (the tetrahedron). Is there an embedding without overlapping vertices? $\endgroup$
    – Ed Pegg
    Mar 22, 2013 at 16:46
  • 1
    $\begingroup$ One idea worth trying -- Build the 3D HS tetrahedron. Let the edges have a range of length .9 to 1.1. Then give the vertices a repulsive force in some sort of modelling program, and see what happens. If it can expand out from a tetrahedron in some way, that new structure may give insight. $\endgroup$
    – Ed Pegg
    Mar 26, 2013 at 18:39

0

Reset to default

You must log in to answer this question.