On homogeneous sets of positive integers
type: Item
instance of: scholarly article
title: On homogeneous sets of positive integers
zbMATH Open document ID: 1015.05091
DOI: 10.1016/S0097-3165(03)00026-8
published in: Journal of Combinatorial Theory. Series A
publication date: 2003-05-27T00:00:00Z
review text: This paper solves affirmatively the longstanding conjecture of Paul Erdős in Ramsey theory on two-colourations of the pairs of the first \(n\) positive integers. It shows that in any two-colouration of \([n]^2\), for sufficiently large natural number \(n,\) there exists a homogeneous set \(H \subseteq [n]\) (all pairs in \(H\) belong to the same colour class) such that the elements of \(H\) are relatively small. More precisely, \(H\) satisfies \(\min H \geq 2\) and \[ \sum_{h \in H} {1 \over \log h} \geq C {\log \log \log \log n \over \log \log \log \log \log n}. \]
Mathematics Subject Classification ID: 05D10
zbMATH DE Number: 1917923
zbMATH Keywords: Ramsey theory
zbMATH Keywords: probabilistic method
author: Vojtěch Rödl
reviewed by: Péter L. Erdős
MaRDI profile type: Publication
cites work: The probabilistic method. With an appendix on the life and work of Paul Erdős.
cites work: Some remarks on the theory of graphs
cites work: On the combinatorial problems which I would most like to see solved
cites work: Q4065548
cites work: Q5759552
cites work: Q4871790
full work available at URL: s0097-3165(03)00026-8
OpenAlex ID: W2056828389
description: scientific article; zbMATH DE number 1917923