On Cages and Choosing with Symmetries

Abstract

Given a set $S$, an integer $k$ and a permutation group $G$ acting on $S$, we provide a novel algorithm for computing ${S \choose k}_{G}$, which is the set of all $k$-subsets of $S$ up to symmetries in $G$. Then we apply our algorithm to compute $(d,g)$-cages which are $d$-regular graphs of girth $g$ and minimum order $n=n(d,g)$. Our algorithm allowed us to reproduce most of the computational results on cages and to improve six lower bounds for the order of cages, namely: $n(3,14)\geq 262$, $n(3,15)\geq 388$, $n(3,17)\geq 770$, $n(4,9)\geq 165$, $n(5,7)\geq 110$ and $n(8,5) \geq 69$.