×

zbMATH — the first resource for mathematics

Maximal chains of isomorphic subgraphs of the Rado graph. (English) Zbl 1313.05342
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.

MSC:
05C80 Random graphs (graph-theoretic aspects)
06A05 Total orders
06A06 Partial orders, general
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Cameron, P. J.; Graham, R. L. (ed.); Nešetřil, J. (ed.), The random graph, No. 14, 333-351, (1997), Berlin, Heidelberg · Zbl 0864.05076
[2] Day, G. W., Maximal chains in atomic Boolean algebras, Fund. Math., 67, 293-296, (1970) · Zbl 0195.03303
[3] Erdős, P.; Rényi, A., Asymmetric graphs, Acta Math. Acad. Sci. Hungar., 14, 295-315, (1963) · Zbl 0118.18901
[4] Koppelberg, S., Maximal chains in interval algebras, Algebra Univers., 27, 32-43, (1990) · Zbl 0699.06001
[5] K. Kuratowski, Sur la notion de l’ordre dans la théorie des ensembles, Fund. Math., 2 (1921), 161-171. · JFM 48.0204.01
[6] Kurilić, M. S., Maximal chains in positive subfamilies of \(P\)(\(ω\)), Order, 29, 119-129, (2012) · Zbl 1257.06001
[7] M. S. Kurilić, Maximal chains of copies of the rational line, Order, in print, doi: 10.1007/s11083-012-9273-1. · Zbl 0195.03303
[8] J. G. Rosenstein, Linear Orderings, Pure and Applied Mathematics 98, Academic Press Inc. (New York, London, 1982).
[9] A. Sierpiński, Cardinal and Ordinal Numbers, PWN (Warszawa, 1965). · Zbl 0131.24801
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.