Tur��n problems for Edge-ordered graphs
| Autor: | Gerbner, D��niel, Methuku, Abhishek, Nagy, D��niel T., P��lv��lgyi, D��m��t��r, Tardos, G��bor, Vizer, M��t�� |
|---|---|
| Rok vydání: | 2020 |
| Předmět: | |
| DOI: | 10.48550/arxiv.2001.00849 |
| Popis: | In this paper we initiate a systematic study of the Tur��n problem for edge-ordered graphs. A simple graph is called $\textit{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$ $\textit{avoids}$ another edge-ordered graph $H$, if no subgraph of $G$ is isomorphic to $H$. The $\textit{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 $\textit{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. 41 pages. Updated grants |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|