Discrepancy and large dense monochromatic subsets
| Authors | |
|---|---|
| Publication date | 2019 |
| Journal | Journal of Algebraic Combinatorics |
| Volume | Issue number | 10 | 1 |
| Pages (from-to) | 87-109 |
| Organisations |
|
| 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 |
Discrepancy and large dense monochromatic subsets subm. vers
(Submitted manuscript)
|
| Permalink to this page | |