2019/10/26 by Bogdan Alecu, Aistis Atminas, Alecu, Bogdan +5
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1910.12109
24 pages
arxiv created 2020/12/04 · arxiv updated 2020/12/07
The Ramsey number RX(p,q) for a class of graphs X is the minimum n such that every graph in X with at least n vertices has either a clique of size p or an independent set of size q. We say that Ramsey numbers are linear in X if there is a constant k such that RX(p,q) ≤ k(p+q) for all p,q. In the present paper we conjecture that if X is a hereditary class defined by finitely many forbidden induced subgraphs, then Ramsey numbers are linear in X if and only if X excludes a forest, a disjoint union of cliques and their complements. We prove the "only if" part of this conjecture and verify the "if" part for a variety of classes. We also apply the notion of linearity to bipartite Ramsey numbers and reveal a number of similarities and differences between the bipartite and non-bipartite case.