{
  "id": "1405.0107",
  "version": "v1",
  "published": "2014-05-01T06:45:05.000Z",
  "updated": "2014-05-01T06:45:05.000Z",
  "title": "Independence and Matchings in $σ$-hypergraphs",
  "authors": [
    "Yair Caro",
    "Josef Lauri",
    "Christina Zarb"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "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$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-05-01T06:45:05.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C65"
    ],
    "keywords": [
      "independence number",
      "highest common factor",
      "colourings",
      "uniform hypergraph",
      "first demonstrate"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1405.0107C"
    }
  }
}