Maximal chains of isomorphic subgraphs of the Rado graph (Q485527)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Maximal chains of isomorphic subgraphs of the Rado graph |
scientific article |
Statements
Maximal chains of isomorphic subgraphs of the Rado graph (English)
0 references
9 January 2015
0 references
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.
0 references
Rado graph
0 references
isomorphic copy
0 references
maximal chain
0 references
compact set
0 references