On a problem of Spencer
From MaRDI portal
Let \(X_ 1,...,X_ n\) be events in a probability space. Let \(\rho_ i\) be the probability that \(X_ i\) occurs. Let \(\rho\) be the probability that none of the \(X_ i\) occur. Let G be a graph on [n] so that for \(1\leq i\leq n\) \(X_ i\) is independent of \(\{X_ j| (i,j)\not\in G\}\). Let f(d) be the sup of those x such that if \(\rho_ 1,...,\rho_ n\leq x\) and G has maximum degree \(\leq d\) then \(\rho >0\). We show \(f(1)=1/2\), \(f(d)=(d-1)^{d-1}d^{-d}\) for \(d\geq 2\). Hence \(\lim_{d\to \infty}df(d)=1/e\). This answers a question posed by \textit{J. Spencer} in Discrete Math. 20(1977), 69-76 (1978; Zbl 0375.05033). We also find a sharp bound for \(\rho\) in terms of the \(\rho_ i\) and G.
Recommendations
Cites work
Cited in
(65)- On codes with the identifiable parent property
- Domination by product measures
- Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
- The Ising partition function: zeros and deterministic approximation
- The harmonic mean formula for probabilities of unions: Applications to sparse random graphs
- Entropy compression versus Lovász local lemma
- Comparison of two convergence criteria for the variable-assignment lopsided Lovász local lemma
- Implementations and the independent set polynomial below the Shearer threshold
- Algorithmic Pirogov-Sinai theory
- Cayley trees do not determine the maximal zero-free locus of the independence polynomial
- Sufficient conditions for uniform bounds in abstract polymer systems and explorative partition schemes
- Covering systems with restricted divisibility
- On a conjecture of Sokal concerning roots of the independence polynomial
- Directed Lovász local lemma and Shearer's lemma
- The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
- Moser-Tardos resampling algorithm, entropy compression method and the subset gas
- SIR epidemics on a scale-free spatial nested modular network
- Finitely dependent coloring
- An improvement of the Lovász local lemma via cluster expansion
- The lefthanded local lemma characterizes chordal dependency graphs
- On conflict-free multi-coloring
- The Lovász Local Lemma and Satisfiability
- Improved bounds on coloring of graphs
- scientific article; zbMATH DE number 1145886 (Why is no real title available?)
- Commutativity in the Algorithmic Lovász Local Lemma
- Shearer's measure and stochastic domination of product measures
- Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
- An algorithmic proof of the Lovász local lemma via resampling oracles
- scientific article; zbMATH DE number 7375995 (Why is no real title available?)
- Commutative algorithms approximate the LLL-distribution
- Fisher Zeros and Correlation Decay in the Ising Model
- New bounds for the Moser-Tardos distribution
- Fisher zeros and correlation decay in the Ising model
- A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability
- Shearer's point process, the hard-sphere model, and a continuum Lovász local lemma
- A local lemma for focused stochastic algorithms
- Partially independent random variables
- Absence of zeros implies strong spatial mixing
- Conflict‐free chromatic number versus conflict‐free chromatic index
- Deterministic algorithms for the Lovász local lemma: Simpler, more general, and more parallel
- One-dependent colorings of the star graph
- Probability bounds for \(n\) random events under \((n-1)\)-wise independence
- Packing list‐colorings
- Zeros, chaotic ratios and the computational complexity of approximating the independence polynomial
- On connectivity in random graph models with limited dependencies
- Bears with hats and independence polynomials
- Fundamentals of partial rejection sampling
- On the zeroes of hypergraph independence polynomials
- Central limit theorems and the geometry of polynomials
- New bounds for proper h-conflict-free colorings
- Zero-free regions for the independence polynomial on restricted graph classes
- Variable version Lovász local lemma: a tale of two boundaries
- Hypergraph independence polynomials with a zero close to the origin
- A Kolmogorov complexity proof of the Lovász local lemma for satisfiability
- The limit of the zero locus of the independence polynomial for bounded degree graphs
- Local approximations of the independent set polynomial
- Path decompositions of oriented graphs
- Polychromatic coloring of tuples in hypergraphs
- Sink-free orientations: a local sampler with applications
- On the roots of independence polynomial: quantifying the gap
- Witness trees in the Moser-Tardos algorithmic Lovász local lemma and Penrose trees in the hard-core lattice gas
- \(k\)-independent percolation on trees
- The hat guessing number of graphs
- Sets of permutations that generate the symmetric group pairwise.
- An estimate for the probability of dependent events
This page was built for publication: On a problem of Spencer
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1072210)
