{
  "id": "2208.11573",
  "version": "v1",
  "published": "2022-08-24T14:28:59.000Z",
  "updated": "2022-08-24T14:28:59.000Z",
  "title": "An asymptotic resolution of a conjecture of Szemerédi and Petruska",
  "authors": [
    "André E. Kézdy",
    "Jenő Lehel"
  ],
  "comment": "23 pages, no figures. Completes project begun in \"On a conjecture of Szemer\\'edi and Petruska\", arXiv:1904.04921v2",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "Consider a $3$-uniform hypergraph of order $n$ with clique number $k$ such that the intersection of all its $k$-cliques is empty. Szemer\\'edi and Petruska proved $n\\leq 8m^2+3m$, for fixed $m=n-k$, and they conjectured the sharp bound $n \\leq {m+2 \\choose 2}$. This problem is known to be equivalent to determining the maximum order of a $\\tau$-critical $3$-uniform hypergraph with transversal number $m$ (details may also be found in a companion paper: arXiv:2204.02859). The best known bound, $n\\leq \\frac{3}{4}m^2+m+1$, was obtained by Tuza using the machinery of $\\tau$-critical hypergraphs. Here we propose an alternative approach, a combination of the iterative decomposition process introduced by Szemer\\'edi and Petruska with the skew version of Bollob\\'as's theorem on set pair systems. The new approach improves the bound to $n\\leq {m+2 \\choose 2} + O(m^{{5}/{3}})$, resolving the conjecture asymptotically.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-08-24T14:28:59.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05D05",
      "05C65"
    ],
    "keywords": [
      "asymptotic resolution",
      "conjecture",
      "uniform hypergraph",
      "set pair systems",
      "clique number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 23,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}