Arboricity and spanning‐tree packing in random graphs

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 → ∞ .