Siblings of Binary Relations: The Case of Direct Sums of Chains, NE-Free Posets and Trees

Date
2022-09
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Two structures are called siblings when they mutually embed in each other. This dissertation mainly discusses Thomasse's conjecture and its alternate form for some binary relations. Thomasse's conjecture states that a countable relation has either one, countably many or continuum many siblings, up to isomorphism and the alternate form says that a relation of any cardinality has one or infinitely many siblings, up to isomorphism. There is also a conjecture due to Bonato-Tardif stating that a tree has one or infinitely many siblings in the category of trees. For a tree which is not a sibling of the graph obtained by adding an isolated vertex to the tree, the Bonato-Tardif conjecture and the alternate Thomasse conjecture are equivalent. Abdi, Laflamme, Tateno, Woodrow verified the ideas of a counterexample to the Bonato-Tardif conjecture claimed by Tateno and they confirmed that the example also disproves Thomasse's conjecture. This is a major development in the program of understanding siblings of a given mathematical structure. The counterexample is not a subject of this dissertation, however, determining which structures exactly do satisfy the conjectures is of interest. Laflamme, Pouzet and Woodrow verified both Thomasse's conjecture and its alternate form for chains. Moreover, the alternate Thomasse conjecture was proved for countable cographs by Hahn, Pouzet and Woodrow. In order to tackle the conjectures towards posets, we verify both Thomasse's conjecture and its alternate version for direct sums of chains. We also show that the alternate Thomasse conjecture is true for countable NE-free posets which have strong connections to cographs. Moreover, making use of decomposition trees, we give a proof that each cograph is the comparability graph of some NE-free poset. In order to pose more restriction on trees related to the Bonato-Tardif conjecture, we give a positive answer to one of the open cases of a result due to Hamann. Tyomkyn conjectured that if a locally finite tree has a non-surjective embedding, then it has infinitely many siblings, unless the tree is a one-way infinite path. We prove that if a locally finite tree has a non-surjective embedding preserving precisely one end, then it has infinitely many siblings, unless the tree is a one-way infinite path. This establishes both conjectures of Bonato-Tardif and Tyomkyn for locally finite trees which do not have non-surjective embeddings preserving precisely two ends. Finally, we give a representation of trees obtained by a technique which is similar to the Cantor-Bendixson derivative of a topological space. This representation helps us to verify the Bonato-Tardif conjecture in some cases.
Description
Keywords
binary relations, siblings, partially ordered sets, linearly ordered sets, graphs, trees
Citation
Abdi Kalow, D. (2022). Siblings of binary relations: the case of direct sums of chains, NE-free posets and trees (Doctoral thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca.