About a graph embedding from R^3 to... - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T19:17:14Z http://mathoverflow.net/feeds/question/109401 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/109401/about-a-graph-embedding-from-r3-to About a graph embedding from R^3 to... Cosmin Pohoata 2012-10-11T18:04:12Z 2012-10-12T06:31:24Z <p>I was working on something and stumbled upon the following situation. I have in front of me a configuration \$L\$ of lines in \$\mathbb{R}^{3}\$ and say I consider the graph \$G\$ having as vertex set \$L\$ with an "edge" between two lines \$l_{i}\$ and \$l_{j}\$ if they interesect (again, in \$\mathbb{R}^{3}\$). Consequently, if we have such an edge, we can associate with it the plane determined by the lines \$l_{i}\$ and \$l_{j}\$. Now, note that these "edges", as planes, have the special property that every two of them intersect exactly once. Thus, what I'm trying to do is embed this graph in \$\mathbb{R}^{2}\$ or on a surface to get a new graph \$G'\$, isomorphic with \$G\$, which is a so-called "thrackle", i.e. it has points as vertices, and they are joined by Jordan arcs or maybe some algebraic curves, so that every two such edges/arcs intersect exactly once. Can I do this?</p> <p>Any insight is more than welcomed! :)</p> http://mathoverflow.net/questions/109401/about-a-graph-embedding-from-r3-to/109435#109435 Answer by Greg Price for About a graph embedding from R^3 to... Greg Price 2012-10-12T06:31:24Z 2012-10-12T06:31:24Z <p>No. Say \$L\$ consists of \$n\$ lines, all concurrent but no three coplanar. Then \$G\$ is the complete graph on \$L\$, isomorphic to \$K_n\$. But for \$n>3\$, \$K_n\$ has no thrackle. For example, <a href="http://www.ams.org/mathscinet-getitem?mr=1476318" rel="nofollow">Lovász, Pach, and Szegedy</a> showed that a thrackle on \$n\$ vertices has at most \$2n-3\$ edges.</p>