Maximizing \(2\)-independents sets in \(3\)-uniform hypergraphs (Q2161206)

Summary: 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.