Loading...
Please wait, while we are loading the content...
Planting Colourings Silently
| Content Provider | Scilit |
|---|---|
| Author | Bapst, Victor Coja-Oghlan, Amin Efthymiou, Charilaos |
| Copyright Year | 2016 |
| Description | Letk⩾ 3 be a fixed integer and $letZ_{k}$(G) be the number ofk-colourings of the graphG. For certain values of the average degree, the random $variableZ_{k}$(G(n,m)) is known to be concentrated in the sense that $\tfrac{1}{n}(\ln Z_k(G(n,m))-\ln\Erw[Z_k(G(n,m))])$ converges to 0 in probability (Achlioptas and Coja-Oghlan,Proc. FOCS 2008). In the present paper we prove a significantly stronger concentration result. Namely, we show that for a wide range of average degrees, $\tfrac{1}{\omega}(\ln Z_k(G(n,m))-\ln\Erw[Z_k(G(n,m))])$ converges to 0 in probability foranydiverging function $\omega=\omega(n)\ra\infty$ . Forkexceeding a certain $constantk_{0}$this result covers all average degrees up to the so-calledcondensation phase $transitiond_{k,con}$, and this is best possible. As an application, we show that the experiment of choosing ak-colouring of the random graphG(n,m) uniformly at random is contiguous with respect to the so-called ‘planted model’. |
| Related Links | http://arxiv.org/pdf/1411.0610 https://www.cambridge.org/core/services/aop-cambridge-core/content/view/2BB714622DD89AC2FDB8D3479F52BC14/S0963548316000390a.pdf/div-class-title-planting-colourings-silently-div.pdf |
| Ending Page | 366 |
| Page Count | 29 |
| Starting Page | 338 |
| ISSN | 09635483 |
| e-ISSN | 14692163 |
| DOI | 10.1017/s0963548316000390 |
| Journal | Combinatorics, Probability and Computing |
| Issue Number | 3 |
| Volume Number | 26 |
| Language | English |
| Publisher | Cambridge University Press (CUP) |
| Publisher Date | 2017-05-01 |
| Access Restriction | Open |
| Subject Keyword | Combinatorics, Probability and Computing Mathematical Physics Primary 05c80 Secondary 05c15 |
| Content Type | Text |
| Resource Type | Article |
| Subject | Applied Mathematics Statistics and Probability Theoretical Computer Science Computational Theory and Mathematics |
