Some Ramsey-type theorems

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\).

Recommendations

Cites work

Cited in

(29)

This page was built for publication: Some Ramsey-type theorems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1174169)