Sergey Norin

activity

20232026

most citedTwin-width of sparse random graphs

2 citations · 2 across the 6 of their papers we have counts for

collaborators

Showing 2023Show all

2 papers · 1 filter

math.CO2023★ 2 cited

Twin-width of sparse random graphs

Kevin Hendrey, Sergey Norin, Raphael Steiner +1

We show that the twin-width of every $n$ -vertex $d$ -regular graph is at most $n^{\frac{d - 2}{2 d - 2} + o (1)}$ and that almost all $d$ -regular graphs attain this bound. More generally, w…

math.CO2023

On an induced version of Menger's theorem

Kevin Hendrey, Sergey Norin, Raphael Steiner +1

We prove Menger-type results in which the obtained paths are pairwise non-adjacent, both for graphs of bounded maximum degree and, more generally, for graphs excluding a topologica…