Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-10T04:35:54.792Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Chromatic Number of Random Cayley Graphs

Part of: Graph theory Additive number theory; partitions

Published online by Cambridge University Press:  09 September 2016

BEN GREEN
BEN GREEN*
Affiliation:
Mathematical Institute, Andrew Wiles Building, Radcliffe Observatory Quarter, Woodstock Road, Oxford OX2 6GG, UK (e-mail: ben.green@maths.ox.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Let G be an abelian group of cardinality n, where hcf(n, 6) = 1, and let A be a random subset of G. Form a graph ΓA on vertex set G by joining x to y if and only if x + y ∈ A. Then, with high probability as n → ∞, the chromatic number χ(ΓA ) is at most $(1 + o(1))\tfrac{n}{2\log_2 n}$ . This is asymptotically sharp when G = ℤ/nℤ, n prime.

MSC classification

Primary: 05C15: Coloring of graphs and hypergraphs
Secondary: 11P70: Inverse problems of additive number theory, including sumsets

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 2 , March 2017 , pp. 248 - 266
Copyright
Copyright © Cambridge University Press 2016 

References

[1] Agarwal, P. K., Alon, N., Aronov, B. and Suri, S. (1994) Can visibility graphs be represented compactly? In ACM Symposium on Computational Geometry: San Diego, CA, 1993. Discrete Comput. Geom. 12 347–365.Google Scholar
[2] Alon, N. (2013) The chromatic number of random Cayley graphs. European J. Combin. 34 1232–1243.Google Scholar
[3] Alon, N., Krivelevich, M. and Sudakov, B. (1999) List coloring of random and pseudo-random graphs. Combinatorica 19 453–472.Google Scholar
[4] Alon, N. and Spencer, J. H. (2000) The Probabilistic Method, second edition, Wiley Interscience.Google Scholar
[5] Bollobás, B. (1988) The chromatic number of random graphs. Combinatorica 8 49–55.Google Scholar
[6] Christophides, D. Random Cayley graphs. In Midsummer Combinatorial Workshop 2011, to appear. http://www.christofides.org/Papers/mcw11.pdf Google Scholar
[7] Green, B. J. (2005) Counting sets with small sumset, and the clique number of random Cayley graphs. Combinatorica 25 307–326.Google Scholar
[8] Green, B. J. and Morris, R. (2016) Counting sets with small sumset and applications. Combinatorica 36 129–159.CrossRefGoogle Scholar
[9] Tao, T. C. and Vu, V. H. (2006) Additive Combinatorics , Vol. 105 of Cambridge Studies in Advanced Mathematics, Cambridge University Press.Google Scholar