Find the range of expected chromatic numbers for a random graph
Home
Search
Subjects
About Erdös
About This Site
Search
Subjects
- All (170)
- Ramsey Theory (40)
- Extremal Graph Theory (40)
- Coloring, Packing, and Covering (25)
- Random Graphs and Graph Enumeration (16)
- Hypergraphs (35)
- Infinite Graphs (14)
About Erdös
About This Site
Problem (proposed by
Erdös\( ^{[1]}\))
How accurately can one estimate the chromatic number of a
random graph with edge probability \( \frac{1}{2}\)?
Prove or disprove that the range of expected values is more (much more) than \( O(1) \).
Shamir and Spencer have an upper bound \( ^{[1]}\) of \( O(n^{1/2})\), which, according to N. Alon, can be slightly improved to \( O(n^{1/2}/\log n)\).
In 2008, Loh and Sudakov showed that the strong chromatic number is is highly concentrated on one value in the dense case, as well as some weaker results in the sparse case \( ^{[4]}\).
In 2010, Kekes, Pérez - Giménez, and Xaviar obtained sharp concentration results for random \( d-\)regular graphs, showing that with high probability the chromatic numbers can take at most two values \( ^{[3]}\).
Bibliography | |
---|---|
1 | E. Shamir and J. Spencer, Sharp concentration of the chromatic number of random graphs \( G_{n,p}\), Combinatorica 7 (1987), 121-129. |
2 | N. Alon, J. H. Spencer and P. Erdös, The Probabilistic Method, Wiley and Sons, New York, 1992. (Link To sample sections.) |
3 | Kemkes, Graeme; Pérez-Giménez, Xavier; Wormald, Nicholas On the chromatic number of random d-regular graphs. Adv. Math. 223 (2010), no. 1, 300–328. |
4 | Loh, Po-Shen; Sudakov, Benny
On the strong chromatic number of random graphs.
Combin. Probab. Comput. 17 (2008), no. 2, 271–286.
|