Tight bounds for intersection-reverse sequences, edge-ordered graphs, and applications

doi:10.1112/jlms.70324

2025-10-01

DOI：10.1112/jlms.70324

原文链接

查看原文

摘要

En 中文

2006年，Marcus和Tardos证明了：如果A(1), ..., A(n)是某个n符号集合的子集上的循环序，且任意两个不同循环序A(i)和A(j)的公共元素在A(i)和A(j)中以相反的循环顺序出现，那么∑(i) |A(i)| = O(n^(3/2) log n)。这一结果在忽略对数因子的情况下是紧致的，并已成为离散几何学中的一个重要工具。本文中，我们将此结果改进为最优上界O(n^(3/2))。实际上，我们证明了以下更一般的结论：我们证明，如果A(1), ..., A(n)是某个n符号集合的子集上的线性序，且在任何两个不同的线性序中不存在三个符号以相同顺序出现，那么∑(i) |A(i)| = O(n^(3/2))。利用这一结果，我们解决了离散几何学与极值图论中的若干开放问题，具体如下：(i) 我们证明，每个不含自交叉四环的n顶点拓扑图具有O(n^(3/2))条边。这解决了Marcus和Tardos在2006年提出的问题。(ii) 我们证明，平面中的n个伪圆可以被切割成O(n^(3/2))个伪线段，这进而为点-圆相交数以及其他几何问题提供了新的界限。这可以追溯到Tamaki和Tokuyama在1998年提出的问题，并改进了该领域内的若干结果。(iii) 我们还证明，四环C-4(1243)的边序Turán数为Θ(n^(3/2))。这给出了一个边序图Turán数已知为Θ(n^α)（其中1 < α < 2）的第一个例子，并回答了Gerbner、Methuku、Nagy、Palvolgyi、Tardos和Vizer提出的问题。使用不同的方法，我们确定了阶染色数为二的边序森林可能具有的最大极值数。Kucheriya和Tardos证明了这样的图的极值数至多为n^(2(O(root log n)))，并猜测这一结果可改进为n^(O(log n))。我们通过证明：对于任意C > 0，存在一个阶染色数为根二的边序树，其极值数为Ω(n^(2c) root log n)，从而强有力地否定了他们的猜想。

Keyword:

GEOMETRIC GRAPHS

NUMBER

CIRCLES