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

expectation thresholdsrandom assignment problemthresholds

Mathematics Subject Classification ID

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

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

• 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
• 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?)
• 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

(52)

• Improved bounds for the sunflower lemma
• On the hat guessing number of graphs
• Threshold progressions in covering and packing contexts
• Dirac-type theorems in random hypergraphs
• The threshold bias of the clique-factor game
• Multitrees in random graphs
• Threshold functions for incidence properties in finite vector spaces
• Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting)
• Mld's vs thresholds and flips
• Thresholds and Expectation Thresholds
• Hitting times for Shamir's problem
• Low-density parity-check codes achieve list-decoding capacity
• Sunflowers: from soil to oil
• Coding for Sunflowers
• Combinatorics. Abstracts from the workshop held January 1--7, 2023
• On a problem of M. Talagrand
• A proof of the Kahn–Kalai conjecture
• Hypercontractivity for global functions and sharp thresholds
• Isoperimetric stability in lattices
• Down‐set thresholds
• Thresholds for Latin squares and Steiner triple systems: Bounds within a logarithmic factor
• The Park-Pham theorem with optimal convergence rate
• Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
• Threshold for Steiner triple systems
• Rainbow powers of a Hamilton cycle in G_n,p
• Defective coloring of hypergraphs
• The square of a Hamilton cycle in randomly perturbed graphs
• Rainbow thresholds
• A short proof of Kahn-Kalai conjecture
• Optimal spread for spanning subgraphs of Dirac hypergraphs
• A smoother notion of spread hypergraphs
• Spanning F-cycles in random graphs
• A robust Corrádi-Hajnal theorem
• Searching for (sharp) thresholds in random structures: where are we now?
• Interview with Alan Frieze
• Thresholds, expectation thresholds and cloning
• Complexity theory. Abstracts from the workshop held June 2--7, 2024
• The story of sunflowers
• On certain spanning subgraphs of random graphs
• Embedding theorems for random graphs with specified degrees
• Some results on fractional vs. expectation thresholds
• Giant rainbow trees in sparse random graphs
• New bounds on families without large sunflowers
• Sharp thresholds in inference of planted subgraphs
• The emergence of a giant rainbow component
• Dirac's theorem for linear hypergraphs
• Spanning trees in pseudorandom graphs via sorting networks
• Isoperimetric stability in lattices (extended abstract)
• On a conjecture of Talagrand on selector processes and a consequence on positive empirical processes
• Minimal H-factors and covers
• On rainbow thresholds
• Clique factors in pseudorandom graphs

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)