Two remarks on Ramsey's theorem
type: Item
instance of: scholarly article
title: Two remarks on Ramsey's theorem
zbMATH Open document ID: 0567.05005
DOI: 10.1016/0012-365X(85)90118-9
author: J. Nešetřil
author: Vojtěch Rödl
published in: Discrete Mathematics
publication date: 1985-01-01T00:00:00Z
review text: For two classical results of Ramsey theory new simple proofs are given: Theorem (Erdős, Rado): (AC) for all \(\gamma\), \(\gamma \nrightarrow (\omega)_ 2^{\omega}\). This is reduced to the fact that using AC a bipartite graph may be 2-colored. Theorem (Deuber; Něsetřil, Rödl). Let \(k,p<\omega\). For every finite graph G there exists a graph H such that \(H\to (G)_ k^{K_ p}\). This ingeniously simple proof makes use of the Graham-Rothschild theorem for n-parametersets, applied to setsystems.
Mathematics Subject Classification ID: 05A17
Mathematics Subject Classification ID: 05C55
Mathematics Subject Classification ID: 03E25
zbMATH DE Number: 3904593
zbMATH Keywords: Ramsey bipartite graphs
zbMATH Keywords: n-parameters
zbMATH Keywords: Ramsey theory
zbMATH Keywords: Erdős
zbMATH Keywords: Rado
zbMATH Keywords: Deuber
zbMATH Keywords: Něsetřil
zbMATH Keywords: Rödl
MaRDI profile type: Publication
cites work: Partitionstheoreme für Graphen
cites work: A partition calculus in set theory
cites work: Ramsey's Theorem for n-Parameter Sets
cites work: Q4088856
cites work: Partitions of finite relational and set systems
full work available at URL: 0012-365x(85)90118-9
OpenAlex ID: W1969530432
description: scientific article; zbMATH DE number 3904593