Maximal chains of isomorphic subgraphs of the Rado graph

DOI10.1007/S10474-013-0341-9MaRDI QIDQ485527zbMATH OpenOpenAlexFDO

Authors Miloš S. Kurilić, Boriša Kuzeljević

Publication date 9 January 2015

Published in Acta Mathematica Hungarica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10474-013-0341-9

zbMATH Keywords

compact setisomorphic copymaximal chainRado graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Total orders (06A05) Partial orders, general (06A06)

Review text

The paper under review considers the set of edges \(E(R)\) of the Rado graph \(R\), i.e. the unique graph on a countable vertex set with the property that for any disjoint finite sets of vertices \(A\) and \(B\) there is a vertex adjacent to every vertex in \(A\) and to no vertex in \(B\). The inclusion partial order is put on the partially ordered set \((E(R)\cup\emptyset,\subset)\) and we investigate maximal chains in this partial order. The aim is to find the possibilities for the order type of maximal chains in this poset. The main result is Theorem 2 of the paper, which states that for each linear order \(L\) three conditions are equivalent: (a) \(L\) is isomorphic to a maximal chain in the poset \((E(R)\cup \emptyset, \subset)\), (b) \(L\) is an \(\mathbb{R}\)-embeddable complete linear order, whose minimal element \(0_{L}\) is not isolated, (c) \(L\) is isomorphic to a compact subset \(K\) of \(\{0,1]\) with \(1\in K\) and 0 being an accumulation point of \(K\). The equivalence of (b) and (c) was already proved by the first author but the rest is new. The result is analogous to one proved when instead of examining maximal chains in \((E(R)\cup\emptyset,\subset)\) the ordered set is the rational line. A range of ideas about partial orders are used in the proof.

Recommendations

• Maximal antichains of isomorphic subgraphs of the Rado graph
• Maximal chains of isomorphic subgraphs of countable ultrahomogeneous graphs
• Maximal chordal subgraphs
• scientific article; zbMATH DE number 637283
• scientific article; zbMATH DE number 3847425
• Toward a graph version of Rado's theorem
• Maximum subgraphs in Ramsey graphs
• Graphs isomorphic to their maximum matching graphs
• On maximal chain subgraphs and covers of bipartite graphs
• A graphical characterization of the largest chain graphs

Cites work

• Asymmetric graphs
• scientific article; zbMATH DE number 3767656 (Why is no real title available?)
• scientific article; zbMATH DE number 3212886 (Why is no real title available?)
• Maximal chains in atomic Boolean algebras
• Maximal chains in interval algebras
• Maximal chains in positive subfamilies of P( )
• Maximal chains of copies of the rational line
• The random graph

Cited in

(8)

• Copies of the random graph
• Maximal chains of isomorphic suborders of countable ultrahomogeneous partial orders.
• Maximal chains of copies of the rational line
• Maximal chains of isomorphic subgraphs of countable ultrahomogeneous graphs
• On the structure of random hypergraphs
• Maximal antichains of isomorphic subgraphs of the Rado graph
• Another look at the Erdős-Hajnal-Pósa results on partitioning edges of the Rado graph
• Forcing with copies of the Rado and Henson graphs

This page was built for publication: Maximal chains of isomorphic subgraphs of the Rado graph

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