The authors verify Talagrand's threshold conjecture for the family of ℓ-uniform hypergraph cliques, with a uniform constant L = 2^12 e^16 for large ground sets.
A sharp version of Talagrand's selector process conjecture and an application to rounding fractional covers
1 Pith paper cite this work. Polarity classification is still indexing.
abstract
Expectation thresholds arise from a class of integer linear programs (LPs) that are fundamental to the study of thresholds in large random systems. An avenue towards estimating expectation thresholds comes from the fractional relaxation of these integer LPs, which yield the fractional expectation thresholds. Regarding the gap between the integer LPs and their fractional relaxations, Talagrand made a bold conjecture, that the integral and fractional expectation thresholds are within a constant factor of each other. In other words, any small fractional solution can be ``rounded''. In this paper, we prove a strong upper bound on the expectation threshold starting from a fractional solution supported on sets with small size. In particular, this resolves Talagrand's conjecture for fractional solutions supported on sets with bounded size. Our key input for rounding the fractional solutions is a sharp version of Talagrand's selector process conjecture that is of independent interest.
citation-role summary
citation-polarity summary
fields
math.CO 1years
2025 1verdicts
CONDITIONAL 1roles
background 1polarities
unclear 1representative citing papers
citing papers explorer
-
Further remarks on fractional vs. expectation thresholds
The authors verify Talagrand's threshold conjecture for the family of ℓ-uniform hypergraph cliques, with a uniform constant L = 2^12 e^16 for large ground sets.