Tur\'an problems for Edge-ordered graphs

DOI10.1016/J.JCTB.2022.12.006MaRDI QIDQ6332248arXivFDO

Authors Dániel Gerbner, Abhishek Methuku, Dániel T. Nagy, Dömötör Pálvölgyi, Gábor Tardos, Máté Vizer

Publication date 3 January 2020

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.JCTB.2022.12.006

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Enumeration in graph theory (05C30) Ordered sets (06A99)

arXiv classification

math.CO

Abstract: In this paper we initiate a systematic study of the Tur'an problem for edge-ordered graphs. A simple graph is called $extitedge-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$ $extitavoids$ another edge-ordered graph $H$, if no subgraph of $G$ is isomorphic to $H$. The $extitTu{r}^{\prime }annumber$ 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 ErdH{o}s-Stone-Simonovits-type theorem for edge-ordered graphs -- we discover that the relevant parameter for the Tur'an number of an edge-ordered graph is its $extitorderchromaticnumber$. We establish several important properties of this parameter. We also study Tur'an 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.

This page was built for publication: Tur\'an problems for Edge-ordered graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6332248)