Discrepancy and large dense monochromatic subsets

DOI10.4310/JOC.2019.V10.N1.A4zbMATH Open1401.05193arXiv1610.06359WikidataQ128829997 ScholiaQ128829997MaRDI QIDQ1630686FDOQ1630686

Authors: Ross J. Kang, Viresh Patel, Guus Regts 

Publication date: 10 December 2018

Published in: Journal of Combinatorics (Search for Journal in Brave)

Abstract: ErdH{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.

Full work available at URL: https://arxiv.org/abs/1610.06359

Recommendations

• Large almost monochromatic subsets in hypergraphs
• A precise threshold for quasi-Ramsey numbers
• Multi-color discrepancies
• Quasi-random graphs of given density and Ramsey numbers
• The Ramsey number of dense graphs

zbMATH Keywords

Ramsey theoryprobabilistic methodquasi-Ramsey numbershypergraph discrepancy

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Ramsey theory (05D10) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Cited In (3)

• Large almost monochromatic subsets in hypergraphs
• The upper logarithmic density of monochromatic subset sums
• Ramsey functions for quasi-progressions

This page was built for publication: Discrepancy and large dense monochromatic subsets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1630686)