Tight bounds for intersection‐reverse sequences, edge‐ordered graphs, and applications
OPEN ACCESS
Loading...
Author / Producer
Date
2025-10
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Scopus:
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
In 2006, Marcus and Tardos proved that if $A^1,\dots,A^n$ are cyclic orders on some subsets of a set of $n$ symbols such that the common elements of any two distinct orders $A^i$ and $A^j$ appear in reversed cyclic order in $A^i$ and $A^j$, then $\sum _{i} |A^i|=O(n^{3/2}\log n)$. This result is tight up to the logarithmic factor and has since become an important tool in Discrete Geometry. In this paper, we improve this to the optimal bound $O(n^{3/2})$. In fact, we prove the following more general result. We show that if $A^1,\dots,A^n$ are linear orders on some subsets of a set of $n$ symbols such that no three symbols appear in the same order in any two distinct linear orders, then $\sum _{i} |A^i|=O(n^{3/2})$. Using this result, we resolve several open problems in Discrete Geometry and Extremal Graph Theory as follows.
(i)We prove that every $n$-vertex topological graph that does not contain a self-crossing four-cycle has $O(n^{3/2})$ edges. This resolves a problem of Marcus and Tardos from 2006.
(ii)We show that $n$ pseudo-circles in the plane can be cut into $O(n^{3/2})$ pseudo-segments, which, in turn, implies new bounds on the number of point-circle incidences and on other geometric problems. This goes back to a problem of Tamaki and Tokuyama from 1998 and improves several results in the area.
(iii)We also prove that the edge-ordered Turán number of the four-cycle $C_4^{1243}$ is $\Theta (n^{3/2})$. This gives the first example of an edge-ordered graph whose Turán number is known to be $\Theta (n^{\alpha })$ for some $1<\alpha <2$, and answers a question of Gerbner, Methuku, Nagy, Pálvölgyi, Tardos, and Vizer.
Using different methods, we determine the largest possible extremal number that an edge-ordered forest of order chromatic number two can have. Kucheriya and Tardos showed that every such graph has extremal number at most $n2^{O(\sqrt {\log n})}$, and conjectured that this can be improved to $n(\log n)^{O(1)}$. We disprove their conjecture in a strong form by showing that for every $C>0$, there exists an edge-ordered tree of order chromatic number two whose extremal number is $\Omega (n 2^{C\sqrt {\log n}})$.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
112 (4)
Pages / Article No.
Publisher
Wiley
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Organisational unit
03993 - Sudakov, Benjamin / Sudakov, Benjamin
Notes
Funding
228014 - 10001163 - Ramsey and Turan Type Problems (SNF)