Edge ordered Turán problems

Abstract

We introduce the Tur\'an problem for edge ordered graphs. We call a simple graph \emph{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$ \emph{avoids} another edge ordered graph $H$, if no subgraph of $G$ is isomorphic to $H$. The Tur\'an number $\mathrm{ex}'_{<}(n,\mathcal{H})$ of a family $\mathcal{H}$ of edge ordered graphs is the maximum number of edges in an edge ordered graph on $n$ vertices that avoids all elements of $\mathcal{H}$. We examine this parameter in general and also for several singleton families of edge orders of certain small specific graphs, like star forests, short paths and the cycle of length four.