Discrepancy and large dense monochromatic subsets
| Autor: | Ross J. Kang, Guus Regts, Viresh Patel |
|---|---|
| Přispěvatelé: | Algebra, Geometry & Mathematical Physics (KDV, FNWI) |
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
Hypergraph
Mathematics::Combinatorics Degree (graph theory) Ramsey theory Complete graph 05C55 (Primary) 05D10 05D40 (Secondary) Combinatorics Probabilistic method Computer Science::Discrete Mathematics Bounded function FOS: Mathematics Mathematics - Combinatorics Monochromatic color Ramsey's theorem Combinatorics (math.CO) Mathematics |
| Zdroj: | Journal of Algebraic Combinatorics, 10(1), 87-109. Springer Netherlands Journal of Combinatorics, 10, 87-109 Journal of Combinatorics, 10, 1, pp. 87-109 |
| ISSN: | 1572-9192 0925-9899 2156-3527 |
| DOI: | 10.4310/JOC.2019.v10.n1.a4 |
| Popis: | 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. Comment: 14 pages; some minor changes suggest by a referee. Accepted in Journal of Combinatorics |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink