Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-05T06:39:22.343Z Has data issue: false hasContentIssue false

On the Chromatic Number of Random Cayley Graphs

Published online by Cambridge University Press:  09 September 2016

BEN GREEN*
Affiliation:
Mathematical Institute, Andrew Wiles Building, Radcliffe Observatory Quarter, Woodstock Road, Oxford OX2 6GG, UK (e-mail: [email protected])

Abstract

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 + yA. 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.

Type
Paper
Copyright
Copyright © Cambridge University Press 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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 347365.Google Scholar
[2] Alon, N. (2013) The chromatic number of random Cayley graphs. European J. Combin. 34 12321243.Google Scholar
[3] Alon, N., Krivelevich, M. and Sudakov, B. (1999) List coloring of random and pseudo-random graphs. Combinatorica 19 453472.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 4955.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 307326.Google Scholar
[8] Green, B. J. and Morris, R. (2016) Counting sets with small sumset and applications. Combinatorica 36 129159.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