A reformulation of the discrete Convexity Conjecture via $k$-thresholds

Abstract

We introduce the notion of "$k$-thresholds'' and show that Talagrand's discrete convexity conjecture is equivalent to the assertion that, for some universal integer $k \ge 2$, the $k$-threshold of every increasing family is at most a universal constant times its expectation threshold. We prove a reduction theorem that bounds the $k$-threshold of any increasing graph property in terms of ordinary thresholds of graphs in suitable decompositions of its members. As a consequence, we determine, up to a constant factor, the $k$-threshold of every fixed graph in terms of a natural $k$-density parameter. We also prove that $k=2$ suffices for several classical spanning graph containment properties. More generally, we establish the conjectured comparison between $k$-thresholds and expectation thresholds for broad classes of graph containment properties whose target graphs have low degeneracy.

Disclosure

“this work was carried out while the third and fourth authors visited the KIAS-KAIST Workshop on Current Challenges in Mathematics, and the authors gratefully acknowledge KIAS and KAIST for their support and hospitality. The authors used generative AI to assist with editing this manuscript. All original mathematical ideas and final language are our own. JP was supported by NSF Grant DMS-2324978, NSF CAREER Grant DMS-2443706 and a Sloan Fellow- ship.”

PDF page 21

Classification

Proofreading, grammar, or spelling

Multiplier

1

Verified

2026-08-23T05:10:13.913643Z

Structural counts