Discrepancy and large dense monochromatic subsets

Open Access
Authors
Publication date 2019
Journal Journal of Algebraic Combinatorics
Volume | Issue number 10 | 1
Pages (from-to) 87-109
Organisations
  • Faculty of Science (FNWI) - Korteweg-de Vries Institute for Mathematics (KdVI)
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.
Document type Article
Language English
Published at https://doi.org/10.4310/JOC.2019.v10.n1.a4
Published at https://arxiv.org/abs/1610.06359
Downloads
Permalink to this page
Back