Discrepancy and large dense monochromatic subsets

DOI10.4310/JOC.2019.V10.N1.A4MaRDI QIDQ1630686zbMATH OpenWikidataFDO

Authors Ross J. Kang, Viresh Patel, Guus Regts

Publication date 10 December 2018

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

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

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)

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.

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

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)