5
$\begingroup$

I am able to construct K7 with crossing number 9 from K6 with crossing number 3. Hence, I know the crossing number for K7 is at most 9; though, the number may not be sharp.

Now, I heard it is possible to prove the crossing number of K7 is at least 7 (also, may not be sharp). Anyone have any idea?

$\endgroup$
3
  • $\begingroup$ The crossing numer of $K_7$ is exactly $9$, and it is known for $n \le 10$ that the crossing number of $K_n$ is $(1/4)[n/2][(n-1)/2][(n-2)/2][(n-3)/2]$ where each square bracket means the floor function. This formula is also known to be a general upper bound, and its being exact for $n \le 10$ was shown by R. Guy. See openproblemgarden.org/op/… $\endgroup$
    – coffeemath
    Apr 22 '13 at 2:28
  • $\begingroup$ I thought R. Guy (1972) proved (n^4)/80+O(n^3) <= nu(Kn) <= (n^4)/64+O(n^3), but the big-O notation doesn't help me here. I'll read your link carefully. Thanks. $\endgroup$
    – Sean
    Apr 22 '13 at 4:13
  • $\begingroup$ Actually I only scanned that the website referred to R. Guy as its backup for the conjectured formula being correct up to $n=10$, and another look shows that's been extended to $n=12$. However I got the impression that someone had shown these up to that point, since the article on the site made a careful distinction between upper/lower bounds and actual values. $\endgroup$
    – coffeemath
    Apr 22 '13 at 4:37
4
$\begingroup$

Take a look at the Rectilinear Crossing Project for the current state of the art. Tight bounds and solutions are known up to $K_{27}$.

There are 3 essentially different ways to embed $K_7$ with 9 crossings, and these solutions are available at that site.

I've added this info at the Wikipedia crossing number page -- really should have been there.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.