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

DOI10.1016/J.APAL.2016.04.001MaRDI QIDQ286593zbMATH OpenOpenAlexFDO

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)

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

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)

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$.

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

Cites work

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

Cited in

(8)

• Indivisible sets and well-founded orientations of the Rado graph
• The poset of all copies of the random graph has the 2-localization property
• Posets of copies of countable ultrahomogeneous tournaments
• Antichains of copies of ultrahomogeneous structures
• Different similarities
• Copies of the random graph
• Forcing with copies of the Rado and Henson graphs
• 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)