The poset of all copies of the random graph has the 2-localization property

DOI10.1016/J.APAL.2016.04.001zbMATH Open1432.03059arXiv1411.3144OpenAlexW2337591713MaRDI QIDQ286593FDOQ286593

Authors: Miloš S. Kurilić, Stevo Todorčević 

Publication date: 20 May 2016

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Abstract: Let $G$ be a countable graph containing a copy of the countable random graph (ErdH{o}s-R'enyi graph, Rado graph), $Emb(G)$ the monoid of its self-embeddings, $mathbbP(G)=f[G]:finEmb(G)$ the set of copies of $G$ contained in $G$, and ${mathcalI}_G$ the ideal of subsets of $G$ which do not contain a copy of $G$. We show that the poset $<mathbbP(G),subset>$, the algebra $P(G)/{mathcalI}_G$, and the inverse of the right Green's pre-order $<Emb(G),prece{q}^R>$ have the 2-localization property. The Boolean completions of these pre-orders are isomorphic and satisfy the following law: for each double sequence $[b_{nm}:<n,m>inomegaimesomega]$ of elements of $mathbbB$ ${\displaystyle }$ extstyle �igwedge_{n in omega}; �igvee_{m in omega}; b_{nm} = �igvee_{{mathcal T} ,in , Bt ({}^{<omega}omega)}; �igwedge_{n in omega}; �igvee_{varphi ,in ,{mathcal T} cap {}^{n+1}omega}; �igwedge_{kleq n}; b_{kvarphi (k)}, ${\displaystyle }$ where $Bt({}^{<omega}omega)$ denotes the set of all binary subtrees of the tree ${}^{<omega}omega$.

Full work available at URL: https://arxiv.org/abs/1411.3144

Recommendations

• Copies of the random graph
• On retracts of the random graph and their natural order
• There is no universal countable random-free graph
• The monoid of the random graph
• The endomorphism monoid of the random poset contains all countable semigroups

zbMATH Keywords

forcing2-localizationcountable random graphisomorphic substructureright Green's pre-orderself-embedding

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Partial orders, general (06A06) Models with special properties (saturated, rigid, etc.) (03C50) Semigroups of transformations, relations, partitions, etc. (20M20) Other aspects of forcing and Boolean-valued models (03E40)

Cites Work

• Isomorphic and strongly connected components
• The poset of all copies of the random graph has the 2-localization property
• From \(A_{1}\) to \(D_{5}\): towards a forcing-related classification of relational structures
• n–localization property
• Maximally embeddable components
• Posets of copies of countable scattered linear orders
• Forcing by non-scattered sets
• Title not available (Why is that?)
• The Ideal Determined by the Unsymmetric Game
• Forcing with copies of countable ordinals
• Universal graphs and universal functions
• The random graph
• Asymmetric graphs
• Different similarities

Cited In (8)

• Posets of copies of countable ultrahomogeneous tournaments
• The poset of all copies of the random graph has the 2-localization property
• Different similarities
• Forcing with copies of the Rado and Henson graphs
• Antichains of copies of ultrahomogeneous structures
• Indivisible sets and well-founded orientations of the Rado graph
• Copies of the random graph
• Posets of copies of countable non-scattered labeled linear orders

This page was built for publication: The poset of all copies of the random graph has the 2-localization property

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q286593)