Improved Ramsey-type results for comparability graphs

DOI10.1017/S0963548320000103zbMATH Open1462.05250arXiv1810.00588MaRDI QIDQ4987258FDOQ4987258

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

Publication date: 30 April 2021

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

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.

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

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

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)

Cites Work

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

Cited In (4)

• Large homogeneous submatrices
• Improved Bounds for the Ramsey Number of Tight Cycles Versus Cliques
• Title not available (Why is that?)
• 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)