Finitely Constrained Classes of Homogeneous Directed Graphs
Latka, Brenda J.
J. Symbolic Logic, Tome 59 (1994) no. 1, p. 124-139 / Harvested from Project Euclid
Given a finite relational language $L$ is there an algorithm that, given two finite sets $\mathscr{A}$ and $\mathscr{B}$ of structures in the language, determines how many homogeneous $L$ structures there are omitting every structure in $\mathscr{B}$ and embedding every structure in $\mathscr{A}$? For directed graphs this question reduces to: Is there an algorithm that, given a finite set of tournaments $\Gamma$, determines whether $\mathscr{Q}_\Gamma$, the class of finite tournaments omitting every tournament in $\Gamma$, is well-quasi-order? First, we give a nonconstructive proof of the existence of an algorithm for the case in which $\Gamma$ 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 $\Gamma$ consists of two tournaments is also discussed.
Publié le : 1994-03-14
Classification: 
@article{1183744439,
     author = {Latka, Brenda J.},
     title = {Finitely Constrained Classes of Homogeneous Directed Graphs},
     journal = {J. Symbolic Logic},
     volume = {59},
     number = {1},
     year = {1994},
     pages = { 124-139},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183744439}
}
Latka, Brenda J. Finitely Constrained Classes of Homogeneous Directed Graphs. J. Symbolic Logic, Tome 59 (1994) no. 1, pp.  124-139. http://gdmltest.u-ga.fr/item/1183744439/