Finite Vertex-colored Ultrahomogeneous Oriented Graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911987383926784 |
|---|---|
| author | Heinrich, Irene Kaja, Eda Schweitzer, Pascal |
| author_facet | Heinrich, Irene Kaja, Eda Schweitzer, Pascal |
| contents | A relational structure R is ultrahomogeneous if every isomorphism of finite induced substructures of R extends to an automorphism of R. We classify the ultrahomogeneous finite binary relational structures with one asymmetric binary relation and arbitrarily many unary relations. In other words, we classify the finite vertex-colored oriented ultrahomogeneous graphs. The classification comprises several general methods with which directed graphs can be combined or extended to create new ultrahomogeneous graphs. Together with explicitly given exceptions, we obtain exactly all vertex-colored oriented ultrahomogeneous graphs this way. Our main technique is a technical tool that characterizes precisely under which conditions two binary relational structures with disjoint unary relations can be combined to form a larger ultrahomogeneous structure. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_07162 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Finite Vertex-colored Ultrahomogeneous Oriented Graphs Heinrich, Irene Kaja, Eda Schweitzer, Pascal Combinatorics Discrete Mathematics 03C13, 05C20, 05C60, 05C75 A relational structure R is ultrahomogeneous if every isomorphism of finite induced substructures of R extends to an automorphism of R. We classify the ultrahomogeneous finite binary relational structures with one asymmetric binary relation and arbitrarily many unary relations. In other words, we classify the finite vertex-colored oriented ultrahomogeneous graphs. The classification comprises several general methods with which directed graphs can be combined or extended to create new ultrahomogeneous graphs. Together with explicitly given exceptions, we obtain exactly all vertex-colored oriented ultrahomogeneous graphs this way. Our main technique is a technical tool that characterizes precisely under which conditions two binary relational structures with disjoint unary relations can be combined to form a larger ultrahomogeneous structure. |
| title | Finite Vertex-colored Ultrahomogeneous Oriented Graphs |
| topic | Combinatorics Discrete Mathematics 03C13, 05C20, 05C60, 05C75 |
| url | https://arxiv.org/abs/2408.07162 |