Independence and matchings in σ-hypergraphs

Abstract

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 V1, V2, . . . , Vn 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 ∩ Vi |, 1 ≤ i ≤ 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 σ.