On a problem of Spencer

DOI10.1007/BF02579368MaRDI QIDQ1072210zbMATH OpenOpenAlexWikidataFDO

Authors James B. Shearer

Publication date 1985

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02579368

zbMATH Keywords

existence of combinatorial configurationsprobabilistic methodrandom graph

Mathematics Subject Classification ID

Graph theory (05C99) Combinatorial probability (60C05)

Recommendations

• The harmonic mean formula for probabilities of unions: Applications to sparse random graphs
• On the probability of independent sets in random graphs
• Independent sets in random sparse graphs
• scientific article; zbMATH DE number 4108812
• On the independence number of sparse graphs

Cites work

• Asymptotic lower bounds for Ramsey functions

Cited in

(64)

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