2020/01/03 by Dániel Gerbner, Abhishek Methuku, Gerbner, Dániel +9 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2001.00849
openalex publication_date 2020/01/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we initiate a systematic study of the Turán problem for edge-ordered graphs. A simple graph is called edge-ordered, if its edges are linearly ordered. An isomorphism between edge-ordered graphs must respect the edge-order. A subgraph of an edge-ordered graph is itself an edge-ordered graph with the induced edge-order. We say that an edge-ordered graph G avoids another edge-ordered graph H, if no subgraph of G is isomorphic to H. The Turán number of an edge-ordered graph H is the maximum number of edges in an edge-ordered graph on n vertices that avoids H. We study this problem in general, and establish an Erdős-Stone-Simonovits-type theorem for edge-ordered graphs -- we discover that the relevant parameter for the Turán number of an edge-ordered graph is its order chromatic number. We establish several important properties of this parameter. We also study Turán numbers of edge-ordered paths, star forests and the cycle of length four. We make strong connections to Davenport-Schinzel theory, the theory of forbidden submatrices, and show an application in Discrete Geometry.