[{"article_type":"original","volume":151,"isi":1,"publication_identifier":{"issn":["0095-8956"]},"quality_controlled":"1","month":"06","intvolume":"       151","file_date_updated":"2021-06-28T13:33:23Z","article_processing_charge":"No","ddc":["510"],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","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.","department":[{"_id":"HeEd"}],"date_created":"2021-06-27T22:01:47Z","date_published":"2021-06-09T00:00:00Z","_id":"9602","oa":1,"author":[{"last_name":"Pach","id":"E62E3130-B088-11EA-B919-BF823C25FEA4","full_name":"Pach, János","first_name":"János"},{"last_name":"Tomon","first_name":"István","full_name":"Tomon, István"}],"type":"journal_article","year":"2021","publisher":"Elsevier","doi":"10.1016/j.jctb.2021.05.004","language":[{"iso":"eng"}],"title":"Erdős-Hajnal-type results for monotone paths","file":[{"file_size":418168,"file_name":"2021_JournalOfCombinatorialTheory_Pach.pdf","success":1,"date_updated":"2021-06-28T13:33:23Z","file_id":"9612","checksum":"15fbc9064cd9d1c777ac0043b78c8f12","date_created":"2021-06-28T13:33:23Z","creator":"asandaue","content_type":"application/pdf","relation":"main_file","access_level":"open_access"}],"external_id":{"isi":["000702280800002"]},"publication":"Journal of Combinatorial Theory. Series B","has_accepted_license":"1","scopus_import":"1","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>","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>.","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>","ista":"Pach J, Tomon I. 2021. Erdős-Hajnal-type results for monotone paths. Journal of Combinatorial Theory. Series B. 151, 21–37.","short":"J. Pach, I. Tomon, Journal of Combinatorial Theory. Series B 151 (2021) 21–37.","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.","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>."},"project":[{"name":"The Wittgenstein Prize","_id":"268116B8-B435-11E9-9278-68D0E5697425","grant_number":"Z00342","call_identifier":"FWF"}],"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."}],"day":"09","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"oa_version":"Published Version","publication_status":"published","page":"21-37","status":"public","date_updated":"2023-08-10T13:38:00Z"}]