alphaFeedback

WorksMathematics

Existence of the qq-Colorability Threshold for Sparse Random Graphs

AI contributions
Not recorded for this paper
View details

Abstract

For a fixed integer q≥3q \ge 3, we call a graph qq-colorable if its vertices admit qq colors with adjacent vertices colored differently. We prove that there exists dq>0d_q > 0 such that the random graph on nn vertices with independent edge probability d/nd/n is qq-colorable with probability tending to one for fixed 0≤d<dq0 \le d < d_q and to zero for fixed d>dqd > d_q, as n→∞n \to \infty. The same holds for the uniform random graph with ⌊cn⌋\lfloor cn \rfloor edges, for fixed c≥0c \ge 0, with threshold dq/2d_q/2 in cc. For fixed ϵ∈(0,1)\epsilon \in (0, 1), the first loss of colorability under independent uniform additions of pairs of distinct vertices lies with probability at least 1−ϵ1 - \epsilon in a deterministic window of Oq,ϵ(n(log⁡n)−3/2)O_{q, \epsilon}(n(\log n)^{-3/2}) steps, where log⁡\log is natural. The proof uses interpolation to establish convergence and bounds the expected number of pairs needed to destroy colorability of the last colorable graph by identifying random vertices and controlling the growth of classes equal in every coloring.

Authors’ Note

With the exception of these notes, the entire document is machine-written. We have carefully supervised its preparation to ensure that the proofs are readable and that previous literature is appropriately cited. We are releasing this manuscript on Hexagon to disseminate the results as quickly as possible because they may be of interest to the mathematical community. A more carefully written version of this manuscript is in preparation and will be submitted for publication. We welcome suggestions concerning mathematical corrections, omitted citations, and attribution of ideas.

P. L. was partially supported by NSF grant DMS-2450004.

Introduction

Background

Let n≥1n \ge1 and q≥2q \ge2 be integers. We let log⁡\log denote the natural logarithm, and let P\mathbb{P}, E\mathbb{E}, and Var⁡\operatorname{Var} denote probability, expectation, and variance, respectively. For every integer k≥1k \ge1, we set [k]={1,…,k}[k] = \{1, \ldots, k\}. We call a map σ:[n]→[q]\sigma: [n] \to[q] a qq-coloring of a graph on [n][n] if σ(u)≠σ(v)\sigma(u) \ne\sigma(v) for all edges {u,v}\{u, v\}. We call a graph qq-colorable if it has a qq-coloring. We define its chromatic number to be the least number of colors in such a coloring. For every integer 0≤m≤(n2)0 \le m \le\binom{n}{2}, we let G(n,m)G(n,m) denote a uniformly random simple graph on [n][n] with mm edges. For p∈[0,1]p \in[0,1], we let G(n,p)G(n,p) denote the random simple graph on [n][n] in which each pair is an edge independently with probability pp. This paper concerns G(n,⌊cn⌋)G(n,\lfloor cn \rfloor) and G(n,d/n)G(n,d/n) for fixed constants c,d≥0c,d \ge0 and sufficiently large nn. The expected average degrees of these models tend to 2c2c and dd, respectively.

The study of the chromatic number of sparse random graphs goes back to Erdős and Rényi, who asked in [30 Section 10, p. 59] for the chromatic number of a random graph on nn vertices with about cncn edges, for c>1/2c > 1/2. For every q≥3q \ge3, Achlioptas and Friedgut proved that qq-colorability has a sharp threshold [2 Theorem 1.1]. More precisely, there exists a sequence (d^n)(\hat d_n) (which depends on qq) such that for every fixed ω>0\omega> 0,

lim⁡n→∞P(G(n,min⁡{1,max⁡{0,d^n−ωn}}) is q-colorable)=1,lim⁡n→∞P(G(n,min⁡{1,d^n+ωn}) is q-colorable)=0.(1)\begin{aligned} \lim_{n \to\infty} \mathbb{P}\left(G\left(n,\min\left\{1,\max\left\{0,\frac{\hat d_n-\omega}{n}\right\}\right\}\right)\text{ is }q\text{-colorable}\right) &= 1,\\ \lim_{n \to\infty} \mathbb{P}\left(G\left(n,\min\left\{1,\frac{\hat d_n+\omega}{n}\right\}\right)\text{ is }q\text{-colorable}\right) &= 0. \tag*{(1)} \end{aligned}

