Improved Ramsey-type results for comparability graphs

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. An important observation for such results is that if G is an n-vertex graph that is the union of r comparability (or more generally, perfect) graphs, then either G or its complement contains a clique of size n(1/(r+1)).
This bound is known to be tight for r = 1. The question whether it is optimal for r >= 2 was studied by Dumitrescu and Toth. We prove that it is essentially best possible for r = 2, as well: we introduce a probabilistic construction of two comparability graphs on n vertices, whose union contains no clique or independent set of size n(1/3+o(1)).
Using similar ideas, we can also construct a graph G that is the union of r comparability graphs, and neither G nor its complement contain a complete bipartite graph with parts of size cn/(log n)(r). With this, we improve a result of Fox and Pach.


Published in:
Combinatorics Probability & Computing, 29, 5, 747-756
Year:
Sep 01 2020
Publisher:
New York, CAMBRIDGE UNIV PRESS
ISSN:
0963-5483
1469-2163
Keywords:




 Record created 2020-10-02, last modified 2020-10-25


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)