Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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. –  Ed Pegg Mar 21 '13 at 20:01
    
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. –  Uma kant Mar 22 '13 at 2:54
1  
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? –  Ed Pegg Mar 22 '13 at 4:00
1  
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? –  Ed Pegg Mar 22 '13 at 16:46
1  
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. –  Ed Pegg Mar 26 '13 at 18:39
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.