Maximal chains of isomorphic subgraphs of the Rado graph
type: Item
instance of: scholarly article
title: Maximal chains of isomorphic subgraphs of the Rado graph
zbMATH Open document ID: 1313.05342
published in: Acta Mathematica Hungarica
publication date: 2015-01-09T00:00:00Z
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.
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 06A05
Mathematics Subject Classification ID: 06A06
zbMATH DE Number: 6385338
zbMATH Keywords: Rado graph
zbMATH Keywords: isomorphic copy
zbMATH Keywords: maximal chain
zbMATH Keywords: compact set
author: Miloš S. Kurilić
author: Boriša Kuzeljević
MaRDI profile type: Publication
full work available at URL: s10474-013-0341-9
OpenAlex ID: W2083905094
cites work: The random graph
cites work: Maximal chains in atomic Boolean algebras
cites work: Asymmetric graphs
cites work: Maximal chains in interval algebras
cites work: Maximal chains in positive subfamilies of \(P(\omega )\)
cites work: Maximal chains of copies of the rational line
cites work: Q3949052
cites work: Q5340125
DOI: 10.1007/S10474-013-0341-9
Recommended article: Maximal antichains of isomorphic subgraphs of the Rado graph
Recommended article: Maximal chains of isomorphic subgraphs of countable ultrahomogeneous graphs
Recommended article: Maximal chordal subgraphs
Recommended article: Q4304335
Recommended article: Q3317132
Recommended article: Toward a graph version of Rado's theorem
Recommended article: Maximum subgraphs in Ramsey graphs
Recommended article: Graphs isomorphic to their maximum matching graphs
Recommended article: On Maximal Chain Subgraphs and Covers of Bipartite Graphs
Recommended article: A graphical characterization of the largest chain graphs
description: scientific article; zbMATH DE number 6385338