Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Tight bounds for intersection‐reverse sequences, edge‐ordered graphs, and applications
 
research article

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

Janzer, Barnabás
•
Janzer, Oliver  
•
Methuku, Abhishek
Show more
October 2025
Journal of the London Mathematical Society

In 2006, Marcus and Tardos proved that if are cyclic orders on some subsets of a set of symbols such that the common elements of any two distinct orders and appear in reversed cyclic order in and , then . 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 . In fact, we prove the following more general result. We show that if are linear orders on some subsets of a set of symbols such that no three symbols appear in the same order in any two distinct linear orders, then . Using this result, we resolve several open problems in Discrete Geometry and Extremal Graph Theory as follows. We prove that every ‐vertex topological graph that does not contain a self‐crossing four‐cycle has edges. This resolves a problem of Marcus and Tardos from 2006. We show that pseudo‐circles in the plane can be cut into 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. We also prove that the edge‐ordered Turán number of the four‐cycle is . This gives the first example of an edge‐ordered graph whose Turán number is known to be for some , 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 , and conjectured that this can be improved to . We disprove their conjecture in a strong form by showing that for every , there exists an edge‐ordered tree of order chromatic number two whose extremal number is .

  • Details
  • Metrics
Type
research article
DOI
10.1112/jlms.70324
Author(s)
Janzer, Barnabás
Janzer, Oliver  

École Polytechnique Fédérale de Lausanne

Methuku, Abhishek
Tardos, Gábor
Date Issued

2025-10

Publisher

Wiley

Published in
Journal of the London Mathematical Society
Volume

112

Issue

4

Article Number

e70324

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
ECOM  
FunderFunding(s)Grant NumberGrant URL

Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung

200021_228014

University of Illinois at Urbana-Champaign

Award RB25050

National Research, Development and Innovation Office

K‐132696,SNN‐135643

Show more
Available on Infoscience
October 17, 2025
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/255029
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés