Bounded VC-Dimension Implies the Schur-Erdős Conjecture
| Autor: | Jacob Fox, Andrew Suk, János Pach |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
Class (set theory)
Conjecture Mathematics::Combinatorics 010102 general mathematics Complete graph Ramsey theory 0102 computer and information sciences 01 natural sciences Combinatorics VC-dimension Computational Mathematics VC dimension Integer 010201 computation theory & mathematics Simple (abstract algebra) Bounded function Multicolor Ramsey numbers FOS: Mathematics Discrete Mathematics and Combinatorics Mathematics - Combinatorics Ramsey's theorem Combinatorics (math.CO) 0101 mathematics Mathematics |
| Zdroj: | Combinatorica |
| DOI: | 10.4230/lipics.socg.2020.46 |
| Popis: | In 1916, Schur introduced the Ramsey number r(3;m), which is the minimum integer n > 1 such that for any m-coloring of the edges of the complete graph K_n, there is a monochromatic copy of K₃. He showed that r(3;m) ≤ O(m!), and a simple construction demonstrates that r(3;m) ≥ 2^Ω(m). An old conjecture of Erdős states that r(3;m) = 2^Θ(m). In this note, we prove the conjecture for m-colorings with bounded VC-dimension, that is, for m-colorings with the property that the set system induced by the neighborhoods of the vertices with respect to each color class has bounded VC-dimension. LIPIcs, Vol. 164, 36th International Symposium on Computational Geometry (SoCG 2020), pages 46:1-46:8 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|