Twin-width of sparse random graphs

被引：0
|
作者：
Hendrey, Kevin [1 ]
Norin, Sergey [2 ]
Steiner, Raphael [3 ]
Turcotte, Jeremie [2 ]
机构：
[1] Monash Univ, Melbourne, Australia
[2] McGill Univ, Dept Math & Stat, Montreal, PQ, Canada
[3] Swiss Fed Inst Technol, Inst Theoret Comp Sci, Dept Comp Sci, Zurich, Switzerland
来源：
COMBINATORICS PROBABILITY AND COMPUTING | 2024年
关键词：
Twin-width; random graphs;
D O I：
10.1017/S0963548324000439
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We show that the twin-width of every n-vertex d-regular graph is at most n (d-2/ 2d-2 + o (1)) for any fixed integer d >= 2 and that almost all d-regular graphs attain this bound. More generally, we obtain bounds on the twin-width of sparse Erdos-Renyi and regular random graphs, complementing the bounds in the denser regime due to Ahn, Chakraborti, Hendrey, Kim, and Oum.
引用
收藏
页数：20
相关论文
共 50 条
  • [1] Twin-width of random graphs
    Ahn, Jungho
    Chakraborti, Debsoumya
    Hendrey, Kevin
    Kim, Donggyu
    Oum, Sang-il
    RANDOM STRUCTURES & ALGORITHMS, 2024, 65 (04) : 794 - 831
  • [2] BOUNDS FOR THE TWIN-WIDTH OF GRAPHS
    Ahn, Jungho
    Hendrey, Kevin
    Kim, Donggyu
    Oum, Sang-Il
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2022, 36 (03) : 2352 - 2366
  • [3] Twin-width of graphs on surfaces
    Král, Daniel
    Pekárková, Kristýna
    Štorgel, Kenny
    arXiv, 2023,
  • [4] Bounds on the Twin-Width of Product Graphs
    Pettersson, William
    Sylvester, John
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2023, 25 (01):
  • [5] Neighbourhood complexity of graphs of bounded twin-width
    Bonnet, Edouard
    Foucaud, Florent
    Lehtila, Tuomo
    Parreau, Aline
    EUROPEAN JOURNAL OF COMBINATORICS, 2024, 115
  • [6] Twin-Width IV: Ordered Graphs and Matrices
    Bonnet, Edouard
    Giocanti, Ugo
    de Mendez, Patrice Ossona
    Simon, Pierre
    Thomasse, Stephan
    Torunczyk, Szymon
    JOURNAL OF THE ACM, 2024, 71 (03)
  • [7] Twin-Width IV: Ordered Graphs and Matrices*
    Bonnet, Edouard
    Giocanti, Ugo
    de Mendez, Patrice Ossona
    Simon, Pierre
    Thomasse, Stephan
    Torunczyk, Szymon
    PROCEEDINGS OF THE 54TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '22), 2022, : 924 - 937
  • [8] Neighbourhood complexity of graphs of bounded twin-width
    Bonnet, Édouard
    Foucaud, Florent
    Lehtilä, Tuomo
    Parreau, Aline
    arXiv, 2023,
  • [9] Distal combinatorial tools for graphs of bounded twin-width
    Przybyszewski, Wojciech
    2023 38TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, LICS, 2023,
  • [10] TWIN-WIDTH AND PERMUTATIONS
    Bonnet, Edouard
    Nesetril, Jaroslav
    De Mendez, Patrice Ossona
    Siebertz, Sebastian
    Thomasse, Stephan
    LOGICAL METHODS IN COMPUTER SCIENCE, 2024, 20 (03) : 1 - 25
12345