REVIEW 3 cited by
Towards an optimal hypergraph container lemma
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Towards an optimal hypergraph container lemma
read the original abstract
The hypergraph container lemma is a powerful tool in probabilistic combinatorics that has found many applications since it was first proved a decade ago. Roughly speaking, it asserts that the family of independent sets of every uniform hypergraph can be covered by a small number of almost-independent sets, called containers. In this article, we formulate and prove two new versions of the lemma that display the following three attractive features. First, they both admit short and simple proofs that have surprising connections to other well-studied topics in probabilistic combinatorics. Second, they use alternative notions of almost-independence in order to describe the containers. Third, they yield improved dependence of the number of containers on the uniformity of the hypergraph, hitting a natural barrier for second-moment-type approaches.
Forward citations
Cited by 3 Pith papers
-
A Hypergraph Container Method for Spread SAT: Approximation and Speedup
SAT formulas with (λ,p)_k-structures admit sub-exponential Gap-SAT algorithms whose speedup is controlled by the spread parameter λ, via hypergraph containers.
-
A Hypergraph Container Method for Spread SAT: Approximation and Speedup
For SAT formulas with clause sets that are well spread, a weighted hypergraph-container method yields sub-exponential-time approximate satisfiability and exact speedups that depend directly on the spread parameter.
-
Counting independent sets in percolated graphs via the Ising model
An asymptotic expansion is derived for the expected number of independent sets in percolated regular bipartite graphs via the Ising model and cluster expansion, extending prior hypercube work.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.