There is no universal countable random-free graph

DOI10.1016/J.DISC.2004.01.002MaRDI QIDQ1827759zbMATH OpenOpenAlexFDO

Authors Masasi Higasikawa

Publication date 6 August 2004

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Random graphInfinite graphStrong embeddability

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (05C99)

Abstract: We consider embeddings between infinite graphs. In particular, We establish that there is no universal element in the class of countable graphs into which the random graph is not embeddable.

Recommendations

• On the existence of countable universal graphs
• Some remarks on universal graphs
• There is no universal countable pentagon‐free graph
• Nonexistence of universal graphs without some trees
• All countable monoids embed into the monoid of the infinite random graph

Cites work

• scientific article; zbMATH DE number 44603 (Why is no real title available?)
• On the order of countable graphs
• Representing Embeddability as Set Inclusion
• Some remarks on universal graphs
• Universal elements and the complexity of certain classes of infinite graphs

Cited in

(3)

• The poset of all copies of the random graph has the 2-localization property
• Uncountable graphs and invariant measures on the set of universal countable graphs
• Universal elements and the complexity of certain classes of infinite graphs

This page was built for publication: There is no universal countable random-free graph

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