Definability in the Substructure Ordering of Finite Directed Graphs
We deal with first-order definability in the substructure ordering (D; subset of) of finite directed graphs. In two papers, the author has already investigated the first-order language of the embeddability ordering (D; <=). The latter has turned out to be quite strong, e.g., it has been shown tha...
Elmentve itt :
| Szerző: | |
|---|---|
| Dokumentumtípus: | Cikk |
| Megjelent: |
2021
|
| Sorozat: | ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS
38 No. 3 |
| Tárgyszavak: | |
| doi: | 10.1007/s11083-020-09548-x |
| mtmt: | 32367318 |
| Online Access: | http://publicatio.bibl.u-szeged.hu/37470 |
| Tartalmi kivonat: | We deal with first-order definability in the substructure ordering (D; subset of) of finite directed graphs. In two papers, the author has already investigated the first-order language of the embeddability ordering (D; <=). The latter has turned out to be quite strong, e.g., it has been shown that, modulo edge-reversing (on the whole graphs), it can express the full secondorder language of directed graphs. Now we show that, with finitely many directed graphs added as constants, the first order language of (D; subset of) can express that of (D; <=). The limits of the expressive power of such languages are intimately related to the automorphism groups of the orderings. Previously, analogue investigations have found the concerning automorphism groups to be quite trivial, e.g., the automorphism group of (D; <=) is isomorphic to Z2. Here, unprecedentedly, this is not the case. Even though we conjecture that the automorphism group is isomorphic to (Z(2)(4) x S-4) x(alpha)Z(2), with a particular a in the semidirect product, we only prove it is finite. |
|---|---|
| Terjedelem/Fizikai jellemzők: | 401-420 |
| ISSN: | 0167-8094 |