Bounded \(VC\)-dimension implies the Schur-Erdős conjecture (Q2064760)

Let \(\mathcal{F}\) be a set system on the ground set \(V\). The VC-dimension of \(\mathcal{F}\) is the largest integer \(d\) for which there exists a \(d\)-element set \(S \subset V\) such that for every subset \(B \subset V\), one can find a member \(A \in \mathcal{F}\) with \(A \cap S = B\). A set system is said to have dual VC-dimension \(d\) if its dual set system has VC-dimension \(d\). Let \(\chi\) be an \(m\)-coloring of the edges of the complete graph \(K_n\). The coloring \(\chi\) is said to have VC-dimension (or dual VC-dimension) \(d\) if the set system induced by the neighborhoods of the vertices with respect to each color class has VC-dimension (resp., dual VC-dimension) \(d\). For \(k \geq 3\), \(m \geq 2\), and \(d \geq 2\), let \(r_d(k;m)\) denote the smallest integer \(n\) such that any \(m\)-coloring of the edges of \(K_n\) with dual VC-dimension at most \(d\) contains a monochromatic clique of size \(k\). This note establishes the following special case for an old conjecture of \textit{P. Erdős} [Mitt. Forsch.-Inst. Math. Mech. Univ. Tomsk 2, 74--82 (1938; Zbl 0020.00504)]. For every \(k \geq 3\) and \(d \geq 2\), there is a constant \(c = c(k;d)\) such that \(r_d(k;m) \leq 2^{cm}\).