Monochromatic vs multicolored paths (Q1205343): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: A Combinatorial Theorem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5759552 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5545303 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5750908 / rank | |||
Normal rank |
Revision as of 15:13, 17 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Monochromatic vs multicolored paths |
scientific article |
Statements
Monochromatic vs multicolored paths (English)
0 references
1 April 1993
0 references
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.
0 references
infinite colour set
0 references
monotone subsequences
0 references
Ramsey theorem
0 references