Open AccessMaximal antichains of isomorphic subgraphs of the Rado graph
Author(s) -
Miloš S. Kurilić,
Petar Marković
Publication year - 2015
Publication title -
filomat
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.449
H-Index - 34
eISSN - 2406-0933
pISSN - 0354-5180
DOI - 10.2298/fil1509919k
Subject(s) - antichain , mathematics , combinatorics , partially ordered set , graph , order (exchange) , integer (computer science) , discrete mathematics , computer science , finance , economics , programming language
If ?R,E? is the Rado graph andR(R) the set of its copies inside R, then ?R(R), ?? is a chain-complete and non-atomic partial order of the size 2x0 . A family A ? R(R) is a maximal antichain in this partial order iff (1) A ? B does not contain a copy of R, for each different A, B ?A and (2) For each S ? R(R) there is A ? A such that A ? S contains a copy of R. We show that the partial order ?R(R), ?? contains maximal antichains of size 2x0, X0 and n, for each positive integer n (thus, of all possible cardinalities, under CH). The results are compared with the corresponding known results concerning the partial order ?[?]?, ??.