{
  "id": "1802.01825",
  "version": "v1",
  "published": "2018-02-06T07:14:50.000Z",
  "updated": "2018-02-06T07:14:50.000Z",
  "title": "Transversals in Uniform Linear Hypergraphs",
  "authors": [
    "Michael A. Henning",
    "Anders Yeo"
  ],
  "comment": "105 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "The transversal number $\\tau(H)$ of a hypergraph $H$ is the minimum number of vertices that intersect every edge of $H$. A linear hypergraph is one in which every two distinct edges intersect in at most one vertex. A $k$-uniform hypergraph has all edges of size $k$. It is known that $\\tau(H) \\le (n + m)/(k+1)$ holds for all $k$-uniform, linear hypergraphs $H$ when $k \\in \\{2,3\\}$ or when $k \\ge 4$ and the maximum degree of $H$ is at most two. It has been conjectured that $\\tau(H) \\le (n+m)/(k+1)$ holds for all $k$-uniform, linear hypergraphs $H$. We disprove the conjecture for large $k$, and show that the best possible constant $c_k$ in the bound $\\tau(H) \\le c_k (n+m)$ has order $\\ln(k)/k$ for both linear (which we show in this paper) and non-linear hypergraphs. We show that for those $k$ where the conjecture holds, it is tight for a large number of densities if there exists an affine plane $AG(2,k)$ of order $k \\ge 2$. We raise the problem to find the smallest value, $k_{\\min}$, of $k$ for which the conjecture fails. We prove a general result, which when applied to a projective plane of order $331$ shows that $k_{\\min} \\le 166$. Even though the conjecture fails for large $k$, our main result is that it still holds for $k=4$, implying that $k_{\\min} \\ge 5$. The case $k=4$ is much more difficult than the cases $k \\in \\{2,3\\}$, as the conjecture does not hold for general (non-linear) hypergraphs when $k=4$. Key to our proof is the completely new technique of the deficiency of a hypergraph introduced in this paper.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-02-06T07:14:50.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C65",
      "51E15"
    ],
    "keywords": [
      "uniform linear hypergraphs",
      "transversal",
      "conjecture fails",
      "distinct edges intersect",
      "uniform hypergraph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 105,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}