A consistent edge partition theorem for infinite graphs
type: Item
instance of: scholarly article
title: A consistent edge partition theorem for infinite graphs
zbMATH Open document ID: 0823.03025
DOI: 10.1007/BF01872104
author: S. Shelah
author: Péter Komjáth
published in: Acta Mathematica Hungarica
publication date: 1994-09-05T00:00:00Z
review text: For graphs \(X\) and \(Y\) and cardinal number \(\mu\), the relation \(X\rightarrowtail (Y)^ 2_ \mu\) means that whenever the edges of the graph \(X\) are coloured with \(\mu\) colours, there is always an induced subgraph isomorphic to \(Y\), all the edges of which have the same colour. The general problem is for which infinite graphs \(Y\) and cardinals \(\mu\) does there exist a graph \(X\) for which \(X\rightarrowtail (Y)^ 2_ \mu\); the answer is independent. \textit{A. Hajnal} and the first author [Trans. Am. Math. Soc. 307, No. 1, 395-409 (1988; Zbl 0659.03029)] showed that it is consistent that there is a \(Y\) (of size \(\aleph_ 1\)) such that there is no \(X\) for which \(X\rightarrowtail (Y)^ 2_ 2\), whereas the second author [Set theory and its applications, Proc. Conf., Toronto/Can. 1987, Lect. Notes Math. 1401, 167-193 (1989; Zbl 0683.04002)] proved that it is consistent that for every \(Y\) and \(\mu\) there is an \(X\) such that \(X\rightarrowtail (Y)^ 2_ \mu\). In the paper under review, this last result is improved by showing that \(X\) can be chosen so that any complete subgraph absent from \(Y\) is also absent from \(X\): it is consistent that for every \(Y\) and \(\mu\) there is \(X\) such that \(X\rightarrowtail (U)^ 2_ \mu\), and further for each cardinal \(\alpha\), if \(Y\) contains no complete subgraph on \(\alpha\) vertices then neither does \(X\). (This also establishes the consistency of the following solution to a long-standing problem of Erdős and Hajnal: there is a graph \(X\) such that \(X\to (\omega)^ 2_ \omega\) and \(X\) contains no uncountable complete subgraph).
Mathematics Subject Classification ID: 03E35
Mathematics Subject Classification ID: 03E05
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 633889
zbMATH Keywords: partition relation
zbMATH Keywords: infinite graph
zbMATH Keywords: consistency
reviewed by: Neil H. Williams
MaRDI profile type: Publication
cites work: Partitionstheoreme für Graphen
cites work: On decomposition of graphs
cites work: A partition calculus in set theory
cites work: Graphs with Monochromatic Complete Subgraphs in Every Edge Coloring
cites work: Embedding finite graphs into graphs colored with infinitely many colors
cites work: Embedding Graphs into Colored Graphs
cites work: Coloring of universal graphs
cites work: The Ramsey property for graphs with forbidden complete subgraphs
cites work: Partitions of finite relational and set systems
Recommended article: Embedding Graphs into Colored Graphs
Recommended article: Consistency results on infinite graphs
Recommended article: NOTES ON SOME ERDŐS–HAJNAL PROBLEMS
Recommended article: A note on chromatic number and connectivity of infinite graphs
Recommended article: Generic graph construction
Recommended article: Q3680856
Recommended article: Identities on cardinals less than ℵω
Recommended article: Finite subgraphs of uncountably chromatic graphs
Recommended article: On Taylor's problem
Recommended article: Q4714217
description: scientific article; zbMATH DE number 633889