Monochromatic vs multicolored paths
Consider the following generalization of the problem of \textit{P. Erdős} and \textit{G. Szekeres} about monotone subsequences [Compos. Math. 2, 463-470 (1935; Zbl 0012.27010)]: let \(\Delta\) be an infinite set of colours. For \(l,k\) positive integers let \(f(l,k)\) be the least integer with the property that if \(| X|\geq f(l,k)+1\) then for every mapping \(\delta:X\times X\to\Delta\) either there exist elements \(y_ 0<y_ 1<\dots<y_ l\) of \(X\) with \(\delta(x_ 0,x_ 1)=\delta(x_ 1,x_ 2)=\cdots=\delta(x_{l-1},x_ l)\), or else there exist elements \(y_ 0<y_ 1<\cdots<y_ k\) of \(X\) with \(\delta(y_{i-1},y_ i)\neq\delta(y_{j-1},y_ j)\) for all \(1\leq i<j\leq k\). The existence of such an integer follows from the canonical Ramsey theorem (see \textit{P. Erdős} and \textit{R. Rado} [J. Lond. Math. Soc. 25, 249-255 (1950; Zbl 0038.153)]). This paper conjectures that for all positive integers \(l\) and \(k\), \(f(l,k)=l^{k-1}\). Here the cases \(l\leq 2\) or \(k\leq 4\) or \(l\geq(3k)^{2k}\) are proved.
- Ordered and canonical Ramsey numbers of stars
- Mixed hypergraphs with bounded degree: Edge-coloring of mixed multigraphs.
- New upper bounds for a canonical Ramsey problem
- Ramsey-Sperner theory
- In memoriam: Professor Robin Thomas (1962--2020)
- Coloring mixed hypertrees
- Flashes and rainbows in tournaments
- A note on a Ramsey-type problem for sequences
- Ascending waves
This page was built for publication: Monochromatic vs multicolored paths
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1205343)
