Back to Search
Start Over
Erd��s-Hajnal-type results for ordered paths
- Publication Year :
- 2020
- Publisher :
- arXiv, 2020.
-
Abstract
- An ordered graph is a graph with a linear ordering on its vertex set. We prove that for every positive integer $k$, there exists a constant $c_k>0$ such that any ordered graph $G$ on $n$ vertices with the property that neither $G$ nor its complement contains an induced monotone path of size $k$, has either a clique or an independent set of size at least $n^{c_k}$. This strengthens a result of Bousquet, Lagoutte, and Thomass��, who proved the analogous result for unordered graphs. A key idea of the above paper was to show that any unordered graph on $n$ vertices that does not contain an induced path of size $k$, and whose maximum degree is at most $c(k)n$ for some small $c(k)>0$, contains two disjoint linear size subsets with no edge between them. This approach fails for ordered graphs, because the analogous statement is false for $k\geq 3$, by a construction of Fox. We provide further examples how this statement fails for ordered graphs avoiding other ordered trees as well.<br />14 pages, 1 figure
- Subjects :
- FOS: Mathematics
Combinatorics (math.CO)
Subjects
Details
- Database :
- OpenAIRE
- Accession number :
- edsair.doi...........a87eb3e3338a51cdaaef360a0540c6a0
- Full Text :
- https://doi.org/10.48550/arxiv.2004.04594