A consistent edge partition theorem for infinite graphs
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).
- Embedding Graphs into Colored Graphs
- Consistency results on infinite graphs
- NOTES ON SOME ERDŐS–HAJNAL PROBLEMS
- A note on chromatic number and connectivity of infinite graphs
- Generic graph construction
- scientific article; zbMATH DE number 3902684
- Identities on cardinals less than ℵω
- Finite subgraphs of uncountably chromatic graphs
- On Taylor's problem
- scientific article; zbMATH DE number 940707
- A partition calculus in set theory
- Coloring of universal graphs
- Embedding finite graphs into graphs colored with infinitely many colors
- Embedding Graphs into Colored Graphs
- Graphs with Monochromatic Complete Subgraphs in Every Edge Coloring
- On decomposition of graphs
- Partitions of finite relational and set systems
- Partitionstheoreme für Graphen
- The Ramsey property for graphs with forbidden complete subgraphs
- The Erdős-Dushnik-Miller theorem for topological graphs and orders
- Tree-partitions of infinite graphs
- Embedding theorems for graphs establishing negative partition relations
- Monochromatic trees with respect to edge partitions
- Edge partitions of the countable triangle free homogeneous graph
- Ramsey theory for highly connected monochromatic subgraphs
- A Ramsey-style extension of a theorem of Erdős and Hajnal
- scientific article; zbMATH DE number 4142066 (Why is no real title available?)
- Embedding Graphs into Colored Graphs
- Colorful Partitions of Cardinal Numbers
- scientific article; zbMATH DE number 3487493 (Why is no real title available?)
- scientific article; zbMATH DE number 1795293 (Why is no real title available?)
- scientific article; zbMATH DE number 940707 (Why is no real title available?)
- scientific article; zbMATH DE number 4118372 (Why is no real title available?)
- NOTES ON SOME ERDŐS–HAJNAL PROBLEMS
- Constructions of infinite graphs with Ramsey property
- Wild edge colourings of graphs
- The Erdős-Hajnal problem list
This page was built for publication: A consistent edge partition theorem for infinite graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1332974)
