Arboricity and spanning‐tree packing in random graphs. Issue 3 (19th December 2017) - Gao, Pu; Pérez‐Giménez, Xavier; Sato, Cristiane M.
Abstract: 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 ) ∈ [ 0, 1 ], we show that, with high probability, T is precisely the minimum of δ and ⌊ m / ( n − 1 ) ⌋, where δ 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 ⌊ m / ( n − 1 ) ⌋ and A equals ⌈ m / ( n − 1 ) ⌉ . Below this threshold, T equals δ, 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 → ∞ .