On a relation between bipartite biregular cages, block designs and generalized polygons*

Abstract: A $\textit{bipartite biregular}$ $(m,n;g)$-graph $\Gamma$ is a bipartite graph of even girth $g$ having the degree set $\{m,n\}$ and satisfying the additional property that the vertices in the same partite set have the same degree. An $(m,n;g)$-$\textit{bipartite biregular cage}$ is a bipartite biregular $(m,n;g)$-graph of minimum order. In this talk, in parallel with the well-known classical results relating the existence of $k$-regular Moore graphs of even girths $g = 6,8 $ and $12$ to the existence of projective planes, generalized quadrangles, and generalized hexagons, we prove that the existence of an $S(2,k,v)$-Steiner system yields the existence of a bipartite biregular $(k,\frac{v-1}{k-1};6)$-cage, and, vice versa, the existence of a bipartite biregular $(k,n;6)$-cage whose order is equal to one of our lower bounds yields the existence of an $S(2,k,1+n(k-1))$-Steiner system. Moreover, with regard to the special case of Steiner triple systems, we completely solve the problem of determining the orders of $(3,n;6)$-bipartite biregular cages for all integers $ngeq 4$. Considering girths higher than $6$, we relate the existence of generalized polygons (quadrangles, hexagons and octagons) to the existence of $(n+1,n^2+1;8)$-, $(n^2+1,n^3+1;8)$-, $(n,n+2;8)$-, $(n+1,n^3+1;12)$- and $(n+1,n^2+1;16)$-bipartite biregular cages, respectively. Using this connection, we also derive improved upper bounds for the orders of other classes of bipartite biregular cages of girths $8$, $12$ and $14$.

Back to Search Research Symposium Abstracts