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 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 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>