Issue UPDATE: in graph theory, different definitions of edge crossing numbers

$begingroup$

$DeclareMathOperatorcr{cr}DeclareMathOperatorpcr{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 Tóth (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 Kynčl (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. Székely (2016): Turán’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 Kynčl (2019): Counterexample to an Extension of the Hanani–Tutte Theorem on the Surface of Genus 4. Combinatorica, 39(6):1267–1279

David Roberts

27.1k6 gold badges79 silver badges219 bronze badges

answered Jul 28 at 8:09

$endgroup$

$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 Kynčl, The $mathbb Z_2$-genus of Kuratowski minors

[SSSV96] https://doi.org/10.1007/BF02086611 – F. Shahrokhi, L. A. Székely, O. Sýkora 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.

Glorfindel

2,0234 gold badges15 silver badges28 bronze badges

answered Jul 29 at 15:59

$endgroup$

$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. László Székely calls it one of the “foundational problems” and devotes a whole section to it in his article Turán’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!

answered Jul 30 at 15:37

$endgroup$

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

Read More

5 Replies to “Issue UPDATE: in graph theory, different definitions of edge crossing numbers“

Leave a Reply

Your email address will not be published.