Abstract We show that the twin-width of every $n$ -vertex $d$ -regular graph is at most $n^{\frac{d-2}{2d-2}+o(1)}$ for any fixed integer $d \geq 2$ 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.

Kevin Hendrey

Sergey Norin

Raphael Steiner

Jérémie Turcotte

Combinatorics Probability Computing

双月刊出版的《组合数学、概率与计算》致力于组合数学、概率论和理论计算机科学三个领域。涵盖的主题包括经典和代数图论、极值集理论、拟阵理论、概率方法和随机组合结构；随机组合结构的组合概率和极限定理；算法理论（包括复杂性理论）、随机算法、算法概率分析、计算学习理论和优化。

"Combinatorics Probability and Computing" is a bi-monthly journal dedicated to the fields of combinatorial mathematics, probability theory, and theoretical computer science. The topics covered include classical and algebraic graph theory, extremal set theory, matroid theory, probabilistic methods, and random combinatorial structures; combinatorial probabilities and limit theorems of random combinatorial structures; algorithm theory (including complexity theory), randomized algorithms, probabilistic analysis of algorithms, computational learning theory, and optimization.

《Combinatorics Probability and Computing》是一本双月刊，专注于组合数学、概率论和理论计算机科学三个领域。期刊涵盖的主题包括经典和代数图论、极值集理论、拟阵理论、概率方法和随机组合结构；随机组合结构的组合概率和极限定理；算法理论（包括复杂性理论）、随机算法、算法概率分析、计算学习理论和优化。

Category	Quartile
数学	4
数学, 统计学与概率论	3
数学, 计算机理论方法	4
数学, 数学	4

Twin-width of sparse random graphs

ivySCI AI Smartly Parses PDF, Answers Researchers' Questions, and Helps You Understand Papers in Seconds

Journal Info

Category	Quartile
STATISTICS & PROBABILITY	3