Twin-width of sparse random graphs

2023/12/06 by Hendrey, Kevin, Norin, Sergey, Steiner, Raphael +1 · 1 citation
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2312.03688

Abstract

We show that the twin-width of every n-vertex d-regular graph is at most n^{(d-2)/(2d-2)+o(1)} and that almost all d-regular graphs attain this bound. More generally, we obtain bounds on the twin-width of sparse Erdős-Renyi and regular random graphs, complementing the bounds in the denser regime due to Ahn, Chakraborti, Hendrey, Kim and Oum.

Cited by

• Temporal Exploration of Random Spanning Tree Models

Related

• Sparse Graphs of Twin-width 2 Have Bounded Tree-width
• On the twin-width of near-regular graphs
• Twin-width II: small classes
• Computation of twin-width of graphs
• Deciding twin-width at most 4 is NP-complete