pith. sign in

arxiv: 1610.06359 · v2 · pith:KLENXZB2new · submitted 2016-10-20 · 🧮 math.CO

Discrepancy and large dense monochromatic subsets

classification 🧮 math.CO
keywords monochromaticnumbersdiscrepancylargequasi-ramseyacrossaveragebounded
0
0 comments X
read the original abstract

Erd\H{o}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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.