Partitions of large Rado graphs (Q834717)
From MaRDI portal
| This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Partitions of large Rado graphs |
scientific article; zbMATH DE number 5598855
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Partitions of large Rado graphs |
scientific article; zbMATH DE number 5598855 |
Statements
Partitions of large Rado graphs (English)
0 references
27 August 2009
0 references
For infinite cardinal numbers \(\kappa\) satisfying \(\kappa^{<\kappa}=\kappa\), the \(\kappa\)-Rado graph \(\mathcal{G}_{\kappa}\) is the graph whose vertex set is \(\kappa\) and which has the property that for all disjoint sets \(A,B\subseteq\kappa\), each of size \(<\kappa\), there is a vertex \(c\in\kappa\) such that there is an edge from \(c\) to each element of \(A\), but no edge to any element of \(B\). In the paper, models of ZFC are constructed in which there exists a measurable cardinal \(\kappa\) with the following property: For all integers \(m\geq 2\) there exists a positive integer \(r_m\) and a partition of \([\kappa]^m\) (the \(m\)-element subsets of \(\kappa\)) into \(r_m\) classes \(\langle C_i:0\leq i<r_m\rangle\), such that for any colouring of any of the classes \(C_j\) with fewer than \(\kappa\) colours, there is a subgraph \(\mathcal{G}^*=(V,E)\) of \(\mathcal{G}_{\kappa}\) which is isomorphic to \(\mathcal{G}_{\kappa}\), such that \([V]^m\cap C_j\) is monochromatic. As a consequence one gets that for any colouring of \([\kappa]^m\) with fewer than \(\kappa\) colours, there is a copy \(\mathcal{G}'=(V',E')\) of \(\mathcal{G}_{\kappa}\) such that \([V']^m\) has at most \(r_m\) colours.
0 references
Rado graph
0 references
random graph
0 references
partitions of graphs
0 references
generalized Ramsey theory
0 references
Cohen forcing
0 references
0.93694556
0 references
0 references
0.9033697
0 references
0 references
0.90027535
0 references
0 references