14:00
There is a growing body of results in extremal combinatorics and Ramsey theory which give better bounds or stronger conclusions under the additional assumption of bounded VC-dimension. Schur and Erdős conjectured that there exists a suitable constant $c$ with the property that every graph with at least $2^{cm}$ vertices, whose edges are colored by $m$ colors, contains a monochromatic triangle. We prove this conjecture for edge-colored graphs such that the set system induced by the neighborhoods of the vertices with respect to each color class has bounded VC-dimension. This result is best possible up to the value of $c$.
Joint work with Jacob Fox and Andrew Suk.
Further Information
Part of the Oxford Discrete Maths and Probability Seminar, held via Zoom. Please see the seminar website for details.