On independent sets in random graphs

DOI10.1002/rsa.20550zbMath1325.05147arXiv1007.1378OpenAlexW2042503074MaRDI QIDQ3452727

Amin Coja-Oghlan, Charilaos Efthymiou

Publication date: 13 November 2015

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1007.1378

zbMATH Keywords

phase transitionsrandom graphsindependent set problemMetropolis process

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Density (toughness, etc.) (05C42)

Related Items

Sparse high-dimensional linear regression. Estimating squared error and a phase transition, New results relating independence and matchings, Random Instances of Problems in NP – Algorithms and Statistical Physics, The largest hole in sparse random graphs, Two-Point Concentration of the Independence Number of the Random Graph, Algorithmic obstructions in the random number partitioning problem, Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics, Phase transitions for the cavity approach to the clique problem on random graphs, The overlap gap property and approximate message passing algorithms for \(p\)-spin models, Constructing concrete hard instances of the maximum independent set problem, Generalized random sequential adsorption on Erdős-Rényi random graphs, The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs, Finding a large submatrix of a Gaussian random matrix, An efficient local search framework for the minimum weighted vertex cover problem, On the independent set problem in random graphs, Independent Sets in Random Graphs from the Weighted Second Moment Method, Sofic homological invariants and the Weak Pinsker Property, Optimal low-degree hardness of maximum independent set

Cites Work

• Unnamed Item
• Unnamed Item
• Optimization by Simulated Annealing
• Phase transitions for the cavity approach to the clique problem on random graphs
• Backtrack: An O(1) expected time algorithm for the graph coloring problem
• On the independence number of random graphs
• Graphs with small chromatic numbers are easy to color
• Concentration of measure and isoperimetric inequalities in product spaces
• The solution of some random NP-hard problems in polynomial expected time
• Reconstruction and Clustering in Random Constraint Satisfaction Problems
• On Counting Independent Sets in Sparse Graphs
• Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method
• Finding Large Independent Sets in Polynomial Expected Time
• Information, Physics, and Computation
• Application of statistical mechanics to NP-complete problems in combinatorial optimisation
• Almost all k-colorable graphs are easy to color
• Large Cliques Elude the Metropolis Process
• On colouring random graphs
• Cliques in random graphs
• Analysis of Two Simple Heuristics on a Random Instance ofk-sat
• Finding and certifying a large hidden clique in a semirandom graph
• Gibbs states and the set of solutions of random constraint satisfaction problems
• A Better Algorithm for Random k-SAT
• Some remarks on the theory of graphs