TY - JOUR

T1 - The chromatic number of random Cayley graphs

AU - Alon, Noga

N1 - Funding Information:
Research supported in part by an ERC Advanced grant, by a USA-Israeli BSF grant and by NSF grant No. DMS-0835373 .

PY - 2013/11

Y1 - 2013/11

N2 - We consider the typical behavior of the chromatic number of a random Cayley graph of a given group of order n with respect to a randomly chosen set of size k ≤ n / 2. This behavior depends on the group: for some groups it is typically 2 for all k < 0.99log 2n, whereas for some other groups it grows whenever k grows. The results obtained include a proof that for any large prime p, and any 1 ≤ k ≤ 0.99log 3p, the chromatic number of the Cayley graph of Z p with respect to a uniform random set of k generators is, asymptotically almost surely, precisely 3. This strengthens a recent result of Czerwiński. On the other hand, for k > log p, the chromatic number is typically at least Ω(k/logp) and for k = Θ (p) it is Θ(plogp).For some non-abelian groups (like SL2 (Z q) ), the chromatic number is, asymptotically almost surely, at least kΩ (1) for every k, whereas for elementary abelian 2-groups of order n = 2t and any k satisfying 1.001t ≤ k ≤ 2.999t the chromatic number is, asymptotically almost surely, precisely 4. Despite these discrepancies between different groups, it seems plausible to conjecture that for any group of order n and any k ≤ n / 2, the typical chromatic number of the corresponding Cayley graph cannot differ from k by more than a poly-logarithmic factor in n.

AB - We consider the typical behavior of the chromatic number of a random Cayley graph of a given group of order n with respect to a randomly chosen set of size k ≤ n / 2. This behavior depends on the group: for some groups it is typically 2 for all k < 0.99log 2n, whereas for some other groups it grows whenever k grows. The results obtained include a proof that for any large prime p, and any 1 ≤ k ≤ 0.99log 3p, the chromatic number of the Cayley graph of Z p with respect to a uniform random set of k generators is, asymptotically almost surely, precisely 3. This strengthens a recent result of Czerwiński. On the other hand, for k > log p, the chromatic number is typically at least Ω(k/logp) and for k = Θ (p) it is Θ(plogp).For some non-abelian groups (like SL2 (Z q) ), the chromatic number is, asymptotically almost surely, at least kΩ (1) for every k, whereas for elementary abelian 2-groups of order n = 2t and any k satisfying 1.001t ≤ k ≤ 2.999t the chromatic number is, asymptotically almost surely, precisely 4. Despite these discrepancies between different groups, it seems plausible to conjecture that for any group of order n and any k ≤ n / 2, the typical chromatic number of the corresponding Cayley graph cannot differ from k by more than a poly-logarithmic factor in n.

UR - http://www.scopus.com/inward/record.url?scp=84881025308&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84881025308&partnerID=8YFLogxK

U2 - 10.1016/j.ejc.2013.05.007

DO - 10.1016/j.ejc.2013.05.007

M3 - Article

AN - SCOPUS:84881025308

VL - 34

SP - 1232

EP - 1243

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

SN - 0195-6698

IS - 8

ER -