Twin-width of sparse random graphs

DOI10.1017/S0963548324000439MaRDI QIDQ6879997zbMATH OpenFDO

Authors Kevin Hendrey, Serguei Norine, Raphael Steiner, Jérémie Turcotte

Publication date 29 December 2025

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/S0963548324000439

zbMATH Keywords

random graphstwin-width

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Graph operations (line graphs, products, etc.) (05C76) Random graphs (graph-theoretic aspects) (05C80)

Review text

The paper studies the twin-width of sparse random graphs. Suppose that \(d\ge2\) is an integer. It is shown that the twin-width \(\operatorname{tww}(G)\le n^{\frac{d-2}{2d-2}+o(1)}\) for every \(d\)-regular graph \(G\) of order \(n\). The inequality holds with equality for almost all \(d\)-regular graphs of order \(n\). It is also shown that the twin-width is typically a polynomial in the number of vertices for the sparse random graph model \(G(n,c/n)\) for \(1<c\le\frac{1}{12}\ln n\), where the exponent is governed by the maximum average degree of the graph.

Cites work

• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• Bounds for the twin-width of graphs
• scientific article; zbMATH DE number 1246230 (Why is no real title available?)
• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• Performance of global load balancing by local adjustment
• The densest subgraph problem in sparse random graphs
• Twin-width II: small classes
• Twin-width of random graphs
• Twin-width. I: Tractable FO model checking

Cited in

(1)

• Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)

This page was built for publication: Twin-width of sparse random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6879997)