数学溢出用户解决博士论文危机

$\BEGINGROUP$QUICE最终更新：只想感谢MO用户的所有支持。特别感谢你的快速回答，我已经接受了第一个，感谢它带给我的清晰。我已经用${\rmcr}(G)$更新了我的圆环算法。在我的完整测试集上运行良好，即圆环上的${\rmcr}(G)={\rmPCR}(G)$的证据。关于这一点的更多信息，稍后还将从上一个答案开始测试更清晰的界限。我会及时提交的！再次感谢MO用户的帮助！

原帖：如果“危机”这个词用得太重，我道歉，但我现在处于恐慌状态，如果这个词是正确的话：两周后，我应该提交我的博士论文，但我刚刚收到了坏消息，或者我应该说一些让我非常担心的信息。这真的是一种紧急情况：

我的论文是计算机科学，与球面和环面上的图形绘制相关的算法。我依赖的一个重要数学结果是图的边交叉引理(或边交叉不等式)。它给出了图$G$的任意图$G$具有$n$顶点和$e$边${\rmcr}(G)\geq\frac{e^3}{64n^2}$$的最小边交数${\rmcr}(G)$的下界。

问题：我在Pach and Tóth的文章中读到，关于交叉数的数学试卷有可能有不同的定义。有交叉数${\Rmcr}(G)$($G$的最小边交叉数)，也有${\RmPcr}(G)$的对交叉数，即$G$的图中的最小边对交叉数。我仔细检查了我的算法，根据这个定义，我清楚地应用了配对交叉数${\rMPCR}(G)$。

关键问题：你能向我证实边交叉引理在球面和环面上对交叉数${\rMPCR}(G)$也是有效的吗？

参考文献：János Pach和Géza Tóth。不管怎么说，它是哪个十字路口的号码？J·康宾。理论系列。B，80(2)：225-246,2000。

$\结束组$。

我真的对穿越号码一无所知，但我能理解这对你来说压力有多大。我希望你能及时修补！$\endgroup$-卡尔-弗雷德里克·尼伯格·布罗达(Carl-Fredrik Nyberg Brodda)

$\Begingroup$@PerAlexandersson-据我所知，两条边可能相交多次；此多重数计入cr，但不计入PCR，因此PCR$\leq$cr。$\endgroup$-Carlo Beenakker。

$\Beginggroup$我想投下一票的人在写博士论文时从来没有感觉到任何压力…。$\endgroup$-1 EFinat-S。

弗雷格曾经不得不写一篇文章，科学家很难遇到比工作刚结束就让基础让路更令人不快的事了。当这部作品即将付诸报刊时，伯特兰·罗素先生的一封信把我推到了这个位置。"；...$\endgroup$-1 Toffomat。

$\BEGINGROUP$也许您可以接受这里的答案，然后在您成功答辩论文后添加您自己的答案。绝大多数阅读这个问题的人都支持你。$\endgroup$-约翰·科尔曼。

$\Beginggroup$$\DeclareMathOperator\cr{cr}\DeclareMathOperator\pcr{pcr}$For对交叉数$\Pcr(G)$，简短的回答是肯定的，交叉引理对球面上的图成立，但不知道它是否也在环面上成立。

