# zbMATH — the first resource for mathematics

Copies of the random graph. (English) Zbl 1423.03189
Summary: Let $$\langle R, \sim \rangle$$ be the Rado graph, $$\mathrm{Emb}(R)$$ the monoid of its self-embeddings, $$\mathbb{P}(R) = \{f(R) : f \in \mathrm{Emb}(R) \}$$ the set of copies of $$R$$ contained in $$R$$, and $$\mathcal{I}_R$$ the ideal of subsets of $$R$$ which do not contain a copy of $$R$$. We consider the poset $$\langle \mathbb{P}(R), \subset \rangle$$, the algebra $$P(R) / \mathcal{I}_R$$, and the inverse of the right Green’s preorder on $$\mathrm{Emb}(R)$$, and show that these preorders are forcing equivalent to a two step iteration of the form $$\mathbb{P} \ast \pi$$, where the poset $$\mathbb{P}$$ is similar to the Sacks perfect set forcing: adds a generic real, has the $$\aleph_0$$-covering property and, hence, preserves $$\omega_1$$, has the Sacks property and does not produce splitting reals, while $$\pi$$ codes an $$\omega$$-distributive forcing. Consequently, the Boolean completions of these four posets are isomorphic and the same holds for each countable graph containing a copy of the Rado graph.

##### MSC:
 03E40 Other aspects of forcing and Boolean-valued models 05C80 Random graphs (graph-theoretic aspects) 03C15 Model theory of denumerable and separable structures 03C50 Models with special properties (saturated, rigid, etc.) 06A06 Partial orders, general 20M20 Semigroups of transformations, relations, partitions, etc.
Full Text:
##### References:
  Cameron, P. J., The random graph, (The Mathematics of Paul Erdös II, Algorithms Combin., vol. 14, (1997), Springer Berlin), 333-351 · Zbl 0864.05076  Erdös, P.; Rényi, A., Asymmetric graphs, Acta Math. Acad. Sci. Hungar., 14, 295-315, (1963) · Zbl 0118.18901  Fraïssé, R., Theory of relations, Studies in Logic and the Foundations of Mathematics, vol. 145, (2000), North-Holland Amsterdam, with an appendix by Norbert Sauer · Zbl 0593.04001  Halpern, J. D.; Läuchli, H., A partition theorem, Trans. Amer. Math. Soc., 124, 360-367, (1966) · Zbl 0158.26902  Hodges, W., Model theory, Encyclopedia of Mathematics and Its Applications, vol. 42, (1993), Cambridge University Press Cambridge  Jech, T., Multiple forcing, Cambridge Tracts in Mathematics, vol. 88, (1986), Cambridge University Press Cambridge · Zbl 0601.03019  Jech, T., Set theory, Perspectives in Mathematical Logic, (1997), Springer-Verlag Berlin · Zbl 0882.03045  Kurilić, M. S., From $$A_1$$ to $$D_5$$: towards a forcing-related classification of relational structures, J. Symbolic Logic, 79, 1, 279-295, (2014) · Zbl 1337.03042  Kurilić, M. S., Posets of copies of countable scattered linear orders, Ann. Pure Appl. Logic, 165, 895-912, (2014) · Zbl 1297.06001  Kurilić, M. S., Forcing with copies of countable ordinals, Proc. Amer. Math. Soc., 143, 4, 1771-1784, (2015) · Zbl 1386.03065  Kurilić, M. S., Different similarities, Arch. Math. Logic, 54, 7-8, 839-859, (2015) · Zbl 1373.03049  Kurilić, M. S.; Kuzeljević, B., Maximal chains of isomorphic subgraphs of the Rado graph, Acta Math. Hungar., 141, 1, 1-10, (2013) · Zbl 1313.05342  Kurilić, M. S.; Marković, P., Maximal antichains of isomorphic subgraphs of the Rado graph, Filomat, 29, 9, 1919-1923, (2015) · Zbl 1464.05329  Kurilić, M. S.; Todorčević, S., Forcing by non-scattered sets, Ann. Pure Appl. Logic, 163, 1299-1308, (2012) · Zbl 1250.03102  Kurilić, M. S.; Todorčević, S., The poset of all copies of the random graph has the 2-localization property, Ann. Pure Appl. Logic, 167, 8, 649-662, (2016) · Zbl 1432.03059  Rado, R., Universal graphs and universal functions, Acta Arith., 9, 331-340, (1964) · Zbl 0139.17303  Todorčević, S., Introduction to Ramsey spaces, Annals of Mathematics Studies, vol. 174, (2010), Princeton University Press Princeton, NJ · Zbl 1205.05001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.