Well quasi-order and atomicity for combinatorial structures under consecutive orders
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914615046176768 |
|---|---|
| author | Ironmonger, Victoria Ruškuc, Nik |
| author_facet | Ironmonger, Victoria Ruškuc, Nik |
| contents | We consider partially ordered sets of combinatorial structures under consecutive orders, meaning that two structures are related when one embeds in the other such that `consecutive' elements remain consecutive in the image. Given such a partially ordered set, we may ask decidability questions about its avoidance sets: subsets defined by a finite number of forbidden substructures. Two such questions ask, given a finite set of structures, whether its avoidance set is well quasi-ordered (i.e. contains no infinite antichains) or atomic (i.e. cannot be expressed as the union of two proper subsets). Extending some recent new approaches, we will establish a general framework, which enables us to answer these problems for a wide class of combinatorial structures, including graphs, digraphs and collections of relations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_01852 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Well quasi-order and atomicity for combinatorial structures under consecutive orders Ironmonger, Victoria Ruškuc, Nik Combinatorics 06A07, 05C20, 05C38, 03C13 We consider partially ordered sets of combinatorial structures under consecutive orders, meaning that two structures are related when one embeds in the other such that `consecutive' elements remain consecutive in the image. Given such a partially ordered set, we may ask decidability questions about its avoidance sets: subsets defined by a finite number of forbidden substructures. Two such questions ask, given a finite set of structures, whether its avoidance set is well quasi-ordered (i.e. contains no infinite antichains) or atomic (i.e. cannot be expressed as the union of two proper subsets). Extending some recent new approaches, we will establish a general framework, which enables us to answer these problems for a wide class of combinatorial structures, including graphs, digraphs and collections of relations. |
| title | Well quasi-order and atomicity for combinatorial structures under consecutive orders |
| topic | Combinatorics 06A07, 05C20, 05C38, 03C13 |
| url | https://arxiv.org/abs/2510.01852 |