Arboricity and spanning-tree packing in random graphs

作者：Gao Pu; Perez-Gimenez Xavier; Sato Cristiane M.^*

来源：Random Structures and Algorithms, 2018, 52(3): 495-535.

DOI：10.1002/rsa.20743

• arboricity
• load balancing
• random graphs
• spanning tree packing

We study the arboricity A and the maximum number T of edge-disjoint spanning trees of the classical random graph g(n,p). For all p(n) is an element of [0,1], we show that, with high probability, T is precisely the minimum delta and [m/ (n - 1)], where delta is the minimum degree of the graph and m denotes the number of edges. Moreover, we explicitly determine a sharp threshold value for p such that the following holds. above this threshold, T equals floor [m/ (n - 1)] and A equals [m/ (n -1 )]. Below this threshold, T equals delta, and we give a two-value concentration result for the arboricity A in that range. Finally, we include a stronger version of these results in the context of the random graph process where the edges are randomly added one by one. A direct application of our result gives a sharp threshold for the maximum load being at most k in the two-choice load balancing problem, where k -> infinity.

• 出版日期2018-5