Talk:Crossing number (graph theory)

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated B-class, Mid-priority)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
B Class
Mid Priority
 Field: Discrete mathematics

Old discussion copied from the Crossing Number Disambiguation page:

Crossing Number Inequality[edit]

Unlike stated in that section, the crossing number inequality apparently has been improved recently: Pach, János; Radoi\v ci\'c, Rado\v s; Tardos, Gábor; Tóth, Géza Improving the crossing lemma by finding more crossings in sparse graphs. Discrete Comput. Geom. 36 (2006), no. 4, 527--552. [[1]] If the paper contains an unconditional (asymptotic) improvement over the known bound, this result should be included. (I haven't read through the paper yet.)Hermel (talk) 13:34, 4 July 2008 (UTC)

They show that when e ≥ (103/6)v , the number of crossings is roughly 1/31.081 e2/v3, improving the previous constant by a little at a big expense in how dense the graph needs to be before the improvement kicks in. (The results we quote in the article are that when e ≥ 4v, we get a 1/64 factor, and when e ≥ 7.5v, we get a 1/33.75 factor. —David Eppstein (talk) 17:23, 4 July 2008 (UTC)

Ok, I'm fine with thatHermel (talk) 19:01, 16 July 2008 (UTC)

I think the page should indicate the improved bound, or else it can be rather misleading. -- (talk) 00:09, 1 April 2013 (UTC)

In the section "The crossing number inequality", final paragraph re "For graphs with girth larger than 2r and e ≥ 4n,", the constant(?) cr in

is not explained. (I don't have access to the journal article sadly.) —Preceding unsigned comment added by (talk) 12:59, 21 November 2010 (UTC)

Notation like that means "a constant depending on r but not on n". —David Eppstein (talk) 16:52, 21 November 2010 (UTC)

I have proven the both Guy's and Zarankiewicz's guesses are right![edit]

the only way to see the proof is to visit a website... I am not trying to promote anything; both answers use the supremum of the minimum of two functions that use the same transform, but they are spanned differently. It's the only way to see the answer... click on the Other Proofs Page; enjoy! Bill —Preceding unsigned comment added by Leavemsg2 (talkcontribs) 22:19, 23 November 2010 (UTC)

Until you publish it in a reputable journal, we can't use it here. —David Eppstein (talk) 03:46, 24 November 2010 (UTC)