I'm looking at embeddings of the Heawood graph in the plane as unit distance graph. Apparently the first such embedding was given by Gerbracht, 2009 and has algebraic (over the rationals) coordinates of maximum degree $79$ . I thought it would be nice to have an embedding that also realizes at least one of the $336$ symmetries of the graph.
If we add the symmetry given by mirroring on the central vertical line (on the drawing on the top left), we get a system where the number of equations is one less than the number of variables. When adding one additional constraint we can find pretty solutions, for example:
- Adding $x_3+x_5=0$, pic top right, solutions of max degree $3$
- Adding $x_1+x_{11}=0$, pic bottom left, solutions of max degree $21$
- Adding $x_8+x_{10}=0$, pic bottom right, solutions max degree $36$
Here $x_i$ denote coordinates of the $x$-axes and the solutions files provide numerical solutions up to $50$ digits of the algebraic number together with their minimal polynomials.
The embedding 1. has the lowest degree, but is not a faithful unit distance graph, since the non-edge $(1,12$) has distance $1$. (The other two embeddings are faithful). For embedding 3. the algebraic coordinates are of degree $36$, but all the corresponding minimal polynomials are even, hence the coordinates are all square roots of algebraic numbers of maximum algebraic degree $18$. If we respect one symmetry, there seems to be a continuous family of embeddings and I wonder whether we can find an embedding with algebraic degree lower than $21$, perhaps choosing the additional constraint in a clever way.
What is the minimal algebraic degree of a (symmetric) (faithful) unit distance embedding of the Heawood graph?
By "algebraic degree" of an embedding with all cordinates being algebraic over the rationals of some degree, I mean the maximum of all of those degrees.
I'm interested in the faithful and the non-faithful version of this question and also the non-symmetric case, but only the unit distance embeddings, where vertices are not mapped to on other vertices or edges. It is not even clear to me that rationals would be impossible (which would be easy to prove if the chromatic number of the graph would be $3$ and not $2$.)
