Journal of Combinatorics
Volume 10 (2019)
Discrepancy and large dense monochromatic subsets
Pages: 87 – 109
Erdös and Pach (1983) introduced the natural degree-based generalisations of Ramsey numbers, where instead of seeking large monochromatic cliques in a 2-edge coloured complete graph, we seek monochromatic subgraphs of high minimum or average degree. Here we expand the study of these so-called quasi-Ramsey numbers in a few ways, in particular, to multiple colours and to uniform hypergraphs.
Quasi-Ramsey numbers are known to exhibit a certain unique phase transition and we show that this is also the case across the settings we consider. Our results depend on a density-biased notion of hypergraph discrepancy optimised over sets of bounded size, which may be of independent interest.
Ramsey theory, quasi-Ramsey numbers, hypergraph discrepancy, probabilistic method
2010 Mathematics Subject Classification
Primary 05C55. Secondary 05D10, 05D40.
The work of Ross J. Kang was initiated while the author was supported by a Veni grant from the Netherlands Organisation for Scientific Research (NWO).
Viresh Patel was supported by NWO through the Gravitation Programme Networks (024.002.003).
Guus Regts was supported by a personal NWO Veni grant.
Received 20 October 2016
Published 7 December 2018