Arboricity and spanning‐tree packing in random graphs. Issue 3 (19th December 2017)

• Record Type: Journal Article
• Authors: Gao, Pu; Pérez‐Giménez, Xavier; Sato, Cristiane M.
• Is Part Of: Random structures & algorithms. Volume 52:Issue 3(2018)
• Page Start: 495
• Page End: 535
• Publication Date: 2017-12-19
• Subjects: arboricity -- load balancing -- random graphs -- spanning tree packing; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20743
• Languages: English
• ISSNs: 1042-9832

Abstract

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