Hostname: page-component-586b7cd67f-l7hp2 Total loading time: 0 Render date: 2024-11-24T20:04:30.240Z 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: [email protected])
Get access Rights & Permissions [Opens in a new window]

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 + 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
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 2 , March 2017 , pp. 248 - 266
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 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