Talk:Crossing number (graph theory)

Untitled

Old discussion copied from the Crossing Number Disambiguation page:

Crossing Number Inequality

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 e²/v³, 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. --18.95.7.4 (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(?) c_r in

$\operatorname {cr} (G)\geq c_{r}{\frac {e^{r+2}}{n^{r+1}}}.\,$

is not explained. (I don't have access to the journal article sadly.) —Preceding unsigned comment added by 70.36.140.58 (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!

the only way to see the proof is to visit a website... www.oddperfectnumbers.com 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 (talk • contribs) 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)

External links modified

Hello fellow Wikipedians,

I have just modified 2 external links on Crossing number (graph theory). Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20140714181310/http://sci.haifa.ac.il/~ackerman/publications/4crossings.pdf to http://sci.haifa.ac.il/~ackerman/publications/4crossings.pdf
• Corrected formatting/usage for http://www.ist.tugraz.at/staff/aichholzer/research/rp/triangulations/crossing/

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 21:41, 14 August 2017 (UTC)