{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,17]],"date-time":"2026-02-17T11:45:43Z","timestamp":1771328743091,"version":"3.50.1"},"reference-count":19,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2020,8,13]],"date-time":"2020-08-13T00:00:00Z","timestamp":1597276800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2020,9]]},"abstract":"Abstract<\/jats:title>Several discrete geometry problems are equivalent to estimating the size of the largest homogeneous sets in graphs that happen to be the union of few comparability graphs<\/jats:italic>. An important observation for such results is that if G<\/jats:italic> is an n<\/jats:italic>-vertex graph that is the union of r<\/jats:italic> comparability (or more generally, perfect) graphs, then either G<\/jats:italic> or its complement contains a clique of size \n$n^{1\/(r+1)}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>This bound is known to be tight for \n$r=1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. The question whether it is optimal for \n$r\\ge 2$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> was studied by Dumitrescu and T\u00f3th. We prove that it is essentially best possible for \n$r=2$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, as well: we introduce a probabilistic construction of two comparability graphs on n<\/jats:italic> vertices, whose union contains no clique or independent set of size \n$n^{1\/3+o(1)}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>Using similar ideas, we can also construct a graph G<\/jats:italic> that is the union of r<\/jats:italic> comparability graphs, and neither G<\/jats:italic> nor its complement contain a complete bipartite graph with parts of size \n$cn\/{(log n)^r}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. With this, we improve a result of Fox and Pach.<\/jats:p>","DOI":"10.1017\/s0963548320000103","type":"journal-article","created":{"date-parts":[[2020,8,13]],"date-time":"2020-08-13T07:37:11Z","timestamp":1597304231000},"page":"747-756","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":2,"title":["Improved Ramsey-type results for comparability graphs"],"prefix":"10.1017","volume":"29","author":[{"given":"D\u00e1niel","family":"Kor\u00e1ndi","sequence":"first","affiliation":[]},{"given":"Istv\u00e1n","family":"Tomon","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2020,8,13]]},"reference":[{"key":"S0963548320000103_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574361"},{"key":"S0963548320000103_ref18","unstructured":"[18] Szab\u00f3, T. personal communication."},{"key":"S0963548320000103_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2008.12.004"},{"key":"S0963548320000103_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(80)90030-8"},{"key":"S0963548320000103_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/PL00007228"},{"key":"S0963548320000103_ref13","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1054"},{"key":"S0963548320000103_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/s003730200017"},{"key":"S0963548320000103_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s11083-006-9043-z"},{"key":"S0963548320000103_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-005-1162-6"},{"key":"S0963548320000103_ref11","doi-asserted-by":"publisher","DOI":"10.1112\/blms\/26.2.132"},{"key":"S0963548320000103_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/s11083-015-9384-6"},{"key":"S0963548320000103_ref3","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20246"},{"key":"S0963548320000103_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-010-0056-3"},{"key":"S0963548320000103_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(88)80014-3"},{"key":"S0963548320000103_ref9","first-page":"127","volume-title":"Contemporary Mathematics","author":"Kostochka","year":"2004"},{"key":"S0963548320000103_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2020.02.003"},{"key":"S0963548320000103_ref17","first-page":"159","volume-title":"Computer Science","author":"Raab","year":"1998"},{"key":"S0963548320000103_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(02)00501-0"},{"key":"S0963548320000103_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.09.006"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548320000103","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,14]],"date-time":"2020-09-14T12:06:13Z","timestamp":1600085173000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548320000103\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,13]]},"references-count":19,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["S0963548320000103"],"URL":"https:\/\/doi.org\/10.1017\/s0963548320000103","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,13]]},"assertion":[{"value":"\u00a9 The Author(s), 2020. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}