Improved Ramsey-type results for comparability graphs

DOI10.1017/S0963548320000103MaRDI QIDQ4987258zbMATH OpenFDO

Authors Dániel Korándi, István Tomon

Publication date 30 April 2021

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.00588

zbMATH Keywords

disjointness graphbiclique

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Generalized Ramsey theory (05C55) Combinatorics of partially ordered sets (06A07) Ramsey theory (05D10)

Abstract: 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 $rge2$ was studied by Dumitrescu and T'oth. 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 contains a complete bipartite graph with parts of size $fraccn(logn{)}^r$. With this, we improve a result of Fox and Pach.

Recommendations

• Ramsey-type results for unions of comparability graphs
• Ramsey properties of semilinear graphs
• Turán-type results for complete h-partite graphs in comparability and incomparability graphs
• Turán-type results for partial orders and intersection graphs of convex sets
• Large cliques and independent sets all over the place

Cites work

• scientific article; zbMATH DE number 1301967 (Why is no real title available?)
• scientific article; zbMATH DE number 2145236 (Why is no real title available?)
• A Ramsey-Type Result for Convex Sets
• A bipartite analogue of Dilworth's theorem
• A bipartite analogue of Dilworth's theorem for multiple partial orders
• A note on Ramsey numbers
• Bounds on the chromatic number of intersection graphs of sets in the plane
• Colouring arcwise connected sets in the plane. I
• Conflict-free coloring of points and simple regions in the plane
• Delaunay graphs of point sets in the plane with respect to axis‐parallel rectangles
• Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
• On the chromatic number of disjointness graphs of curves
• Ramsey-type constructions for arrangements of segments
• Ramsey-type results for unions of comparability graphs
• Some geometric applications of Dilworth's theorem
• The isoperimetric number of random regular graphs
• Turán-type results for complete h-partite graphs in comparability and incomparability graphs
• Turán-type results for partial orders and intersection graphs of convex sets

Cited in

(4)

• Large homogeneous submatrices
• Improved Bounds for the Ramsey Number of Tight Cycles Versus Cliques
• scientific article; zbMATH DE number 7559254 (Why is no real title available?)
• Ramsey-type results for unions of comparability graphs

This page was built for publication: Improved Ramsey-type results for comparability graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4987258)