Bounds for the Twin-Width of Graphs

Bonnet et al. J. ACM, 69 (2022), 3 introduced the twin-width of a graph. We show that the twin-width of an n-vertex graph is less than (n+n n+n+2 n) /2, and the twin-width of an m-edge graph for a positive m is less than 3m+ m^1/4 m / (4 3^1/4) + 3m^1/4 / 2. Conference graphs of order n (when such graphs exist) have twin-width at least (n-1) /2, and we show that Paley graphs achieve this lower bound. We also show that the twin-width of the Erdös--Rényi random graph G (n, p) with 1/n p 1/2 is larger than 2p (1-p) n - (22+) p (1-p) n n asymptotically almost surely for any positive. Last, we calculate the twin-width of random graphs G (n, p) with p c/n for a constant c<1, determining the thresholds at which the twin-width jumps from 0 to 1 and from 1 to 2.