scientific article; zbMATH DE number 1380613
From MaRDI portal
Publication:4705349
DOI<63::AID-RSA3>3.0.CO;2-7 10.1002/(SICI)1098-2418(1999010)14:1<63::AID-RSA3>3.0.CO;2-7zbMath0962.05055MaRDI QIDQ4705349
Ehud Friedgut, Demetrios Achlioptas
Publication date: 19 December 1999
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items
Bootstrap percolation on the hypercube ⋮ Phase transitions in discrete structures ⋮ Random Instances of Problems in NP – Algorithms and Statistical Physics ⋮ An enhanced formulation for solving graph coloring problems with the Douglas-Rachford algorithm ⋮ Upper-bounding the \(k\)-colorability threshold by counting covers ⋮ Inter-generational comparison of quantum annealers in solving hard scheduling problems ⋮ Hypercontractivity for global functions and sharp thresholds ⋮ Lower bounds on the chromatic number of random graphs ⋮ On the chromatic number of random regular graphs ⋮ Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs ⋮ Critical window of the symmetric perceptron ⋮ Estimating the strong \(r\)-colorability threshold in random hypergraphs ⋮ Planting Colourings Silently ⋮ On the connectivity of proper colorings of random graphs and hypergraphs ⋮ Another look at the phenomenon of phase transition ⋮ A Spectral Approach to Analysing Belief Propagation for 3-Colouring ⋮ On the chromatic number of random graphs ⋮ Constraining the clustering transition for colorings of sparse random graphs ⋮ Sharp thresholds for certain Ramsey properties of random graphs ⋮ Why almost all \(k\)-colorable graphs are easy to color ⋮ Between 2- and 3-colorability ⋮ A case study in programming a quantum annealer for hard operational planning problems ⋮ Gibbs measures and phase transitions on sparse random graphs ⋮ The typical structure of sparse $K_{r+1}$-free graphs ⋮ Local convergence of random graph colorings ⋮ Homomorphism complexes and \(k\)-cores ⋮ On the Potts antiferromagnet on random graphs ⋮ Almost all graphs with average degree 4 are 3-colorable ⋮ The condensation phase transition in random graph coloring ⋮ Colorings of partial Steiner systems and their applications ⋮ On the Number of Solutions in Random Graphk-Colouring ⋮ The SAT-UNSAT transition for random constraint satisfaction problems ⋮ The property of having a k -regular subgraph has a sharp threshold ⋮ When does the giant component bring unsatisfiability? ⋮ The resolution complexity of random graph \(k\)-colorability ⋮ Threshold properties of random Boolean constraint satisfaction problems ⋮ A novel giant-subgraph phase-transition in sparse random \(k\)-partite graphs ⋮ On the chromatic number of a random hypergraph ⋮ Spines of random constraint satisfaction problems: definition and connection with computational complexity
Cites Work
- Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
- A note on the sharp concentration of the chromatic number of random graphs
- Correlation inequalities on some partially ordered sets
- The concentration of the chromatic number of random graphs
- Almost all graphs with 1.44n edges are 3-colorable
- On the critical percolation probabilities
- The chromatic number of random graphs
- The chromatic number of random graphs
