On the Power of Choice for k-Colorability of Random Graphs

Dani, Varsha; Gupta, Diksha; Hayes, Thomas P.

doi:10.4230/LIPIcs.APPROX/RANDOM.2021.59

File

LIPIcs.APPROX-RANDOM.2021.59.pdf

Filesize: 0.7 MB
17 pages

Document Identifiers

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.59
URN: urn:nbn:de:0030-drops-147527

Author Details

Varsha Dani

Ronin Institute, Montclair, NJ, USA
Dept. of Computer Science, Rochester Institute of Technology, NY, USA

Diksha Gupta

School of Computing, National University of Singapore, Singapore

Thomas P. Hayes

Dept. of Computer Science, University of New Mexico, Albuquerque, NM, USA
http:cs.unm.edu/ hayest

Acknowledgements

The authors would like to thank Will Perkins for suggesting the problem of shifting the threshold for k-coloring, and Will Perkins and Cris Moore for helpful conversations.

Cite As Get BibTex

Varsha Dani, Diksha Gupta, and Thomas P. Hayes. On the Power of Choice for k-Colorability of Random Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 59:1-59:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.59

Abstract

In an r-choice Achlioptas process, random edges are generated r at a time, and an online strategy is used to select one of them for inclusion in a graph. We investigate the problem of whether such a selection strategy can shift the k-colorability transition; that is, the number of edges at which the graph goes from being k-colorable to non-k-colorable.
We show that, for k ≥ 9, two choices suffice to delay the k-colorability threshold, and that for every k ≥ 2, six choices suffice.

Subject Classification

ACM Subject Classification

Mathematics of computing → Stochastic processes
Theory of computation → Generating random combinatorial structures

Keywords

Random graphs
Achlioptas Processes
Phase Transition
Graph Colorability

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

References

Dimitris Achlioptas and Cristopher Moore. Almost all graphs with average degree 4 are 3-colorable. Journal of Computer and System Sciences, 67(2):441-471, 2003.
Dimitris Achlioptas and Assaf Naor. The two possible values of the chromatic number of a random graph. Annals of mathematics, 162(3):1335-1351, 2005.
Tom Bohman and Alan Frieze. Avoiding a giant component. Random Structures & Algorithms, 19(1):75-85, 2001.
Tom Bohman, Alan Frieze, and Nicholas C Wormald. Avoidance of a giant component in half the edge set of a random graph. Random Structures & Algorithms, 25(4):432-449, 2004.
Amin Coja-Oghlan and Dan Vilenchik. Chasing the k-colorability threshold. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 380-389. IEEE, 2013.
Varsha Dani, Josep Diaz, Thomas Hayes, and Cristopher Moore. The power of choice for random satisfiability. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 484-496. Springer, 2013.
Paul Erdős and Alfréd Rényi. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5(1):17-60, 1960.
Cristopher Moore and Stephan Mertens. The nature of computation. OUP Oxford, 2011.
Will Perkins. Random k-SAT and the power of two choices. Random Structures & Algorithms, 47(1):163-173, 2015.
Andrea W Richa, M Mitzenmacher, and R Sitaraman. The power of two random choices: A survey of techniques and results. Combinatorial Optimization, 9:255-304, 2001.
Oliver Riordan and Lutz Warnke. Achlioptas process phase transitions are continuous. The Annals of Applied Probability, 22(4):1450-1464, 2012.
Alistair Sinclair and Dan Vilenchik. Delaying satisfiability for random 2-SAT. Random Structures & Algorithms, 43(2):251-263, 2013.
Joel Spencer and Nicholas Wormald. Birth control for giants. Combinatorica, 27(5):587-628, 2007.