---
_id: '9602'
abstract:
- lang: eng
  text: "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 ck > 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^ck . This strengthens a result of Bousquet, Lagoutte, and
    Thomassé, who proved the analogous result for unordered graphs.\r\nA 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 ≥ 3, by a construction of Fox. We provide some further examples
    showing that this statement also fails for ordered graphs avoiding other ordered
    trees."
acknowledgement: We would like to thank the anonymous referees for their useful comments
  and suggestions. János Pach is partially supported by Austrian Science Fund (FWF)
  grant Z 342-N31 and by ERC Advanced grant “GeoScape.” István Tomon is partially
  supported by Swiss National Science Foundation grant no. 200021_196965, and thanks
  the support of MIPT Moscow. Both authors are partially supported by The Russian
  Government in the framework of MegaGrant no. 075-15-2019-1926.
article_processing_charge: No
article_type: original
author:
- first_name: János
  full_name: Pach, János
  id: E62E3130-B088-11EA-B919-BF823C25FEA4
  last_name: Pach
- first_name: István
  full_name: Tomon, István
  last_name: Tomon
citation:
  ama: Pach J, Tomon I. Erdős-Hajnal-type results for monotone paths. <i>Journal of
    Combinatorial Theory Series B</i>. 2021;151:21-37. doi:<a href="https://doi.org/10.1016/j.jctb.2021.05.004">10.1016/j.jctb.2021.05.004</a>
  apa: Pach, J., &#38; Tomon, I. (2021). Erdős-Hajnal-type results for monotone paths.
    <i>Journal of Combinatorial Theory. Series B</i>. Elsevier. <a href="https://doi.org/10.1016/j.jctb.2021.05.004">https://doi.org/10.1016/j.jctb.2021.05.004</a>
  chicago: Pach, János, and István Tomon. “Erdős-Hajnal-Type Results for Monotone
    Paths.” <i>Journal of Combinatorial Theory. Series B</i>. Elsevier, 2021. <a href="https://doi.org/10.1016/j.jctb.2021.05.004">https://doi.org/10.1016/j.jctb.2021.05.004</a>.
  ieee: J. Pach and I. Tomon, “Erdős-Hajnal-type results for monotone paths,” <i>Journal
    of Combinatorial Theory. Series B</i>, vol. 151. Elsevier, pp. 21–37, 2021.
  ista: Pach J, Tomon I. 2021. Erdős-Hajnal-type results for monotone paths. Journal
    of Combinatorial Theory. Series B. 151, 21–37.
  mla: Pach, János, and István Tomon. “Erdős-Hajnal-Type Results for Monotone Paths.”
    <i>Journal of Combinatorial Theory. Series B</i>, vol. 151, Elsevier, 2021, pp.
    21–37, doi:<a href="https://doi.org/10.1016/j.jctb.2021.05.004">10.1016/j.jctb.2021.05.004</a>.
  short: J. Pach, I. Tomon, Journal of Combinatorial Theory. Series B 151 (2021) 21–37.
date_created: 2021-06-27T22:01:47Z
date_published: 2021-06-09T00:00:00Z
date_updated: 2023-08-10T13:38:00Z
day: '09'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.1016/j.jctb.2021.05.004
external_id:
  isi:
  - '000702280800002'
file:
- access_level: open_access
  checksum: 15fbc9064cd9d1c777ac0043b78c8f12
  content_type: application/pdf
  creator: asandaue
  date_created: 2021-06-28T13:33:23Z
  date_updated: 2021-06-28T13:33:23Z
  file_id: '9612'
  file_name: 2021_JournalOfCombinatorialTheory_Pach.pdf
  file_size: 418168
  relation: main_file
  success: 1
file_date_updated: 2021-06-28T13:33:23Z
has_accepted_license: '1'
intvolume: '       151'
isi: 1
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '06'
oa: 1
oa_version: Published Version
page: 21-37
project:
- _id: 268116B8-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: Z00342
  name: The Wittgenstein Prize
publication: Journal of Combinatorial Theory. Series B
publication_identifier:
  issn:
  - 0095-8956
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Erdős-Hajnal-type results for monotone paths
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 151
year: '2021'
...