Thresholds and Expectation Thresholds
From MaRDI portal
Abstract: Consider a random graph G in G(n,p) and the graph property: G contains a copy of a specific graph H. (Note: H depends on n; a motivating example: H is a Hamiltonian cycle.) Let q be the minimal value for which the expected number of copies of H' in G is at least 1/2 for every subgraph H' of H. Let p be the value for which the probability that G contains a copy of H is 1/2. Conjecture: p/q = O(log n). Related conjectures for general Boolean functions, and a possible connection with discrete isoperimetry are discussed.
Recommendations
Cited in
(53)- On Russo's approximate zero-one law
- Boolean functions: influence, threshold and noise
- Around two theorems and a lemma by Lucio Russo
- A stability result for the cube edge isoperimetric inequality
- On a biased edge isoperimetric inequality for the discrete cube
- Thresholds versus fractional expectation-thresholds
- Concentration on the Boolean hypercube via pathwise stochastic analysis
- The junta method for hypergraphs and the Erdős-Chvátal simplex conjecture
- Stability versions of Erdős-Ko-Rado type theorems via isoperimetry
- Spanning trees in random graphs
- Juntas in the \(\ell_{1}\)-grid and Lipschitz maps between discrete tori
- Spanning structures and universality in sparse hypergraphs
- Almost isoperimetric subsets of the discrete cube
- On spanning structures in random hypergraphs
- Mld's vs thresholds and flips
- Note on a problem of M. Talagrand
- Variable Influences in Conjunctive Normal Forms
- On the structure of subsets of the discrete cube with small edge boundary
- Thresholds and expectation-thresholds of monotone properties with small minterms
- The threshold for the square of a Hamilton cycle
- Hitting times for Shamir's problem
- Sunflowers: from soil to oil
- Biased halfspaces, noise sensitivity, and local Chernoff inequalities
- On the union of intersecting families
- On Erdős-Ko-Rado for random hypergraphs. I
- Optimal threshold for a random graph to be 2-universal
- Arbitrary Threshold Widths for Monotone, Symmetric Properties
- The threshold for combs in random graphs
- 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
- 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 Gn,p
- A simple proof of the nonuniform Kahn-Kalai conjecture
- A short proof of Kahn-Kalai conjecture
- Optimal spread for spanning subgraphs of Dirac hypergraphs
- Spanning F-cycles in random graphs
- Searching for (sharp) thresholds in random structures: where are we now?
- 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
- Counting stars is constant-degree optimal for detecting any planted subgraph
- Some results on fractional vs. expectation thresholds
- When do the Kahn-Kalai bounds provide nontrivial information?
- Sharp thresholds in inference of planted subgraphs
- Isoperimetric stability in lattices (extended abstract)
- Towards an optimal contention resolution scheme for matchings
- On rainbow thresholds
This page was built for publication: Thresholds and Expectation Thresholds
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3438145)
