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.
Introduction
In extremal combinatorics, a fundamental question involves finding the structure of a graph or hypergraph that maximizes a specific property under fixed constraints. A classic version of this problem asks: given $n$ vertices and $e$ edges, which graph contains the maximum number of independent sets? This paper, published in The Electronic Journal of Combinatorics, extends this inquiry to 3-uniform hypergraphs—where every edge consists of exactly three vertices—and focuses on "2-independent sets."
A 2-independent set is a subset of vertices that contains at most one vertex from any given edge in the hypergraph. The authors demonstrate that this problem is mathematically equivalent to finding the graph with $n$ vertices and $e$ triangles that maximizes the number of standard independent sets. This "triangle-constrained" problem has long been a subject of interest in extremal graph theory.
Methodology and Visualization
The authors employ several sophisticated combinatorial techniques to characterize the optimal hypergraph structures:
- Shifting: This standard tool in extremal set theory allows researchers to assume the optimal hypergraph has a "compressed" or "nested" structure, significantly reducing the search space.
- Downsets and Grid Visualization: Shifted 3-graphs are represented as "downsets" in a 2D grid. This transformation converts a complex set-theoretic problem into a geometric optimization problem on a grid, where edges are mapped to specific coordinates.
- Cost Analysis: The researchers derived a formula for the "cost" of an edge, defined as the number of 2-independent sets lost when a new edge is added. This cost is shown to be exponential ($2^{n-k-1}$), enabling rigorous comparisons between different structural configurations.
- Local Moves: The core proof involves algorithmic "local moves," where cells in the grid representation are swapped to demonstrate that non-lex-style structures are sub-optimal.
Key Insights: The (2, 3, 1)-lex Style
The most significant finding is the identification of the (2, 3, 1)-lex style as the optimal structure. Unlike simple lexicographical (dictionary) or colexicographical orders, this specific permutation-based ordering prioritizes edges such that their "second greatest element" is kept as small as possible.
The difficulty of this problem stems from conflicting constraints. Maximizing independent sets requires balancing two opposing forces: structuring the "lower shadow" (the pairs contained within triples) to resemble one type of graph while ensuring the "upper shadow" (the triples themselves) resembles another.
Furthermore, the authors identified a "phase transition" at $n=33$. For smaller values of $n$, the optimal structures exhibit somewhat chaotic behavior, termed "transient exceptions." However, once $n \ge 33$, the behavior stabilizes into a predictable, persistent pattern.
Key Results and Classification
- Main Theorem: For $n \ge 33$, the maximum number of 2-independent sets is achieved by a (2, 3, 1)-lex style hypergraph, with only five specific "persistent" exceptions involving specific configurations like $K_4$ or $K_5$ cliques.
- Graph Equivalence: The paper proves that to maximize independent sets in a graph with a fixed number of triangles, one should almost always utilize a "lex graph" where edges are added in dictionary order.
- Complete Classification: The authors provide a complete list of the 16 exceptions for $n < 33$, filling the gap where the general theorem does not apply through computational verification.
Future Directions
While this work provides a definitive solution for 3-uniform hypergraphs and 2-independent sets ($r=3, s=2$), the general case for $r$-uniform hypergraphs and $s$-independent sets remains open. The authors propose Conjecture 57, suggesting that a specific $(r-s+1, \dots, r, 1, \dots, s)$-lex order is asymptotically optimal for the general case. Proving this for all $r$ and $s$ remains a significant challenge in the field, as current results for higher dimensions are primarily limited to asymptotic estimates rather than exact solutions.
Summary updated