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

Lauren Keough¹ ; Jamie Radcliffe²

¹Grand Valley State University
²University of Nebraska-Lincoln

The electronic journal of combinatorics, Tome 29 (2022) no. 3

Résumé

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.

Détail

DOI : 10.37236/9365

Classification : 05C35, 05C65, 05C69, 05D05
Mots-clés : \(2\)-independent set, \(3\)-uniform hypergraph