Thresholds versus fractional expectation-thresholds

DOI10.4007/ANNALS.2021.194.2.2MaRDI QIDQ1983096zbMATH OpenOpenAlexFDO

Authors Keith Frankston, Jinyoung Park, J. Kahn, Bhargav P. Narayanan

Publication date 15 September 2021

Published in Annals of Mathematics. Second Series (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1910.13433

zbMATH Keywords

thresholdsrandom assignment problemexpectation thresholds

Mathematics Subject Classification ID

Gaussian processes (60G15) Random graphs (graph-theoretic aspects) (05C80) Geometric probability and stochastic geometry (60D05)

Abstract: Proving a conjecture of Talagrand, a fractional version of the 'expectation-threshold' conjecture of Kalai and the second author, we show for any increasing family $F$ on a finite set $X$ that $p_c(F)=O(q_f(F)logell(F))$, where $p_c(F)$ and $q_f(F)$ are the threshold and 'fractional expectation-threshold' of $F$, and $ell(F)$ is the largest size of a minimal member of $F$. This easily implies several heretofore difficult results and conjectures in probabilistic combinatorics, including thresholds for perfect hypergraph matchings (Johansson--Kahn--Vu), bounded-degree spanning trees (Montgomery), and bounded-degree spanning graphs (new). We also resolve (and vastly extend) the 'axial' version of the random multi-dimensional assignment problem (earlier considered by Martin--M'{e}zard--Rivoire and Frieze--Sorkin). Our approach builds on a recent breakthrough of Alweiss, Lovett, Wu and Zhang on the ErdH{o}s--Rado 'Sunflower Conjecture'.

Recommendations

• Thresholds and Expectation Thresholds
• A proof of the Kahn–Kalai conjecture
• Thresholds and expectation-thresholds of monotone properties with small minterms
• scientific article; zbMATH DE number 949656
• Down‐set thresholds

Cites work

• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 775039 (Why is no real title available?)
• A course in combinatorics.
• An upper bound on the number of Steiner triple systems
• Are many small sets explicitly small?
• Coding for Sunflowers
• Counting designs
• Efficient algorithms for three‐dimensional axial and planar random assignment problems
• Embedding large graphs into a random graph
• Embedding spanning trees in random graphs
• Factors in random graphs
• Hunting for sharp thresholds
• Improved bounds for the sunflower lemma
• Intersection Theorems for Systems of Sets
• Nonisomorphic Steiner triple systems
• Optimal divisibility conditions for loose Hamilton cycles in random hypergraphs
• Optimal threshold for a random graph to be 2-universal
• Random graphs.
• Reducibility among combinatorial problems
• Selector processes on classes of sets
• Sharp thresholds of graph properties, and the $k$-sat problem
• Spanning subgraphs of random graphs
• Spanning trees in random graphs
• The Generic Chaining
• Threshold functions
• Thresholds and Expectation Thresholds
• Upper and lower bounds for stochastic processes. Modern methods and classical problems

Cited in

(37)

• Complexity theory. Abstracts from the workshop held June 2--7, 2024
• Thresholds, expectation thresholds and cloning
• The Park-Pham theorem with optimal convergence rate
• Improved bounds for the sunflower lemma
• Thresholds for Latin squares and Steiner triple systems: Bounds within a logarithmic factor
• Threshold progressions in covering and packing contexts
• Isoperimetric stability in lattices
• Combinatorics. Abstracts from the workshop held January 1--7, 2023
• Coding for Sunflowers
• The square of a Hamilton cycle in randomly perturbed graphs
• The threshold bias of the clique-factor game
• Searching for (sharp) thresholds in random structures: where are we now?
• Defective coloring of hypergraphs
• Rainbow thresholds
• A short proof of Kahn-Kalai conjecture
• Hitting times for Shamir's problem
• Multitrees in random graphs
• Optimal spread for spanning subgraphs of Dirac hypergraphs
• A proof of the Kahn–Kalai conjecture
• A smoother notion of spread hypergraphs
• Spanning \(F\)-cycles in random graphs
• A robust Corrádi-Hajnal theorem
• Low-density parity-check codes achieve list-decoding capacity
• Rainbow powers of a Hamilton cycle in G_n,p
• Thresholds and Expectation Thresholds
• On the hat guessing number of graphs
• Hypercontractivity for global functions and sharp thresholds
• Mld's vs thresholds and flips
• Down‐set thresholds
• Threshold functions for incidence properties in finite vector spaces
• Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
• Dirac-type theorems in random hypergraphs
• Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting)
• Interview with Alan Frieze
• Sunflowers: from soil to oil
• Threshold for Steiner triple systems
• On a problem of M. Talagrand

This page was built for publication: Thresholds versus fractional expectation-thresholds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1983096)