Journal of Combinatorics

Volume 10 (2019)

Number 1

Discrepancy and large dense monochromatic subsets

Pages: 87 – 109

DOI: https://dx.doi.org/10.4310/JOC.2019.v10.n1.a4

Authors

Ross J. Kang (Department of Mathematics, IMAPP, Radboud University, Nijmegen, The Netherlands)

Viresh Patel (Korteweg de Vries Institute for Mathematics, University of Amsterdam, The Netherlands)

Guus Regts (Korteweg de Vries Institute for Mathematics, University of Amsterdam, The Netherlands)

Abstract

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.

Keywords

Ramsey theory, quasi-Ramsey numbers, hypergraph discrepancy, probabilistic method

2010 Mathematics Subject Classification

Primary 05C55. Secondary 05D10, 05D40.

Full Text (PDF format)

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