Some Ramsey-type theorems (Q1174169): Difference between revisions
From MaRDI portal
Latest revision as of 09:23, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Some Ramsey-type theorems |
scientific article |
Statements
Some Ramsey-type theorems (English)
0 references
25 June 1992
0 references
For any set \(A\) let \([A]^r\) denote the collection of \(r\)-element subsets of \(A\). By a \(k\)-coloring of the \(r\)-subsets of \(A\) we mean a function \(f:[A]^r\to\{1,\dots,k\}\). A set \(X\subset A\) is said to be \(f\)-homogeneous if \(f\) is a constant on \([X]^r\). The partition symbol \(a\to(x)^r_k\) denotes the assertion: given a set \(A\) with \(| A|=a\) and a coloring \(f: [A]^r\to\{1,\dots,k\}\), there is an \(f\)- homogeneous set \(X\subset A\) with \(|X| \leq x\). The main result of this paper is Theorem 2.1. Let \(r\) and \(k\) be positive integers, and let the function \(\varphi:\mathbb{N}\to\mathbb{R}\) be such that \(n\to(\varphi(n))^r_{k+1}\) holds for all sufficienty large \(n\). Given any coloring \(f: [\mathbb{N}]^r\to\{1,\dots,k\}\), there is a set \(A\subset\mathbb{N}\) such that: (1) \(|\{f(X): X\in[A]^r\}| \leq 2^{r-1}\); (2) \(|A\cap\{1,\dots,n\}| \geq \varphi(n)\) for infinitely many \(n\).
0 references
Ramsey-type theorems
0 references
homogeneous set
0 references
partition
0 references
coloring
0 references