Induced betweenness in order-theoretic trees
The ternary relation B(x,y,z) of betweenness states that an element y is between the elements x and z, in some sense depending on the considered structure. In a partially ordered set (N,≤), B(x,y,z):⇔x<y<z∨z<y<x, and the corresponding betweenness structure is (N,B). The class of betweenn...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2022-09-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/7288/pdf |
| _version_ | 1797270011626127360 |
|---|---|
| author | Bruno Courcelle |
| author_facet | Bruno Courcelle |
| author_sort | Bruno Courcelle |
| collection | DOAJ |
| description | The ternary relation B(x,y,z) of betweenness states that an element y is between the elements x and z, in some sense depending on the considered structure. In a partially ordered set (N,≤), B(x,y,z):⇔x<y<z∨z<y<x, and the corresponding betweenness structure is (N,B). The class of betweenness structures of linear orders is first-order definable. That of partial orders is monadic second-order definable. An order-theoretic tree is a partial order such that the set of elements larger that any element is linearly ordered and any two elements have an upper-bound. Finite or infinite rooted trees ordered by the ancestor relation are order-theoretic trees. In an order-theoretic tree, B(x,y,z) means that x<y<z or z<y<x or x<y≤x⊔z or z<y≤x⊔z, where x⊔z is the least upper-bound of incomparable elements x and z. In a previous article, we established that the corresponding class of betweenness structures is monadic second-order definable.We prove here that the induced substructures of the betweenness structures of the countable order-theoretic trees form a monadic second-order definable class, denoted by IBO. The proof uses a variant of cographs, the partitioned probe cographs, and their known six finite minimal excluded induced subgraphs called the bounds of the class. This proof links two apparently unrelated topics: cographs and order-theoretic trees.However, the class IBO has finitely many bounds, i.e., minimal excluded finite induced substructures. Hence it is first-order definable. The proof of finiteness uses well-quasi-orders and does not provide the finite list of bounds. Hence, the associated first-order defining sentence is not known. |
| first_indexed | 2024-03-11T21:31:52Z |
| format | Article |
| id | doaj.art-7d85493aec46492c9b2ae1b0e9ca647e |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:57:29Z |
| publishDate | 2022-09-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-7d85493aec46492c9b2ae1b0e9ca647e2024-03-07T15:44:44ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502022-09-01vol. 23 no. 2, special issue...Special issues10.46298/dmtcs.72887288Induced betweenness in order-theoretic treesBruno Courcelle0https://orcid.org/0000-0002-5545-8970Laboratoire Bordelais de Recherche en InformatiqueThe ternary relation B(x,y,z) of betweenness states that an element y is between the elements x and z, in some sense depending on the considered structure. In a partially ordered set (N,≤), B(x,y,z):⇔x<y<z∨z<y<x, and the corresponding betweenness structure is (N,B). The class of betweenness structures of linear orders is first-order definable. That of partial orders is monadic second-order definable. An order-theoretic tree is a partial order such that the set of elements larger that any element is linearly ordered and any two elements have an upper-bound. Finite or infinite rooted trees ordered by the ancestor relation are order-theoretic trees. In an order-theoretic tree, B(x,y,z) means that x<y<z or z<y<x or x<y≤x⊔z or z<y≤x⊔z, where x⊔z is the least upper-bound of incomparable elements x and z. In a previous article, we established that the corresponding class of betweenness structures is monadic second-order definable.We prove here that the induced substructures of the betweenness structures of the countable order-theoretic trees form a monadic second-order definable class, denoted by IBO. The proof uses a variant of cographs, the partitioned probe cographs, and their known six finite minimal excluded induced subgraphs called the bounds of the class. This proof links two apparently unrelated topics: cographs and order-theoretic trees.However, the class IBO has finitely many bounds, i.e., minimal excluded finite induced substructures. Hence it is first-order definable. The proof of finiteness uses well-quasi-orders and does not provide the finite list of bounds. Hence, the associated first-order defining sentence is not known.https://dmtcs.episciences.org/7288/pdf[info.info-lo]computer science [cs]/logic in computer science [cs.lo] |
| spellingShingle | Bruno Courcelle Induced betweenness in order-theoretic trees Discrete Mathematics & Theoretical Computer Science [info.info-lo]computer science [cs]/logic in computer science [cs.lo] |
| title | Induced betweenness in order-theoretic trees |
| title_full | Induced betweenness in order-theoretic trees |
| title_fullStr | Induced betweenness in order-theoretic trees |
| title_full_unstemmed | Induced betweenness in order-theoretic trees |
| title_short | Induced betweenness in order-theoretic trees |
| title_sort | induced betweenness in order theoretic trees |
| topic | [info.info-lo]computer science [cs]/logic in computer science [cs.lo] |
| url | https://dmtcs.episciences.org/7288/pdf |
| work_keys_str_mv | AT brunocourcelle inducedbetweennessinordertheoretictrees |