2016/10/20 by Ross J. Kang, Ross Kang, Kang, Ross +4
Computer Science · Mathematics · #05C55 (Primary) #05D10 #05D40 (Secondary) #Advanced Topology and Set Theory #Combinatorics (math.CO) #Digital Image Processing Techniques #FOS: Mathematics #Limits and Structures in Graph Theory #math.CO #msc:05C55 #msc:05D10 #msc:05D40
paper · pdf · doi:10.48550/arxiv.1610.06359
14 pages; some minor changes suggest by a referee. Accepted in Journal of Combinatorics
openalex publication_date 2016/10/20 · arxiv created 2018/01/10 · arxiv updated 2018/01/11 · openalex created_date 2019/07/30 · openalex updated_date 2026/07/28
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.