https://mathoverflow.net/questions/366765/issue-update-in-graph-theory-different-definitions-of-edge-crossing-numbers Stack Exchange Network Stack Exchange network consists of 177 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers. Visit Stack Exchange [ ] Loading... 1. 2. 0 3. +0 4. + Tour Start here for a quick overview of the site + Help Center Detailed answers to any questions you might have + Meta Discuss the workings and policies of this site + About Us Learn more about Stack Overflow the company + Business Learn more about hiring developers or posting ads with us 5. 6. Log in Sign up 7. current community + MathOverflow help chat + MathOverflow Meta your communities Sign up or log in to customize your list. more stack exchange communities company blog By using our site, you acknowledge that you have read and understand our Cookie Policy, Privacy Policy, and our Terms of Service. MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up. Sign up to join this community [ano] Anybody can ask a question [ano] Anybody can answer [an] The best answers are voted up and rise to the top MathOverflow 1. Home 2. 1. Questions 2. Tags 3. Users 4. Unanswered Issue UPDATE: in graph theory, different definitions of edge crossing numbers - impact on applications? Ask Question Asked 7 days ago Active yesterday Viewed 64k times 150 27 $\begingroup$ QUICK FINAL UPDATE: Just wanted to thank you MO users for all your support. Special thanks for the fast answers, I've accepted first one, appreciated the clarity it gave me. I've updated my torus algorithm with ${\rm cr}(G)$. Works fine on my full test set, i.e. evidence for ${\rm cr}(G)={\rm pcr}(G)$ on torus. More on this later, will test sharper bound from last answer as well. I'm going to submit in time! Thanks again MO users for all your help! Original post: I apologize if ,,crisis" is too strong a word, but I am in a mode of panic, if that's the right word: In two weeks, I should be submitting my Ph.D. Thesis, but I have just received bad news, or I should say information that makes me very concerned. It is really an emergency situation: My thesis is in computer science, algorithms related to graph drawings on the sphere and the torus. One of the cornerstone mathematical results I am relying on is the graph edge crossing lemma (or edge crossing inequality). It gives a lower bound for the minimum number of edge crossings ${\rm cr}(G)$ for any drawing of the graph $G$ with $n$ vertices and $e$ edges $${\rm cr}(G)\geq \frac{e^3}{64n^ 2}$$ for $e>4n$. PROBLEM: I am reading in the article of Pach and Toth that there is a possibility that mathematics papers on crossing numbers operate with different definitions. There is the crossing number ${\rm cr}(G)$ (minimum of edge crossings in a drawing of $G$), but also the pair crossing number ${\rm pcr}(G)$, the minimum number of edge pairs crossing in a drawing of $G$. I double-checked my algorithms and, based on this definition, I clearly apply the pair crossing number ${\rm pcr}(G)$ CRITICAL QUESTION: Can you confirm to me that the edge crossing lemma remains valid on the sphere and the torus also for the pair crossing number ${\rm pcr}(G)$? Reference: Janos Pach and Geza Toth. Which crossing number is it anyway? J. Combin. Theory Ser. B, 80(2): 225-246, 2000. And Wikipedia article as a starting point https://en.wikipedia.org/ wiki/Crossing_number_inequality co.combinatorics graph-theory algorithms computer-science random-graphs share | cite | improve this question | follow | edited yesterday user161819 asked Jul 28 at 7:51 [d8b] user161819user161819 78322 gold badges33 silver badges88 bronze badges $\endgroup$ * 79 $\begingroup$ I don't really know anything about crossing numbers, but I can appreciate how stressful this must be for you. I hope that you are able to patch things up in time! $\endgroup$ - Carl-Fredrik Nyberg Brodda Jul 28 at 8:24 * 10 $\begingroup$ @PerAlexandersson --- as I understand it two edges may intersect multiple times; this multiplicity is counted in cr but not in pcr, hence pcr $\leq$ cr. $\endgroup$ - Carlo Beenakker Jul 28 at 15:53 * 37 $\begingroup$ I suppose that the downvoter never felt any stress while doing his/her Ph.D Thesis... $\endgroup$ - EFinat-S Jul 28 at 17:15 * 19 $\begingroup$ Frege once had to write "A scientist can hardly meet with anything more undesirable than to have the foundations give way just as the work is finished. I was put in this position by a letter from Mr. Bertrand Russell when the work was nearly through the press. "... $\endgroup$ - Toffomat Jul 29 at 8:49 * 12 $\begingroup$ Maybe you could accept the answer that is here, and then add your own answer after you successfully defend your dissertation. The vast majority of people who read this question are rooting for you. $\endgroup$ - John Coleman Jul 29 at 13:34 | show 8 more comments 3 Answers 3 Active Oldest Votes 127 $\begingroup$ $\DeclareMathOperator\cr{cr}\DeclareMathOperator\pcr{pcr}$For the pair crossing number $\pcr(G)$, the short answer is yes the crossing lemma holds for drawings on the sphere, but it is not known whether it also holds on the torus. The best and most current reference for you could be the survey article from Schaefer, updated in February 2020: "The Graph Crossing Number and its Variants: A Survey" from the Electronic Journal of Combinatorics (https://doi.org/10.37236/2713). The relevant pages for you are pages 5 and 6 with the following quote from Schaefer: "Since the Hanani-Tutte theorem is not known to be true for the torus, this means that we do not currently have a proof of the crossing lemma for $\pcr$ or $\pcr_-$ on the torus." Generally, $\pcr(G)\leq \cr(G)$. It is still an open problem whether they are equal or not. The first proofs of the crossing lemma did not make the distinction. The first one to raise the ambiguity was Mohar (1995) in a conference talk. The Pach and Toth (2000) paper that you mention does make the distinction between $\pcr(G)$ and $\cr(G)$, and applies Hanani-Tutte in the proof of the crossing lemma, which ensures that it also holds for $\pcr(G)$. The issue is that you can apply Hanani-Tutte for the sphere (and the projective plane), but you cannot apply it for the torus. For surfaces of genus $\geq4$ it is known to be false, see Fulek and Kyncl (2019). This means the torus is really "in-between". Edit: Adding the references Bojan Mohar (1995): Problem mentioned at the special session on Topological Graph Theory, Mathfest, Burlington, Vermont. (cited from: L.A. Szekely (2016): Turan's Brick Factory Problem: The Status of the Conjectures of Zarankiewicz and Hill. In: R. Gera et al. (eds.) (2016): Graph Theory--favorite conjectures and open problems. 1.) Hanani-Tutte Theorem https://en.wikipedia.org/wiki/ Hanani%E2%80%93Tutte_theorem Radoslav Fulek and Jan Kyncl (2019): Counterexample to an Extension of the Hanani-Tutte Theorem on the Surface of Genus 4. Combinatorica, 39(6):1267-1279 share | cite | improve this answer | follow | edited Jul 29 at 5:23 [XFS] David Roberts 27.1k66 gold badges7979 silver badges219219 bronze badges answered Jul 28 at 8:09 [6fe] Claus DollingerClaus Dollinger 2,96011 gold badge1212 silver badges3030 bronze badges $\endgroup$ * 26 $\begingroup$ The author's name is Toth by the way, not Thot lol. $\endgroup$ - Hollis Williams Jul 28 at 23:26 * 60 $\begingroup$ From OP's point of view this could be viewed as glass half-full rather than glass half-empty. Their dissertation results hold unequivocally on the sphere and might hold on the torus, though it is an open problem if they do. It is certainly legitimate to study what follows from a given conjecture being true. It could even be spun as a feature rather than a bug of the dissertation. If the results in fact fail on the torus then you know that the conjecture must be false. Potentially, it could open up a fruitful avenue of attack. $\endgroup$ - John Coleman Jul 29 at 0:25 * 1 $\begingroup$ I think in algebraic topology literature, Hanani-Tutte is known as a version of the Flores-Van Kampen theorem, if that's a helpful link $\endgroup$ - Matt Jul 29 at 8:53 * 1 $\begingroup$ Adding to my comment, here is a 2019 reference "Invariants of graph drawings in the plane" from A. Skopenkov arxiv.org/pdf/1805.10237.pdf $\endgroup$ - Matt Jul 29 at 9:05 * 22 $\begingroup$ @ClausDollinger . The clarity is helpful. Thanks for your fast help. Much appreciated. I'm glad I can keep my sphere algorithm. I'm checking whether I can adapt my torus algorithm to ${\rm cr}(G)$ within the next 5 days $\endgroup$ - user161819 Jul 29 at 17:22 add a comment | 31 $\begingroup$ Assuming an unpublished Ramsey-type result by Robertson and Seymour about Kuratowski minors [FK18, Claim 5], which is now "folklore" in the graph-minor community, an asymptotic variant of the crossing lemma, $\operatorname{cr}(G)\ge \Omega(e^3/n^2)$, is true even for the pair crossing number on a fixed surface, such as a torus. With Radoslav Fulek [FK18, Corollary 9] we have shown that [FK18, Claim 5] implies an approximate version of the Hanani-Tutte theorem on orientable surfaces. In particular, [FK18, Claim 5] implies that there is a constant $g$ such that for every graph $G$ that can be drawn on the torus with every pair of independent edges crossing an even number of times, $G$ can be drawn on the orientable surface of genus $g$ without crossings. This gives an upper bound $3n + O(g)$ on the number of edges of every such graph $G$, and this can be used in the probabilistic proof of the crossing lemma, as described on p. 5-6 of Marcus Schaefer's survey [S20], mentioned in Claus Dollinger's answer. See also [SSSV96, Theorem 4.1]. References: [FK18] https://dx.doi.org/10.4230/LIPIcs.SoCG.2018.40, https:// arxiv.org/abs/1803.05085 - R. Fulek and J Kyncl, The $\mathbb Z_2$ -genus of Kuratowski minors [SSSV96] https://doi.org/10.1007/BF02086611 - F. Shahrokhi, L. A. Szekely, O. Sykora and I. Vrt'o, Drawings of graphs on surfaces with few crossings, Algorithmica 16, 118-131 (1996) [S20] https://doi.org/10.37236/2713 - M. Schaefer, The Graph Crossing Number and its Variants: A Survey, The Electronic Journal of Combinatorics, DS21: Feb 14, 2020. share | cite | improve this answer | follow | edited Jul 29 at 19:26 [Haz] Glorfindel 2,02344 gold badges1515 silver badges2828 bronze badges answered Jul 29 at 15:59 [757] Jan KynclJan Kyncl 4,4111414 silver badges2525 bronze badges $\endgroup$ * $\begingroup$ Is Schaefer's survey Hanani-Tutte and related results (MSN)? $\endgroup$ - LSpice Jul 29 at 16:30 * 2 $\begingroup$ I meant the survey about crossing numbers, mentioned in Claus Dollinger's answer. I will make an edit and add the reference to make it clear. $\endgroup$ - Jan Kyncl Jul 29 at 16:47 * 2 $\begingroup$ By the way, you know that diacrits like V are allowed in your username if you want, right? $\endgroup$ - LSpice Jul 29 at 17:03 * 8 $\begingroup$ @JanKyncl Thank you for your help as well, much appreciated. My advisor says the faculty will not accept asymptotics. I'm checking whether I can put ${\rm cr}(G)$ into my torus algorithm $\endgroup$ - user161819 Jul 29 at 17:26 * 27 $\begingroup$ "the faculty will not accept asymptotics"? $\ endgroup$ - Ville Salo Jul 29 at 20:39 add a comment | 16 $\begingroup$ @user161819 I wanted to make a comment but it got too long, so putting it as an answer. But please take it just as a comment for later, once everything is finished: If I understand your comment to my answer correctly, you are aiming to change your algorithm for the torus so it works with $ {\rm cr}(G)$. I think the whole MO community is keeping their fingers crossed, wishing you that you can successfully complete everything in time! Looking at the far horizon, I wanted to make a suggestion to you. Once you have changed your torus algorithm and completed your thesis, you will have effectively two algorithms in your hands for the torus: The old one based on ${\rm pcr}(G)$ and the new one based on ${\rm cr}(G)$. I am saying the obvious here, keep both of them, they can really be fruitful for future research. (1) Obviously, your two algorithms could support research on the big open question whether ${\rm pcr}(G)\stackrel{\rm ?}{=}{\rm cr}(G)$ or not. They could produce experimental evidence, ideas, and insights for a future proof of equality, or an actual counterexample. (Again, I am saying the obvious here.) (2) To really pressure-test ${\rm pcr}(G)\stackrel{\rm ?}{=}{\rm cr} (G)$ on the torus, it would be interesting to also try the best known to date lower bound for ${\rm cr}(G)$ $$\frac{1}{29}\frac{e^3}{n^2}$$ for graphs with $e>7n$. This lower bound is from Eyal Ackerman (2019): "On topological graphs with at most four crossings per edge", Computational Geometry, 85: 101574, 31, doi:10.1016/ j.comgeo.2019.101574 (probably you are aware of it from the Wikipedia article that you quoted). I think your question and this whole topic are really important. Laszlo Szekely calls it one of the "foundational problems" and devotes a whole section to it in his article Turan's Brick Factory Problem: The Status of the Conjectures of Zarankiewicz and Hill. In: R. Gera et al. (eds.)(2016): Graph Theory--favorite conjectures and open problems. 1.) For now, fingers crossed that you can complete your thesis in time! share | cite | improve this answer | follow | answered Jul 30 at 15:37 [6fe] Claus DollingerClaus Dollinger 2,96011 gold badge1212 silver badges3030 bronze badges $\endgroup$ * 1 $\begingroup$ Thanks for your comment!! Much appreciated. And thanks again for your help. I'm very interested in this Ackermann bound, will take a look at it $\endgroup$ - user161819 Jul 30 at 16:28 * 5 $\begingroup$ One good thing, my prototype for updated torus algorithm: tested on on first 2 graphs from my test set, and went ok $\endgroup$ - user161819 Jul 30 at 16:33 * 4 $\begingroup$ The term "Ackermann bound" generally refers to a bound of a type far, far worse than the one given here: en.wikipedia.org/wiki/Ackermann_function $\endgroup$ - Terry Tao yesterday * 5 $\begingroup$ @TerryTao Terry you are very right. Huge difference between the Wilhelm Ackermann bound that you mention and the Eyal Ackerman bound I am quoting here! Good to make the distinction. $ \endgroup$ - Claus Dollinger yesterday add a comment | Your Answer [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] Thanks for contributing an answer to MathOverflow! * Please be sure to answer the question. Provide details and share your research! But avoid ... * Asking for help, clarification, or responding to other answers. * Making statements based on opinion; back them up with references or personal experience. Use MathJax to format equations. MathJax reference. To learn more, see our tips on writing great answers. Draft saved Draft discarded [ ] Sign up or log in Sign up using Google Sign up using Facebook Sign up using Email and Password Submit Post as a guest Name [ ] Email Required, but never shown [ ] Post as a guest Name [ ] Email Required, but never shown [ ] Post Your Answer Discard 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 co.combinatorics graph-theory algorithms computer-science random-graphs or ask your own question. Featured on Meta * Improved experience for users with review suspensions * CEO Blog: Some exciting news about fundraising Related 3 Min Bend Orthogonal Knots 13 Drawings of complete graphs with $Z(n)$ crossings 4 Example to show pairwise crossing number is not equal to crossing number 3 Looking for examples showing that the crossing number may not be realized by the drawings with local crossing number 5 Conjecture about minimal number of edge crossings in complete bipartite graphs Question feed Subscribe to RSS Question feed To subscribe to this RSS feed, copy and paste this URL into your RSS reader. [https://mathoverflow] * MathOverflow * Tour * Help * Chat * Contact * Feedback * Mobile Company * Stack Overflow * For Teams * Advertise With Us * Hire a Developer * Developer Jobs * About * Press * Legal * Privacy Policy Stack Exchange Network * Technology * Life / Arts * Culture / Recreation * Science * Other * Stack Overflow * Server Fault * Super User * Web Applications * Ask Ubuntu * Webmasters * Game Development * TeX - LaTeX * Software Engineering * Unix & Linux * Ask Different (Apple) * WordPress Development * Geographic Information Systems * Electrical Engineering * Android Enthusiasts * Information Security * Database Administrators * Drupal Answers * SharePoint * User Experience * Mathematica * Salesforce * ExpressionEngine(r) Answers * Stack Overflow em Portugues * Blender * Network Engineering * Cryptography * Code Review * Magento * Software Recommendations * Signal Processing * Emacs * Raspberry Pi * Stack Overflow na russkom * Code Golf * Stack Overflow en espanol * Ethereum * Data Science * Arduino * Bitcoin * Software Quality Assurance & Testing * Sound Design * Windows Phone * more (28) * Photography * Science Fiction & Fantasy * Graphic Design * Movies & TV * Music: Practice & Theory * Worldbuilding * Video Production * Seasoned Advice (cooking) * Home Improvement * Personal Finance & Money * Academia * Law * Physical Fitness * Gardening & Landscaping * Parenting * more (10) * English Language & Usage * Skeptics * Mi Yodeya (Judaism) * Travel * Christianity * English Language Learners * Japanese Language * Chinese Language * French Language * German Language * Biblical Hermeneutics * History * Spanish Language * Islam * Russkii iazyk * Russian Language * Arqade (gaming) * Bicycles * Role-playing Games * Anime & Manga * Puzzling * Motor Vehicle Maintenance & Repair * Board & Card Games * Bricks * Homebrewing * Martial Arts * The Great Outdoors * Poker * Chess * Sports * more (16) * MathOverflow * Mathematics * Cross Validated (stats) * Theoretical Computer Science * Physics * Chemistry * Biology * Computer Science * Philosophy * Linguistics * Psychology & Neuroscience * Computational Science * more (10) * Meta Stack Exchange * Stack Apps * API * Data * Blog * Facebook * Twitter * LinkedIn * Instagram site design / logo (c) 2020 Stack Exchange Inc; user contributions licensed under cc by-sa. rev 2020.8.4.37336 MathOverflow works best with JavaScript enabled [p-c1rF4kxg]