Remarks on a Ramsey theory for trees (Q2392039): Difference between revisions

The authors use a randomized coloring algorithm, called random split, to prove two quantitative versions of Furstenberg-Weiss results from [\textit{H.~Furstenberg} and \textit{B.~Weiss}, Comb. Probab. Comput. 12, No. 5--6, 547--563 (2003; Zbl 1061.05094)]. Theorem: Let \(d\), \(n\) be positive integers, and let \(H\) be a subset of the vertex set of the vertex set of the binary tree \(T_n\) satisfying \[ 2^{w(H)}> \sum_{i=0}^{d-1}{n \choose i}. \] Then \(H\) contains a replica of \(T_d\). Here \(w(H) = \sum_{x\in H}w(x)\), \(w(x) = 2^{-l(x)}\), \(l(x)\) is the level of \(x\) in \(T_n\). Theorem: Let \(k,d,n \geqslant 2\) be integers. (i) Suppose that \(n > 5dk \log k\). Then, for any coloring of the vertices of \(T_n\) with \(k\) colors, one can find in \(T_n\) a monochromatic replica of \(T_d\). (ii) If \(n\leqslant (d-1)k\log (k/6)\), then there exists a coloring of \(T_n\) with \(k\) colors such that contains no monochromatic replica of \(T_d\).