Their proof rests on Friedgut’s criterion for sharp thresholds [32], which relates a coarse threshold to the approximation of the property by the appearance of bounded subgraphs, and it leaves the dependence of d^n\hat d_n on nn undetermined. Achlioptas and Friedgut expressed the belief that d^n\hat d_n converges, and they recorded its convergence as an open problem [2 Remark 1.2]. Achlioptas and Molloy had already noted that this convergence was widely conjectured [3 p. 204], and later works describe it as a well-known open problem [21 Section 1.1], [9 Section 1]. The goal of this paper is to prove that d^n\hat d_n converges for every q≥3q \ge3.

We first recall the known bounds on the location of the transition. For q=3q = 3, the random graph G(n,d/n)G(n,d/n) is 3-colorable with probability tending to one for d≤4.03d \le4.03 [4 Corollary 2], and with probability tending to zero for d>4.697d > 4.697 [8 Section 1.3] (see [3, 18, 27, 41] for earlier bounds). For general qq, we set γq=log⁡q/log⁡(q/(q−1))\gamma_q = \log q/\log(q/(q-1)). We use oq(1)o_q(1) for a quantity tending to zero as q→∞q \to\infty, after the limit in nn at fixed qq. A first-moment computation in G(n,⌊cn⌋)G(n,\lfloor cn\rfloor) gives non-colorability with probability tending to one when c>γqc > \gamma_q. Comparing the fixed-edge and binomial models gives the same conclusion for G(n,d/n)G(n,d/n) when d>2γqd > 2\gamma_q. We have 2γq=2qlog⁡q−log⁡q+oq(1)2\gamma_q = 2q\log q - \log q + o_q(1). Achlioptas and Naor showed that G(n,d/n)G(n,d/n) is qq-colorable with probability tending to one for d<2(q−1)log⁡(q−1)d < 2(q-1)\log(q-1), and that its chromatic number is concentrated on two explicit consecutive integers [5 Theorem 1]. Coja-Oghlan and Vilenchik [21, Theorem 1.1} and Coja-Oghlan [20 Theorem 1] then proved that

lim inf⁡n→∞d^n≥2qlog⁡q−log⁡q−2log⁡2−oq(1),lim sup⁡n→∞d^n≤2qlog⁡q−log⁡q−1+oq(1),(2)\liminf_{n\to\infty}\hat d_n \ge2q\log q-\log q-2\log2-o_q(1), \qquad\limsup_{n\to\infty}\hat d_n \le2q\log q-\log q-1+o_q(1), \tag*{(2)}

and Coja-Oghlan and Vilenchik also showed that the chromatic number of G(n,d/n)G(n,d/n) is concentrated on a single value for all dd in an explicit set of asymptotic density one [21 Theorem 1.2]. These results locate the transition. However, they do not show that d^n\hat d_n converges.

Statistical physics gives precise, non-rigorous predictions. Statistical-physics computations place the 3-colorability threshold near average degree 4.69 [49], refined numerically to 4.687(2) [63 Table II], and give the asymptotic form 2qlog⁡q−log⁡q−1+oq(1)2q\log q-\log q-1+o_q(1) for large qq [42], which agrees with the upper bound in (2). The same theory predicts further transitions in the set of colorings below the colorability threshold [43, 63]. Rigorous results on the number of colorings below that threshold were obtained for large qq [9 Theorem 2.1] and later for all q≥3q \ge3 [23 arXiv:1611.00814v4, Theorem 1.2].

For other random constraint satisfaction problems, the existence of a limiting threshold is known in several cases. The threshold of random 2-SAT is at one clause per variable [19, 36], with a window of order n2/3n^{2/3} clauses [11 Theorem 1.1]. The threshold of random kk-XORSAT was determined for k=3k = 3 in [28] and for all k≥3k \ge3 in [56]. Ding, Sly, and Sun proved the existence of the threshold for random kk-SAT, and identified its value, for all sufficiently large kk [26 Theorem 1]. For random dd-regular graphs and all sufficiently large qq, Coja-Oghlan, Efthymiou, and Hetterich located the qq-colorability threshold in an interval of length less than one [22 Theorem 1.1 and Corollary 1.2]. Since the degree is an integer, this leaves at most one degree at which the limiting behavior is not determined. This argument does not apply to G(n,d/n)G(n,d/n), in which dd varies continuously.

Recently, two preprints claimed the existence of a limiting threshold for random kk-SAT for every fixed k≥3k \ge3, without identifying its value. These preprints use independent uniformly signed clauses, with distinct variables within each clause and with replacement between clauses. Carenini [16 Theorem 1.1 and Corollary 1.2] claims an upper bound of order n1/2+1/kn^{1/2+1/k} clauses for the window, improving her earlier O(n/log⁡n)O(n/\log n) bound [17 Corollary 7.10]. She obtains the polynomial bound from a variance bound for the hitting time of unsatisfiability and deduces the existence of the threshold from a criterion of Abbe and Montanari [1], in the form stated in [55 Proposition 14]. The preprint [51 Theorem 1.1] claims the same conclusion, combining a variance bound for a capped hitting time with an interpolation inequality and comparisons between systems of different sizes. The latter preprint explicitly credits Carenini with priority for the threshold-existence result [51 abstract and Section 1]. These preprints are unrefereed. We give self-contained proofs of the adaptations used here, while drawing on their arguments as described below. To the best of our knowledge, the convergence of d^n\hat{d}_n had not previously been established for a single value of q≥3q \ge3.

Main results

From now on, we fix an integer q≥3q \ge3. Recall that

γq=log⁡qlog⁡(q/(q−1)).(3)\gamma_q = \frac{\log q}{\log(q/(q-1))}. \tag*{(3)}

Our main result is the existence of the qq-colorability threshold.

Theorem 1.1. Let q≥3q \ge3 be an integer. There exists αq∈[1/2,γq]\alpha_q \in[1/2,\gamma_q] such that for every fixed real c≥0c \ge0,

lim⁡n→∞P(G(n,⌊cn⌋) is q-colorable)={1if 0≤c<αq,0if c>αq,\lim_{n \to\infty} \mathbb{P}\left(G(n,\lfloor cn\rfloor)\text{ is }q\text{-colorable}\right) = \begin{cases} 1 & \text{if }0 \le c < \alpha_q,\\ 0 & \text{if }c > \alpha_q, \end{cases}

and for every fixed real d≥0d \ge0,

lim⁡n→∞P(G(n,d/n) is q-colorable)={1if 0≤d<2αq,0if d>2αq,\lim_{n \to\infty} \mathbb{P}\left(G(n,d/n)\text{ is }q\text{-colorable}\right) = \begin{cases} 1 & \text{if }0 \le d < 2\alpha_q,\\ 0 & \text{if }d > 2\alpha_q, \end{cases}

where G(n,d/n)G(n,d/n) is defined for n≥dn \ge d.

We define dq=2αqd_q = 2\alpha_q to be the threshold in terms of the asymptotic average degree. To relate our result to the sharp threshold sequence, we show that d^n→dq\hat{d}_n \to d_q. Fix 0<ω<dq0 < \omega< d_q. If d^n≥dq+ω\hat{d}_n \ge d_q + \omega along a subsequence, the lower side of (1), with shift ω/2\omega/2, and monotonicity imply that G(n,(dq+ω/2)/n)G(n,(d_q + \omega/2)/n) is colorable with probability tending to one along that subsequence, contrary to Theorem 1.1. If d^n≤dq−ω\hat{d}_n \le d_q - \omega along a subsequence, the upper side, with the same shift, implies that G(n,(dq−ω/2)/n)G(n,(d_q - \omega/2)/n) is colorable with probability tending to zero, again a contradiction. This proves the claim.

The bounds on the limit inferior and limit superior in (2) now transfer directly to dqd_q. A bound at a fixed density transfers as well. If it failed for dqd_q, a density strictly between the two values would contradict monotonicity and Theorem 1.1. In particular, 4.03≤d3≤4.6974.03 \le d_3 \le4.697, and dqd_q satisfies the two bounds in (2).

The bounds 1/2≤αq≤γq1/2 \le\alpha_q \le\gamma_q in Theorem 1.1 are classical and are included for completeness. The upper bound is the first-moment bound mentioned above. The lower bound holds since, for c<1/2c < 1/2, with probability tending to one every component of G(n,⌊cn⌋)G(n, \lfloor cn \rfloor) is a tree or has exactly one cycle [30], [40 Theorem 5.5, p. 112], and such graphs are 3-colorable. Theorem 1.1 is an asymptotic statement. As we explain in Remark 7.4, our proof gives no further information on the value of αq\alpha_q and no rate of convergence.

References

  1. [1]Emmanuel Abbe and Andrea Montanari. On the concentration of the number of solutions of random satisfiability formulas. Random Structures & Algorithms, 45(3):362–382, 2014. doi: 10.1002/rsa.20501. URL https://doi.org/10.1002/rsa.20501. Published online April 12, 2013.
  2. [2]Dimitris Achlioptas and Ehud Friedgut. A sharp threshold for k-colorability. Random Structures & Algorithms, 14(1):63–70, 1999. doi: 10.1002/(SICI)1098-2418(19990110)14:1<63::AID-RSA3>3.0.CO;2-7. URL https://cgi.di.uoa.gr/~optas/papers/k-color-threshold.pdf.
  3. [3]Dimitris Achlioptas and Michael Molloy. The analysis of a list-coloring algorithm on a random graph. In Proceedings of the 38th Annual Symposium on Foundations of Computer Science, pages 204–212. IEEE, 1997. doi: 10.1109/SFCS.1997.646109. URL https://cgi.di.uoa.gr/~optas/papers/list-coloring.pdf.
  4. [4]Dimitris Achlioptas and Christopher Moore. Almost all graphs with average degree 4 are 3-colorable. Journal of Computer and System Sciences, 67(2):441–471, 2003. doi: 10.1016/S0022-0000(03)00120-X. URL https://sites.santafe.edu/~moore/pubs/3coloring-jcss.DOI
  5. [5]Dimitris Achlioptas and Assaf Naor. The two possible values of the chromatic number of a random graph. Annals of Mathematics, 162(3):1335–1351, 2005. doi: 10.4007/annals.2005.162.1335. URL https://annals.math.princeton.edu/wp-content/uploads/annals-v162-n3-p05.pdf.DOI
  6. [6]Dimitris Achlioptas and Federico Ricci-Tersenghi. Random formulas have frozen variables. SIAM Journal on Computing, 39(1):260–280, 2009. doi: 10.1137/070680382. URL https://doi.org/10.1137/070680382. Conference predecessor: On the solution-space geometry of random constraint satisfaction problems, STOC 2006, pp. 130–139.
  7. [7]David J. Aldous. Threshold limits for cover times. Journal of Theoretical Probability, 4(1):197–211, 1991. doi: 10.1007/BF01047002. URL https://doi.org/10.1007/BF01047002.
  8. [8]Peter Ayre, Amin Coja-Oghlan, and Catherine Greenhill. Lower bounds on the chromatic number of random graphs. Combinatorica, 42:617–658, 2022. doi: 10.1007/s00493-021-4236-z. URL https://doi.org/10.1007/s00493-021-4236-z. Published online October 26, 2021.
  9. [9]Victor Bapst, Amin Coja-Oghlan, Samuel Hetterich, Felicia Raißmann, and Dan Vilenchik. The condensation phase transition in random graph coloring. Communications in Mathematical Physics, 341:543–606, 2016. doi: 10.1007/s00220-015-2464-z. URL https://doi.org/10.1007/s00220-015-2464-z.
  10. [10]Mohsen Bayati, David Gamarnik, and Prasad Tetali. Combinatorial approach to the interpolation method and scaling limits in sparse random graphs. The Annals of Probability, 41(6):4080–4115, 2013. doi: 10.1214/12-AOP816. URL https://doi.org/10.1214/12-AOP816.
  11. [11]Béla Bollobás, Christian Borgs, Jennifer T. Chayes, Jeong Han Kim, and David B. Wilson. The scaling window of the 2-SAT transition. Random Structures & Algorithms, 18(3):201–256, 2001. doi: 10.1002/rsa.1006. URL https://doi.org/10.1002/rsa.1006.
  12. [12]Stéphane Boucheron, Olivier Bousquet, Gábor Lugosi, and Pascal Massart. Moment inequalities for functions of independent random variables. The Annals of Probability, 33(2):514–560, 2005. doi: 10.1214/009117904000000856. URL https://doi.org/10.1214/009117904000000856.
  13. [13]Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: a nonasymptotic theory of independence. Oxford University Press, 2013. ISBN 9780199535255. doi: 10.1093/acprof:oso/9780199535255.001.0001. URL https://doi.org/10.1093/acprof:oso/9780199535255.001.0001.
  14. [16]Gaia Carenini. A polynomial scaling window for random k-SAT and a proof of the satisfiability conjecture. Technical Report TR26–229, Electronic Colloquium on Computational Complexity, October 2026. URL https://eccc.weizmann.ac.il/report/2026/229/. Preprint; October 5, 2026 report.
  15. [17]Gaia Carenini. The scaling window of random k-SAT. Technical Report TR26–145, Electronic Colloquium on Computational Complexity, August 2026. URL https://arxiv.org/abs/2609.26222v1. Preprint, arXiv version 1, August 11, 2026; also ECCC TR26-145, published August 16, 2026.
  16. [18]Vášek Chvátal. Almost all graphs with 1.44n edges are 3-colorable. Random Structures & Algorithms, 2(1):11–28, 1991. doi: 10.1002/rsa.3240020103. URL https://doi.org/10.1002/rsa.3240020103.
  17. [19]Vášek Chvátal and Bruce Reed. Mick gets some (the odds are on his side). In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, pages 620–627. IEEE, 1992. doi: 10.1109/SFCS.1992.267789. URL https://doi.org/10.1109/SFCS.1992.267789.
  18. [20]Amin Coja-Oghlan. Upper-bounding the k-colorability threshold by counting covers. The Electronic Journal of Combinatorics, 20(3):P32, 2013. doi: 10.37236/3337. URL https://doi.org/10.37236/3337.
  19. [21]Amin Coja-Oghlan and Dan Vilenchik. The chromatic number of random graphs for most average degrees. International Mathematics Research Notices, 2016(19):5801–5859, 2016. doi: 10.1093/imrn/rnv333. URL https://doi.org/10.1093/imrn/rnv333. Extended abstract: Chasing the k-colorability threshold, FOCS 2013, pp. 380–389.
  20. [22]Amin Coja-Oghlan, Charilaos Efthymiou, and Samuel Hetterich. On the chromatic number of random regular graphs. Journal of Combinatorial Theory, Series B, 116:367–439, 2016. doi: 10.1016/j.jctb.2015.09.006. URL https://doi.org/10.1016/j.jctb.2015.09.006.
  21. [23]Amin Coja-Oghlan, Florent Krzakala, Will Perkins, and Lenka Zdeborová. Information-theoretic thresholds from the cavity method. Advances in Mathematics, 333:694–795, 2018. doi: 10.1016/j.aim.2018.05.029. URL https://doi.org/10.1016/j.aim.2018.05.029.
  22. [24]Joseph Culberson and Ian Gent. Frozen development in graph coloring. Theoretical Computer Science, 265(1–2):227–264, 2001. doi: 10.1016/S0304-3975(01)00164-5. URL https://doi.org/10.1016/S0304-3975(01)00164-5.
  23. [25]N. G. de Bruijn and Paul Erdős. Some linear and some quadratic recursion formulas. II. Proceedings of the Koninklijke Nederlandse Akademie van Wetenschappen, Series A, 55:152–163, 1952. doi: 10.1016/S1385-7258(52)50021-0. URL https://doi.org/10.1016/S1385-7258(52)50021-0. Also Indagationes Mathematicae 14 (1952), 152–163; Theorems 22–23.
  24. [26]Jian Ding, Allan Sly, and Nike Sun. Proof of the satisfiability conjecture for large k. Annals of Mathematics, 196(1):1–388, 2022. doi: 10.4007/annals.2022.196.1.1. URL https://doi.org/10.4007/annals.2022.196.1.1.
  25. [27]Olivier Dubois and Jacques Mandler. On the non-3-colourability of random graphs, 2002. URL https://arxiv.org/abs/math/0209087v1. Preprint, version 1, September 9, 2002.
  26. [28]Olivier Dubois and Jacques Mandler. The 3-XORSAT threshold. Comptes Rendus Mathématique, 335(11):963–966, 2002. doi: 10.1016/S1631-073X(02)02563-3. URL https://doi.org/10.1016/S1631-073X(02)02563-3.
  27. [29]Bradley Efron and Charles Stein. The jackknife estimate of variance. The Annals of Statistics, 9(3):586–596, 1981. doi: 10.1214/aos/1176345462. URL https://doi.org/10.1214/aos/1176345462.
  28. [30]Paul Erdős and Alfréd Rényi. On the evolution of random graphs. A Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei, 5:17–61, 1960. URL https://users.renyi.hu/~p_erdos/1960-10.pdf.
  29. [31]Silvio Franz and Michele Leone. Replica bounds for optimization problems and diluted spin systems. Journal of Statistical Physics, 111(3–4):535–564, 2003. doi: 10.1023/A:1022885828956. URL https://doi.org/10.1023/A:1022885828956.
  30. [32]Ehud Friedgut. Sharp thresholds of graph properties, and the k-SAT problem. Journal of the American Mathematical Society, 12(4):1017–1054, 1999. doi: 10.1090/S0894-0347-99-00305-7. URL https://doi.org/10.1090/S0894-0347-99-00305-7. With an appendix by Jean Bourgain.
  31. [33]Ehud Friedgut and Gil Kalai. Every monotone graph property has a sharp threshold. Proceedings of the American Mathematical Society, 124(10):2993–3002, 1996. doi: 10.1090/S0002-9939-96-03732-X. URL https://doi.org/10.1090/S0002-9939-96-03732-X.
  32. [34]Alan Frieze and Michał Karoński. Introduction to random graphs. Cambridge University Press, 2016. ISBN 9781107118508. doi: 10.1017/CBO9781316339831. URL https://doi.org/10.1017/CBO9781316339831.
  33. [35]Zoltán Füredi and Imre Z. Ruzsa. Nearly subadditive sequences. Acta Mathematica Hungarica, 161(2):401–411, 2020. doi: 10.1007/s10474-020-01071-0. URL https://doi.org/10.1007/s10474-020-01071-0.
  34. [36]Andreas Goerdt. A threshold for unsatisfiability. Journal of Computer and System Sciences, 53(3):469–486, 1996. doi: 10.1006/jcss.1996.0081. URL https://doi.org/10.1006/jcss.1996.0081.
  35. [37]Geoffrey Grimmett. Probability on Graphs: Random Processes on Graphs and Lattices, volume 8 of Institute of Mathematical Statistics Textbooks. Cambridge University Press, Cambridge, second edition, 2018. doi: 10.1017/9781108528986. URL https://doi.org/10.1017/9781108528986.
  36. [38]Francesco Guerra and Fabio Lucio Toninelli. The thermodynamic limit in mean field spin glass models. Communications in Mathematical Physics, 230(1):71–79, 2002. doi: 10.1007/s00220-002-0699-y. URL https://doi.org/10.1007/s00220-002-0699-y.
  37. [39]Bruce Hajek. Hitting-time and occupation-time bounds implied by drift analysis with applications. Advances in Applied Probability, 14(3):502–525, 1982. doi: 10.2307/1426671. URL https://doi.org/10.2307/1426671.
  38. [40]Svante Janson, Tomasz Łuczak, and Andrzej Ruciński. Random graphs. John Wiley & Sons, 2000. ISBN 9780471175414. doi: 10.1002/9781118032718. URL https://doi.org/10.1002/9781118032718.
  39. [41]Alexis C. Kaporis, Lefteris M. Kirousis, and Yannis C. Stamatiou. A note on the non-colorability threshold of a random graph. The Electronic Journal of Combinatorics, 7(1):R29, 2000. doi: 10.37236/1507. URL https://doi.org/10.37236/1507.
  40. [42]Florent Krzakala, Andrea Pagnani, and Martin Weigt. Threshold values, stability analysis, and high-q asymptotics for the coloring problem on random graphs. Physical Review E, 70:046705, 2004. doi: 10.1103/PhysRevE.70.046705. URL https://doi.org/10.1103/PhysRevE.70.046705.
  41. [43]Florent Krzakala, Andrea Montanari, Federico Ricci-Tersenghi, Guilhem Semerjian, and Lenka Zdeborová. Gibbs states and the set of solutions of random constraint satisfaction problems. Proceedings of the National Academy of Sciences, 104(25):10318–10323, 2007. doi: 10.1073/pnas.0703685104. URL https://pmc.ncbi.nlm.nih.gov/articles/PMC1965511/.DOI
  42. [44]Günter Last and Mathew Penrose. Lectures on the Poisson process, volume 7 of Institute of Mathematical Statistics Textbooks. Cambridge University Press, 2018. ISBN 9781107088016. doi: 10.1017/9781316104477. URL https://doi.org/10.1017/9781316104477. First published 2018; Cambridge online publication October 26, 2017.
  43. [45]Joseph Mecke. Stationäre zufällige Maße auf lokalkompakten Abelschen Gruppen. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, 9(1):36–58, 1967. doi: 10.1007/BF00535466. URL https://doi.org/10.1007/BF00535466.
  44. [46]Michael Molloy. The freezing threshold for k-colourings of a random graph. Journal of the ACM, 65(2):7:1–7:62, 2018. doi: 10.1145/3034781. URL https://www.cs.toronto.edu/~molloy/webpapers/frozencol15.pdf. A shorter version appeared in STOC 2012, pp. 921–930.DOI
  45. [47]Rémi Monasson and Riccardo Zecchina. Entropy of the K-satisfiability problem. Physical Review Letters, 76(21):3881–3885, 1996. doi: 10.1103/PhysRevLett.76.3881. URL https://doi.org/10.1103/PhysRevLett.76.3881.
  46. [48]Rémi Monasson, Riccardo Zecchina, Scott Kirkpatrick, Bart Selman, and Lidrør Troyansky. Determining computational complexity from characteristic ‘phase transitions’. Nature, 400:133–137, 1999. doi: 10.1038/22055. URL https://doi.org/10.1038/22055.
  47. [49]Roberto Mulet, Andrea Pagnani, Martin Weigt, and Riccardo Zecchina. Coloring random graphs. Physical Review Letters, 89:268701, 2002. doi: 10.1103/PhysRevLett.89.268701. URL https://doi.org/10.1103/PhysRevLett.89.268701.
  48. [50]OpenAI. A sharp threshold bound for monotone graph properties. OpenAI Math Release preprint, September 2026. URL https://github.com/openai/math/blob/7e f5c0cc5ca4b0e072b7a050fca09ab24bc6fa3a/preprints/A-Sharp-Threshold-Bound-for-Monotone-Graph-Properties-September-25-2026/paper.pdf. Unrefereed preprint; manuscript dated September 25, 2026; repository version 7ef5c0c.
  49. [51]OpenAI. A limiting satisfiability threshold for every fixed clause size. OpenAI Math Release preprint, September 2026. URL https://github.com/openai/math/blob/fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb/preprints/A-Limiting-Satisfiability-Threshold-for-Every-Fixed-Clause-Size-September-25-2026/article.pdf. Unrefereed preprint; manuscript dated September 25, 2026; repository version fd4aeeb.hub.valency.io/works/W_4fmh35kn
  50. [52]OpenAI. Linear variance of the random 3-SAT hitting time. OpenAI Math Release preprint, October 2026. URL https://github.com/openai/math/blob/fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb/preprints/Linear-Variance-of-the-Random-3-SAT-Hitting-Time-October-5-2026/linear-variance-of-the-random-3-sat-hitting-time.pdf. Unrefereed preprint; manuscript dated October 5, 2026; repository version fd4aeeb.hub.valency.io/works/W_abp63c58
  51. [53]OpenAI. Variance of the random k-SAT hitting time. OpenAI Math Release preprint, September 2026. URL https://github.com/openai/math/blob/fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb/preprints/Variance-of-the-Random-k-SAT-Hitting-Time-September-27-2026/article.pdf. Unrefereed preprint; manuscript dated September 27, 2026; repository version fd4aeeb.hub.valency.io/works/W_ygubr4aj
  52. [54]Dmitry Panchenko and Michel Talagrand. Bounds for diluted mean-fields spin glass models. Probability Theory and Related Fields, 130(3):319–336, 2004. doi: 10.1007/s00440-004-0342-2. URL https://doi.org/10.1007/s00440-004-0342-2.
  53. [55]Will Perkins. Searching for (sharp) thresholds in random structures: where are we now? Bulletin of the American Mathematical Society, 62(1):113–143, 2025. doi: 10.1090/bull/1857. URL https://doi.org/10.1090/bull/1857. Online publication October 30, 2024.
  54. [56]Boris Pittel and Gregory B. Sorkin. The satisfiability threshold for k-XORSAT. Combinatorics, Probability and Computing, 25(2):236–268, 2016. doi: 10.1017/S0963548315000097. URL https://doi.org/10.1017/S0963548315000097.
  55. [57]Boris Pittel and Ji-A Yeum. How frequently is a system of 2-linear Boolean equations solvable? The Electronic Journal of Combinatorics, 17(1):R92, 2010. doi: 10.37236/364. URL https://doi.org/10.37236/364.
  56. [58]Ronald C. Read. An introduction to chromatic polynomials. Journal of Combinatorial Theory, 4(1):52–71, 1968. doi: 10.1016/S0021-9800(68)80087-0. URL https://doi.org/10.1016/S0021-9800(68)80087-0.
  57. [59]Lucio Russo. An approximate zero-one law. Zeitschrift für Wahrscheinlichkeits theorie und Verwandte Gebiete, 61(1):129–139, 1982. doi: 10.1007/BF00537230. URL https: //doi.org/10.1007/BF00537230.DOI
  58. [60]Guilhem Semerjian. On the freezing of variables in random constraint satisfaction problems. Journal of Statistical Physics, 130(2):251–293, 2008. doi: 10.1007/s10955-007-9417-7. URL https://doi.org/10.1007/s10955-007-9417-7.
  59. [61]J. Michael Steele. An Efron–Stein inequality for nonsymmetric statistics. The Annals of Statistics, 14(2):753–758, 1986. doi: 10.1214/aos/1176349952. URL https://doi.org/10.1214/aos/1176349952.
  60. [62]David B. Wilson. On the critical exponents of random k-SAT. Random Structures & Algorithms, 21(2):182–195, 2002. doi: 10.1002/rsa.10050. URL https://doi.org/10.1002/rsa.10050.
  61. [63]Lenka Zdeborová and Florent Krzakala. Phase transitions in the coloring of random graphs. Physical Review E, 76:031131, 2007. doi: 10.1103/PhysRevE.76.031131. URL https://doi.org/10.1103/PhysRevE.76.031131.

Paper details

vlnc:W_nj4vfw7k
v1 · latestHistory (1)

published · Fresh — added to the Hub within the last 30 days

added ·

Usage

views · 7

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

CC BY 4.0

Original source

  • Mathematics

Not recorded for this paper · View statement →

Looking for related papers…
Contents