Finitely constrained classes of homogeneous directed graphs
- 12 March 1994
- journal article
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 59 (1) , 124-139
- https://doi.org/10.2307/2275255
Abstract
Given a finite relational language L is there an algorithm that, given two finite sets and of structures in the language, determines how many homogeneous L structures there are omitting every structure in and embedding every structure in ?For directed graphs this question reduces to: Is there an algorithm that, given a finite set of tournaments Γ, determines whether Γ, the class of finite tournaments omitting every tournament in Γ. is well-quasi-order?First, we give a nonconstructive proof of the existence of an algorithm for the case in which Γ consists of one tournament. Then we determine explicitly the set of tournaments each of which does not have an antichain omitting it. Two antichains are exhibited and a summary is given of two structure theorems which allow the application of Kruskal's Tree Theorem. Detailed proofs of these structure theorems will be given elsewhere.The case in which Γ consists of two tournaments is also discussed.Keywords
This publication has 7 references indexed in Scilit:
- Homogeneous tournaments revisitedGeometriae Dedicata, 1988
- On countable stable structures which are homogeneous for a finite relational languageIsrael Journal of Mathematics, 1984
- Countable homogeneous tournamentsTransactions of the American Mathematical Society, 1984
- Orbits of Permutation Groups on Unordered SetsJournal of the London Mathematical Society, 1978
- On well-quasi-ordering finite treesMathematical Proceedings of the Cambridge Philosophical Society, 1963
- Well-quasi-ordering, the Tree Theorem, and Vazsonyi’s conjectureTransactions of the American Mathematical Society, 1960
- Ordering by Divisibility in Abstract AlgebrasProceedings of the London Mathematical Society, 1952