On the Livingstone-Wagner theorem.

V. B. Mnukhin ; I. J. Siemons

The electronic journal of combinatorics, Tome 11 (2004) no. 1

Résumé

Let $G$ be a permutation group on the set $\Omega$ and let ${\cal S}$ be a collection of subsets of $\Omega,$ all of size $\geq m$ for some integer $m$. For $s\leq m$ let $n_{s}(G,\,{\cal S})$ be the number of $G$-orbits on the subsets of $\Omega$ which have a representative $y\subseteq x$ with $|y|=s$ and $y\subseteq x$ for some $x\in {\cal S}$. We prove that if $s < t$ with $s+t\leq m$ then $n_{s}(G,\,{\cal S})\leq n_{t}(G,\,{\cal S})$. A special case of this theorem is the Livingstone-Wagner Theorem when ${\cal S}=\{\Omega\}$. We show how the result can be applied to estimate orbit numbers for simplicial complexes, sequences, graphs and amalgamation classes. It is also shown how this theorem can be extended to orbit theorems on more general partially ordered sets.

Détail

DOI : 10.37236/1782

Classification : 20B05, 06A07
Mots-clés : permutation groups, numbers of orbits, Livingstone-Wagner theorem, partially ordered sets