Independence and Matchings in $σ$-hypergraphs

Yair Caro, Josef Lauri, Christina Zarb

Published 2014-05-01Version 1

Let $\sigma$ be a partition of the positive integer $r$. A $\sigma$-hypergraph $H=H(n,r,q|\sigma)$ is an $r$-uniform hypergraph on $nq$ vertices which are partitioned into $n$ classes $V_1, V_2, \ldots, V_n$ each containing $q$ vertices. An $r$-subset $K$ of vertices is an edge of the hypergraph if the partition of $r$ formed by the non-zero cardinalities $|K\cap V_i|, 1\leq i \leq n,$ is $\sigma$. In earlier works we have considered colourings of the vertices of $H$ which are constrained such that any edge has at least $\alpha$ and at most $\beta$ vertices of the same colour, and we have shown that interesting results can be obtained by varying $\alpha, \beta$ and the parameters of $H$ appropriately. In this paper we continue to investigate the versatility of $\sigma$-hypergraphs by considering two classical problems: independence and matchings. We first demonstrate an interesting link between the constrained colourings described above and the $k$-independence number of a hypergraph, that is, the largest cardinality of a subset of vertices of a hypergraph not containing $k+1$ vertices in the same edge. We also give an exact computation of the $k$-independence number of the $\sigma$-hypergraph $H$. We then present results on maximum, and sometimes perfect, matchings in $H$. These results often depend on divisibility relations between the parameters of $H$ and on the highest common factor of the parts of $\sigma$.