Partitions of large Rado graphs (Q834717)

From MaRDI portal





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
    0 references
    0 references
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references