Hypergraph Containers and Their Generalization to Super-Hyper-Graph Containers

Abstract

Hypergraphs extend classical graphs by allowing each edge-known as a hyperedge-to join any number of vertices, thereby modeling higher-order relationships. Recently, super-hyper-graphs have been introduced to incorporate recursively nested powerset layers, enabling hierarchical and self-referential connections among hyperedges and vertices. While the theory of hypergraph containers offers powerful tools to cover all independent sets in a hypergraph under controlled edge-density or vertex-measure constraints, existing container techniques do not exploit the multi-layered structure inherent in super-hyper-graphs. In this work, we define the novel concept of a super-hyper-graph container. We begin by extending the classical degree-measure and container definitions to the n-level super-hyper-graph setting. We then develop a general removal-based construction that produces, for any n-super-hyper-graph, a family of containers satisfying both coverage and smallness properties.