On the chromatic number of random Cayley graphs

DOI10.1017/S0963548316000304MaRDI QIDQ5366943zbMATH OpenOpenAlexFDO

Authors Ben Green

Publication date 10 October 2017

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1308.1872

zbMATH Keywords

asymptotically sharp chromatic numbers

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Random graphs (graph-theoretic aspects) (05C80) Inverse problems of additive number theory, including sumsets (11P70)

Abstract: Let G be an abelian group of cardinality N, where (N,6) = 1, and let A be a random subset of G. Form a graph Gamma_A on vertex set G by joining x to y if and only if x + y is in A. Then, almost surely as N tends to infinity, the chromatic number chi(Gamma_A) is at most (1 + o(1))N/2 log_2 N. This is asymptotically sharp when G = Z/NZ, N prime. Presented at the conference in honour of Bela Bollobas on his 70th birthday, Cambridge August 2013.

Recommendations

• The chromatic number of random Cayley graphs
• Distinguishing chromatic number of random Cayley graphs
• Counting sets with small sumset, and the clique number of random Cayley graphs
• One-point concentration of the clique and chromatic numbers of the random Cayley graph on \(\mathbb{F}_2^n\)
• scientific article; zbMATH DE number 4214033

Cites work

• Additive combinatorics
• Can visibility graphs be represented compactly?
• Counting sets with small sumset and applications
• Counting sets with small sumset, and the clique number of random Cayley graphs
• List coloring of random and pseudo-random graphs
• The chromatic number of random Cayley graphs
• The chromatic number of random graphs
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(15)

• On the chromatic number of structured Cayley graphs
• The chromatic number of finite group Cayley tables
• Distinguishing chromatic number of random Cayley graphs
• A Cheeger type inequality in finite Cayley sum graphs
• Counting sets with small sumset, and the clique number of random Cayley graphs
• The chromatic number of random Cayley graphs
• One-point concentration of the clique and chromatic numbers of the random Cayley graph on \(\mathbb{F}_2^n\)
• scientific article; zbMATH DE number 1787232 (Why is no real title available?)
• Visible lattice points and the chromatic zeta function of a graph
• Chromatic numbers of Cayley graphs on Z and recurrence
• On the subgraphs of Cayley sum graphs
• Chromatic numbers of Cayley graphs of abelian groups: a matrix method
• On the independence number of sparser random Cayley graphs
• Coloring minimal Cayley graphs
• On the cop number and the weak Meyniel conjecture for algebraic graphs

This page was built for publication: On the chromatic number of random Cayley graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5366943)