We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Partitions of large Rado graphs.
- Authors
Džamonja, M.; Larson, J. A.; Mitchell, W. J.
- Abstract
Let κ be a cardinal which is measurable after generically adding $${\beth_{\kappa+\omega}}$$ many Cohen subsets to κ and let $${\mathcal G= ( \kappa,E )}$$ be the κ-Rado graph. We prove, for 2 ≤ m < ω, that there is a finite value $${r_m^+}$$ such that the set [ κ] m can be partitioned into classes $${\langle{C_i:i<r^{+} _m}\rangle}$$ such that for any coloring of any of the classes C i in fewer than κ colors, there is a copy $${\mathcal{G} ^\ast}$$ of $${\mathcal G}$$ in $${\mathcal G}$$ such that $${[\mathcal{G} ^\ast ] ^m\cap C_i}$$ is monochromatic. It follows that $${\mathcal{G}\rightarrow (\mathcal{G} ) ^m_{<\kappa/r_m^+}}$$, that is, for any coloring of $${[ \mathcal {G} ] ^m}$$ with fewer than κ colors there is a copy $${\mathcal{G} ^{\prime}}$$ of $${\mathcal{G}}$$ such that $${[\mathcal{G} ^{\prime} ] ^{m}}$$ has at most $${r_m^+}$$ colors. On the other hand, we show that there are colorings of $${\mathcal{G}}$$ such that if $${\mathcal{G} ^{\prime}}$$ is any copy of $${\mathcal{G}}$$ then $${C_i\cap [\mathcal{G} ^{\prime} ] ^m\not=\emptyset}$$ for all $${i<r^{+} _m}$$, and hence $${\mathcal{G}\nrightarrow [ \mathcal{G} ] ^{m} _{r^{+} _m}}$$ . We characterize $${r_m^+}$$ as the cardinality of a certain finite set of types and obtain an upper and a lower bound on its value. In particular, $${r_2^+=2}$$ and for m > 2 we have $${r_m^+ > r_m}$$ where r m is the corresponding number of types for the countable Rado graph.
- Subjects
PARTITIONS (Mathematics); NUMBER theory; CHARTS, diagrams, etc.; GRAPHIC methods; HALL polynomials; YOUNG tableaux
- Publication
Archive for Mathematical Logic, 2009, Vol 48, Issue 6, p579
- ISSN
0933-5846
- Publication type
Article
- DOI
10.1007/s00153-009-0138-2