论文标题
边缘订购图的Turán问题
Turán problems for Edge-ordered graphs
论文作者
论文摘要
在本文中，我们启动了针对边订购图的Turán问题的系统研究。一个简单的图称为$ \ textIt {edge-drounded} $，如果其边缘是线性排序的。边订购图之间的同构必须尊重边阶。边订购图的子图本身是带有诱导边阶的边订购的图形。我们说，如果没有$ g $的子图是同构至$ h $的，则一个边订购的图形$ g $ $ $ g $ \ $ \ textit {devers} $另一个边缘排序的图形$ h $。 边订购的图形$ h $的$ \ textit {turán编号} $是$ n $顶点上避免$ h $的边订购图中的最大边数。我们通常研究此问题，并建立一个用于边订购图的ERDőS-STONE-SIMONOVITS-type定理 - 我们发现，turán数字的相关参数是其$ \ textIt {order ofdit {order ofdit {order ofer {order ofder {order ofer corm vallomatic number} $。我们建立了此参数的几个重要属性。 我们还研究了Turán数量的边缘路径，星森林和长度四的周期。我们与禁忌一键式理论达文波特 - 锡泽尔理论建立了牢固的联系，并在离散的几何形状中显示了应用。
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.
