5
$\begingroup$

Sorry if the terminology's wrong, I don't know differential topology. Also, this is more of a brain-teaser than a bona fide research question, but it's hopefully a "real mathematician"-level brain-teaser.

So the crossing number inequality gives a lower bound for how many intersections you have to have if you draw a graph with enough edges in the plane. The thing is, the crossing number inequality counts intersections "with multiplicity." It's pretty easy to see that if you don't count intersections with multiplicity, you can draw any finite graph in the plane with only one "crossing point."

However, while there's an easy explicit description of such a drawing, the edges aren't smooth (or even first-differentiable!) So my question is in two parts:

  1. Is there a drawing of K_n in the plane such that there is exactly one point where edges can intersect, and all edges are smooth embeddings of the (open) unit interval in R^2?

  2. Is there an explicit description of such a drawing? (E.g., can you write the edges as real algebraic curves?)

(Note to moderators: you might want to tag this as "recreational" or "brain-teaser" or something of that sort; I don't have 250 reputation and so can't. :-/)

Improve this question
$\endgroup$
3
  • $\begingroup$ This seems like a perfectly reasonable question to me. It's not particularly "recreational." I wouldn't worry so much about defending your question. $\endgroup$
    – Noah Snyder
    Commented Oct 18, 2009 at 23:00
  • $\begingroup$ @Noah: I think what I meant by "recreational" was that it didn't arise so much from Serious Thinking about a Serious Problem as from saying "oh, hey, this problem's cool!" $\endgroup$
    – Harrison Brown
    Commented Oct 18, 2009 at 23:01
  • 1
    $\begingroup$ But lots of math is done because someone thinks "oh, hey, this problem is cool" $\endgroup$
    – Theo Johnson-Freyd
    Commented Oct 19, 2009 at 5:05

2 Answers 2

Reset to default
6
$\begingroup$

If a graph can be embedded into the plane with smooth edges and one point of crossing, then it can be embedded smoothly into the projective plane without crossings, by blowing up the crossing point (and conversely). But not every graph can be embedded into the projective plane, so not every graph has a smooth embedding of the type you describe.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I believe you, but I am a little confused -- why doesn't the same argument work for topological embeddings? $\endgroup$
    – Harrison Brown
    Commented Oct 18, 2009 at 22:49
  • 1
    $\begingroup$ A "blow-up" is a way of replacing a single point with a whole line, where the points on this new line correspond to directions passing through the original point. When you blow up a point in the real plane you end up with a mobius strip. (This is a bit hard to visualize and I'm having trouble finding a good picture online.) So if you could draw any graph with a single intersection point then you could draw it on a Mobius strip with no intersection points. This isn't possible, see a bunch of nice posts at The Everything Seminar starting at cornellmath.wordpress.com/2007/06/30/9 $\endgroup$
    – Noah Snyder
    Commented Oct 18, 2009 at 23:07
  • $\begingroup$ Ah, okay, so it doesn't work for topological embeddings, but it should work even when the arcs are first-differentiable? Or am I being silly, here? $\endgroup$
    – Harrison Brown
    Commented Oct 18, 2009 at 23:12
  • 2
    $\begingroup$ The argument works if they're first differentiable and they're not tangent at the intersection point. Because of this tangency issue I think David's very nice argument doesn't quite work here. $\endgroup$
    – Noah Snyder
    Commented Oct 18, 2009 at 23:33
  • 1
    $\begingroup$ Ok, right. If you have them all tangent to each other you can do anything you want. E.g. make curve C_k converge to the point (0,0) like the graph of k exp(x^2) on the x > 0 side and like the graph of π(k) exp(x^2) on the x < 0 side, where π is your favorite permutation; that way they realize π and are still all smooth. $\endgroup$
    – David Eppstein
    Commented Oct 19, 2009 at 1:19
0
$\begingroup$

What's the "easy explicit description" you refer to? I have some drawings for, say, K_6, but I can't convince myself that they generalize.

Improve this answer
$\endgroup$
1
  • $\begingroup$ It's easier to picture on a sphere. Have all of the edges go straight out to the point at infinity. This means every edge is noncontinuous at the intersection point. You can perturb things if you want so that the intersection point isn't at infinity. $\endgroup$
    – Noah Snyder
    Commented Oct 18, 2009 at 23:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .