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.

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: DOI
[1] 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
[2] Erdös, P.; Rényi, A., Asymmetric graphs, Acta Math. Acad. Sci. Hungar., 14, 295-315, (1963) · Zbl 0118.18901
[3] 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
[4] Halpern, J. D.; Läuchli, H., A partition theorem, Trans. Amer. Math. Soc., 124, 360-367, (1966) · Zbl 0158.26902
[5] Hodges, W., Model theory, Encyclopedia of Mathematics and Its Applications, vol. 42, (1993), Cambridge University Press Cambridge
[6] Jech, T., Multiple forcing, Cambridge Tracts in Mathematics, vol. 88, (1986), Cambridge University Press Cambridge · Zbl 0601.03019
[7] Jech, T., Set theory, Perspectives in Mathematical Logic, (1997), Springer-Verlag Berlin · Zbl 0882.03045
[8] 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
[9] Kurilić, M. S., Posets of copies of countable scattered linear orders, Ann. Pure Appl. Logic, 165, 895-912, (2014) · Zbl 1297.06001
[10] Kurilić, M. S., Forcing with copies of countable ordinals, Proc. Amer. Math. Soc., 143, 4, 1771-1784, (2015) · Zbl 1386.03065
[11] Kurilić, M. S., Different similarities, Arch. Math. Logic, 54, 7-8, 839-859, (2015) · Zbl 1373.03049
[12] 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
[13] Kurilić, M. S.; Marković, P., Maximal antichains of isomorphic subgraphs of the Rado graph, Filomat, 29, 9, 1919-1923, (2015) · Zbl 1464.05329
[14] Kurilić, M. S.; Todorčević, S., Forcing by non-scattered sets, Ann. Pure Appl. Logic, 163, 1299-1308, (2012) · Zbl 1250.03102
[15] 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
[16] Rado, R., Universal graphs and universal functions, Acta Arith., 9, 331-340, (1964) · Zbl 0139.17303
[17] 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.