- Series
- ACO Student Seminar
- Time
- Friday, April 22, 2022 - 1:00pm for 1 hour (actually 50 minutes)
- Location
- Skiles 254
- Speaker
- Manuel Fernandez – Mathematics, Georgia Tech – mfernandez39@gatech.edu
- Organizer
- Abhishek Dhawan
Please Note: Streaming online at https://gatech.zoom.us/j/91232113113?pwd=MDhteEdtcENuME9kdXJmcUY0eWlSUT09
The clique chromatic number of a graph is the smallest number of colors in a vertex coloring so that no inclusion-maximal clique is monochromatic (ignoring isolated vertices).
For the binomial random graph G_{n,p} the clique chromatic number has been studied in a number of works since 2016, but for sparse edge-probabilities in the range n^{-2/5} \ll p \ll 1 even the order of magnitude remained a technical challenge.
Resolving open problems of Alon and Krivelevich as well as Lichev, Mitsche and Warnke, we determine the clique chromatic number of the binomial random graph G_{n,p} in most of the missing regime: we show that it is of order (\log n)/p for edge-probabilities n^{-2/5+\eps} \ll p \ll n^{-1/3} and n^{-1/3+\eps} \ll p \ll 1, for any constant \eps > 0.
Perhaps surprisingly for a result about random graphs, a key ingredient in the proof is an application of the probabilistic method (that hinges on careful counting and density arguments).
This talk is based on joint work with Lutz Warnke.