Partitions of large Rado graphs (Q834717)

From MaRDI portal





scientific article; zbMATH DE number 5598855
Language Label Description Also known as
default for all languages
No label defined
    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