Independence and Matchings in $σ$-hypergraphs

Let $σ$ be a partition of the positive integer $r$. A $σ$-hypergraph $H=H(n,r,q|σ)$ 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 $σ$. In earlier works we have considered colourings of the vertices of $H$ which are constrained such that any edge has at least $α$ and at most $β$ vertices of the same colour, and we have shown that interesting results can be obtained by varying $α, β$ and the parameters of $H$ appropriately. In this paper we continue to investigate the versatility of $σ$-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 $σ$-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 $σ$.

No reviews yet.

No comments yet.