Open AccessUniversality of Random Graphs
Author(s) -
Domingos Dellamonica,
Yoshiharu Kohayakawa,
Vojtěch Rödl,
Andrzej Ruciński
Publication year - 2012
Publication title -
siam journal on discrete mathematics
Language(s) - English
Resource type - Book series
SCImago Journal Rank - 0.843
H-Index - 66
eISSN - 1095-7146
pISSN - 0895-4801
ISBN - 978-0-89871-698-6
DOI - 10.1137/10079882x
Subject(s) - mathematics , combinatorics , bipartite graph , bounded function , discrete mathematics , random graph , embedding , degree (music) , random regular graph , expander graph , chordal graph , graph , 1 planar graph , mathematical analysis , physics , artificial intelligence , computer science , acoustics
We prove that asymptotically (as n -> infinity) almost all graphs with n vertices and C(d)n(2-1/2d) log(1/d) n edges are universal with respect to the family of all graphs with maximum degree bounded by d. Moreover, we provide an efficient deterministic embedding algorithm for finding copies of bounded degree graphs in graphs satisfying certain pseudorandom properties. We also prove a counterpart result for random bipartite graphs, where the threshold number of edges is even smaller but the embedding is randomized.CAPESNSF [DMS080070]Charles University, PragueFAPESP [FAPESP 2003/09925-5]CNPq [308509/2007-2, 485671/2007-7, 486124/2007-0]Polish Ministry of Higher Education [N201036 32/2546
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom