Wiley: Random Structures & Algorithms: Table of Contents

On the Chromatic Number of Random Triangle‐Free Graphs

Clayton Mizgerd, Will Perkins, Yuzhou Wang — Sat, 06 Jun 2026 01:13:27 -0700

ABSTRACT

We study the chromatic number of typical triangle-free graphs with Θn3/2(logn)1/2$$ \Theta \left({n}^{3/2}{\left(\log n\right)}^{1/2}\right) $$ edges and establish the width of the scaling window for the transitions from χ=3$$ \chi =3 $$ to χ=4$$ \chi =4 $$ and from χ=4$$ \chi =4 $$ to χ=5$$ \chi =5 $$. The transition from 3- to 4-colorability has scaling window of width Θ(n4/3(logn)−1/3)$$ \Theta \left({n}^{4/3}{\left(\log n\right)}^{-1/3}\right) $$. To prove this, we show a high probability equivalence of the 3-colorability of a random triangle-free graph at this density and the satisfiability of an instance of bipartite random 2-SAT, for which we establish the width of the scaling window following the techniques of Bollobás, Borgs, Chayes, Kim, and Wilson. The transition from 4- to 5-colorability has scaling window of width Θ(n3/2(logn)−1/2)$$ \Theta \left({n}^{3/2}{\left(\log n\right)}^{-1/2}\right) $$. To prove this, we show a high probability equivalence of the 4-colorability of a random triangle-free graph at this density and the simultaneous 2-colorability of two independent Erdős–Rényi random graphs. For this transition, we also establish the limiting probability of 4-colorability inside the scaling window.

A Unimodular Random Graph With Large Upper Growth and No Growth

Péter Mester, Ádám Timár — Fri, 29 May 2026 19:30:36 -0700

ABSTRACT

We construct a unimodular random rooted graph with maximal degree d≥3$$ d\ge 3 $$ and upper growth rate d−1$$ d-1 $$, which does not have a growth rate. Abért, Fraczyk and Hayes showed that for a unimodular random tree, if the upper growth rate is at least d−1$$ \sqrt{d-1} $$, then the growth rate exists, and asked with some scepticism if this may hold for more general graphs. Our construction shows that the answer is negative. We also provide a non-hyperfinite example of a unimodular random graph with no growth rate. This may be of interest in light of a conjecture of Abért that unimodular random Riemannian surfaces of bounded negative curvature always have growth.

Issue Information

Fri, 29 May 2026 04:51:04 -0700

Random Structures &Algorithms, Volume 68, Issue 4, July 2026.