对你来说，最好也是最新的参考资料可能是谢弗的调查文章，该文章于2020年更新：“图形交叉数及其变种：调查”(The Graph Crossing Number and It Variables：A Survey)，来自电子组合学杂志(https://doi.org/10.37236/2713).)。

为您提供的相关页面是第5页和第6页，其中引用了Schaefer的以下内容：

“由于哈纳尼-图特定理对环面不成立，这意味着我们目前没有关于环面上的$\pcr$或$\pcr_−$的交叉引理的证明。”

通常，$\PCR(G)\leq\cr(G)$。他们是否相等仍是一个悬而未决的问题。交叉引理的第一个证明没有做出区分。第一个提出这种模棱两可的是莫哈尔(1995)在一次会议演讲中。

你提到的Pach和Tóth(2000)论文确实区分了$\PCR(G)$和$\cr(G)$，并将Hanani-Tutte应用于交叉引理的证明中，从而确保它也适用于$\PCR(G)$。

问题是您可以将Hanani-Tutte应用于球体(和投影平面)，但不能将其应用于圆环。对于亏格$\geq4$的曲面，已知是假的，请参见Fulek和Kynčl(2019年)。这意味着圆环真的是“介于两者之间”。

Bojan Mohar(1995)：在拓扑图论特别会议上提到的问题，Mathfest，Burlington，Vermont，Mathfest，Vermont。(引用自：L.A.SZékely(2016)：图兰的砖厂问题：Zarankiewicz和Hill猜想的现状。见：R.Gera等人。(编著)(2016)：图论-最受欢迎的猜想和公开问题。1)。

Radola v Fulek和Jan Kynčl(2019年)：推广的HANANI-TUTE定理在属4表面的反例。组合，39(6)：1267-1279。

$\结束组$。

$\egingroup$顺便说一下，作者的名字叫托斯，不是索特·哈哈。$\endgroup$-1霍利斯·威廉姆斯。

$\Begingroup$从OP'；的观点来看，这可以被视为玻璃杯半满，而不是玻璃杯半空。他们的论文结果明确地保持在球面上，并可能保持在环面上，尽管如果他们这样做了，这是一个悬而未决的问题。研究从给定的猜想是否为真得出的结论当然是合法的。它甚至可以被当作论文的一个特写，而不是一个错误。如果环面上的结果实际上失败了，那么你就知道这个猜想一定是错误的。潜在地，它可能会开辟一条卓有成效的攻击途径。$\endgroup$-约翰·科尔曼

$\BEGINGROUP$我认为在代数拓扑学文献中，Hanani-Tutte被认为是Flores-Van Kampen型定理的一个版本，如果这是一个有用的链接。

$\BEGINGROUP$添加我的评论，这里是来自A.Skopenkov arxiv.org/pdf/1805.10237.pdf$\endgroup$-mat的2019年平面图形不变量参考。

$\Begingroup$@ClausDollinger。这种清晰度是有帮助的。谢谢你的快速帮助。非常感谢。我很高兴我能保留我的球面算法。我正在检查是否可以在接下来的5天内将我的环面算法调整为${\rmcr}(G)$$\endgroup$-.user161819。

$\Begingroup$假设Robertson和Seymour关于Kuratowski未成年人的Ramsey型结果[FK18，权利要求5]未发表[FK18，权利要求5]，在图-次要社区中，交叉引理的一个渐近变体$\Operatorname{cr}(G)\ge\omega(e^3/n^2)$，即使对于固定曲面(如环面)上的对交叉数也成立。

利用Radola v Fulek[FK18，推论9]，我们已经证明了[FK18，权利要求5]蕴含了可定向曲面上的Hanani-Tutte定理的一个近似版本。特别地，[FK18，权利要求5]暗示存在一个常数$g$，使得对于可以绘制在环面上且每对独立边相交偶数次的每个图$G$，都可以在亏格为$g$的可定向曲面上绘制$G$而没有十字。这就是说，[FK18，权利要求5]意味着对于可以绘制在环面上且每对独立边相交偶数次的图$G$，可以在亏格为$g$的可定向曲面上绘制$G$。正如马库斯·谢弗(Marcus Schaefer')第5-6页所述；的调查[S20]，在克劳斯·多林格的回答中提到。另见[SSSV96，定理4.1]。

Https://dx.doi.org/10.4230/LIPIcs.SoCG.2018.40，https://arxiv.org/abs/1803.05085-R.Fulek和J Kynčl，库拉托夫斯基未成年人的$\mathbb Z_2$-亏格。

[https://doi.org/10.1007/BF02086611-F.Shahrokhi，L.A.Székely，O.S y.kora和I.VRT'；o，具有较少交叉的曲面上的图形的绘图，算法16,118131(1996)][Székely，O.S.Motikora and I.VRT'；o]，算法16，第118-131页(1996年)。

[S20]https://doi.org/10.37236/2713-M.Schaefer，图形交叉数及其变体：调查，组合学电子期刊，DS21：2020年2月14日。

$\结束组$。

$\BEGINGROUP$是Schaefer的调查Hanani-Tutte及相关结果(MSN)？$\endgroup$-.LSpice。

我指的是克劳斯·多林格(Claus Dollinger)答案中提到的关于穿越人数的调查。我将进行编辑并添加引用以使其清楚。$\endgroup$-Jan Kyncl。

$\BEGINGROUP$顺便说一下，您知道您的用户名中允许使用像ˇ这样的变音符号，对吧？$\EndGroup$-.lspice。

$\Begingroup$@JanKyncl也感谢您的帮助，非常感谢。我的导师说教员不会接受渐近性。我正在检查是否可以将${\rmcr}(G)$放入我的环面算法$\endgroup$-.user161819。

$\BEGINGROUP$@user161819我想发表评论，但评论太长了，所以把它作为答案。但是，请将其作为稍后的评论，一旦一切都完成了：

如果我正确理解了您对我答案的评论，您的目标是更改圆环的算法，使其与${\rmcr}(G)$一起工作。我想整个MO社区都在祈祷，希望你能按时成功地完成所有的事情！

看着远处的地平线，我想给你一个建议。一旦您更改了环面算法并完成了论文，您手中将有效地掌握两个环面算法：基于${\rmPCR}(G)$的旧算法和基于${\rmcr}(G)$的新算法。我在这里说的是显而易见的，把它们都保留下来，它们真的可以为未来的研究带来丰硕的成果。

(1)显然，您的两个算法可以支持对${\rMPCR}(G)\stackrel{\rm？}{=}{\rmcr}(G)$这一大的公开问题的研究。他们可以为未来的平等证明或实际反例提供实验证据、想法和见解。(再一次，我在这里说的是显而易见的事情。)。

(2)要真正在环面上对${\rmPCR}(G)\stackrel{\rm？}{=}{\rmcr}(G)${\rmcr}(G)$\frac{1}{29}\frac{e^3}{n^2}$$进行压力测试，也可以尝试$e>；7n$的图的迄今最好的下界。这个下限来自于EYAL AKERMAN(2019年)：关于每条边至多有四个交叉的拓扑图"；，计算几何，85：101574，31，doi：10.1016/j.comGeo.2019.101574(您可能从您引用的维基百科文章中知道了这一点)。

我认为你的问题和整个话题真的很重要。LászlóSzékely称其为基础性问题之一，并在他的文章“图兰的砖厂问题：Zarankiewicz和Hill猜想的现状”中用了整整一节的篇幅来讨论这一问题。见：R.Gera等人。(编著)(2016)：图论-最受欢迎的猜想和公开问题。1)。

$\结束组$。

$\Beginggroup$感谢您的评论！！非常感谢。再次感谢您的帮助。我对这个Ackermann界限非常感兴趣，我会看看它$\endgroup$-1user161819。

$\BEGINGROUP$一件好事，我更新的环面算法的原型：在我的测试集中的前2个图上进行测试，结果是正常的$\endgroup$-.user161819。

$\Begingroup$术语Ackermann Bound通常指的是比这里给出的类型严重得多的边界：en.wikipedia.org/wiki/Ackermann_function$\endgroup$-*Terry陶渊源。

$\BEGINGROUP$@TerryTao Terry你说得很对。你提到的威廉·阿克曼界限和我在这里引用的埃亚尔·阿克曼界限有很大的不同！很高兴能做出区分。$\endgroup$-1克劳斯·多林格

点击“发布您的答案”，即表示您同意我们的服务条款、隐私政策和Cookie政策。

不是你想要的答案吗？浏览标记的其他问题或提出您自己的问题。