On k-homogeneous posets and graphs (Q2276986)

A relational structure \({\mathcal A}\) is called k-homogeneous if each isomorphism between two k-element substructures of \({\mathcal A}\) extends to an automorphism of \({\mathcal A}\). In this paper the authors show that if a countable poset (Q,\(\leq)\) is 1- and 4-homogeneous, then it is k- homogeneous for each \(k\in {\mathbb{N}}\). There are infinitely many examples of \(\aleph_ 0\)-categorical universal countable posets (Q,\(\leq)\) showing that here the number 4 may not be replaced by 2 or 3. Also, the authors show that for every \(k\in {\mathbb{N}}\) there are continuously many countable \(\aleph_ 0\)-categorical universal graphs which are k-homogeneous but not \((k+1)\)-homogeneous; this answers a question of R. Fraïssé. Finally the paper contains some open problems.