Maximizing $2$-Independents Sets in $3$-Uniform Hypergraphs

Abstract

In this paper we solve three equivalent problems. The first is: what $3$-uniform hypergraph on a ground set of size $n$, having at least $e$ 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 the $3$-uniform hypergraph for which the size of $\partial^+(\partial_2(\mathcal{H}))$ is minimized. Here $\partial_2({\cdot})$ is the down-shadow on level $2$, and $\partial^+({\cdot})$ denotes the up-shadow on all levels. This in turn is equivalent to the problem of determining which graph on $n$ vertices having at least $e$ triangles has the most independent sets. The (hypergraph) answer is that, ignoring some transient and some persistent exceptions which we can classify completely, a $(2,3,1)$-lex style $3$-graph is optimal.

We also discuss the general 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.