{
  "id": "1903.08232",
  "version": "v1",
  "published": "2019-03-19T19:39:39.000Z",
  "updated": "2019-03-19T19:39:39.000Z",
  "title": "Maximizing 2-Independent Sets in 3-Uniform Hypergraphs",
  "authors": [
    "Lauren Keough",
    "A. J. Radcliffe"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "There has been interest recently in maximizing the number of independent sets in graphs. For example, the Kahn-Zhao theorem gives an upper bound on the number of independent sets in a $d$-regular graph. Similarly, it is a corollary of the Kruskal-Katona theorem that the lex graph has the maximum number of independent sets in a graph of fixed size and order. In this paper we solve two equivalent problems. The first is: what $3$-uniform hypergraph on a ground set of size $n$, having at least $t$ edges, has the most $2$-independent sets? Here a $2$--independent set is a subset of vertices containing fewer than $2$ vertices from each edge. This is equivalent to the problem of determining which graph on $n$ vertices having at least $t$ triangles has the most independent sets. The (hypergraph) answer is that, ignoring some transient and some persistent exceptions, a $(2,3,1)$-lex style $3$-graph is optimal. We also discuss the problem of maximizing the number of $s$-independent sets in $r$-uniform hypergraphs of fixed size and order, proving some simple results, and conjecture an asymptotically correct general solution to the problem.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-03-19T19:39:39.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C35",
      "05C65",
      "05C69"
    ],
    "keywords": [
      "independent set",
      "maximizing",
      "uniform hypergraph",
      "asymptotically correct general solution",
      "regular graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}