{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T16:00:51Z","timestamp":1762272051286},"reference-count":9,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2016,9,9]],"date-time":"2016-09-09T00:00:00Z","timestamp":1473379200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2017,3]]},"abstract":"<jats:p>Let <jats:italic>G<\/jats:italic> be an abelian group of cardinality <jats:italic>n<\/jats:italic>, where hcf(<jats:italic>n<\/jats:italic>, 6) = 1, and let <jats:italic>A<\/jats:italic> be a random subset of <jats:italic>G<\/jats:italic>. Form a graph \u0393<jats:italic><jats:sub>A<\/jats:sub><\/jats:italic> on vertex set <jats:italic>G<\/jats:italic> by joining <jats:italic>x<\/jats:italic> to <jats:italic>y<\/jats:italic> if and only if <jats:italic>x<\/jats:italic> + <jats:italic>y<\/jats:italic> \u2208 <jats:italic>A<\/jats:italic>. Then, with high probability as <jats:italic>n<\/jats:italic> \u2192 \u221e, the chromatic number \u03c7(\u0393<jats:sub><jats:italic>A<\/jats:italic><\/jats:sub>) is at most <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548316000304_inline1\" \/><jats:tex-math>$(1 + o(1))\\tfrac{n}{2\\log_2 n}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. This is asymptotically sharp when <jats:italic>G<\/jats:italic> = <jats:italic>\u2124\/n\u2124<\/jats:italic>, <jats:italic>n<\/jats:italic> prime.<\/jats:p>","DOI":"10.1017\/s0963548316000304","type":"journal-article","created":{"date-parts":[[2016,9,9]],"date-time":"2016-09-09T04:10:00Z","timestamp":1473394200000},"page":"248-266","source":"Crossref","is-referenced-by-count":6,"title":["On the Chromatic Number of Random Cayley Graphs"],"prefix":"10.1017","volume":"26","author":[{"given":"BEN","family":"GREEN","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2016,9,9]]},"reference":[{"key":"S0963548316000304_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-015-3129-4"},{"key":"S0963548316000304_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/s004939970001"},{"key":"S0963548316000304_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-005-0018-2"},{"key":"S0963548316000304_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122551"},{"key":"S0963548316000304_ref4","doi-asserted-by":"publisher","DOI":"10.1002\/0471722154"},{"key":"S0963548316000304_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2013.05.007"},{"key":"S0963548316000304_ref6","unstructured":"Christophides D. Random Cayley graphs. In Midsummer Combinatorial Workshop 2011, to appear. http:\/\/www.christofides.org\/Papers\/mcw11.pdf"},{"key":"S0963548316000304_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574385"},{"key":"S0963548316000304_ref9","volume-title":"Cambridge Studies in Advanced Mathematics","author":"Tao","year":"2006"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548316000304","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,17]],"date-time":"2019-04-17T22:09:35Z","timestamp":1555538975000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548316000304\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9,9]]},"references-count":9,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,3]]}},"alternative-id":["S0963548316000304"],"URL":"https:\/\/doi.org\/10.1017\/s0963548316000304","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,9,9]]}}}