Hitting times for arc-disjoint arborescences in random digraph processes

Author(s)

Collares, Mauricio ; Kohayakawa, Yoshiharu ; Martins, Taisa ; Parente, Roberto ; Souza, Victor ; Ferreira, CE ; Lee, O ; Miyazawa, FK

• Document type: Journal article
• Source: PROCEEDINGS OF THE XI LATIN AND AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM; v. 195, p. 9-pg., 2021-01-01.

Abstract

In this work, we study hitting times for the appearance of a spanning structure in the Erdos-Renyi random directed graph processes. Namely, we are concerned with the appearance of an arborescence, a spanning digraph in which, for a vertex u called the root and any other vertex v, there is exactly one directed path from u to v. Let D(n, 0), D(n, 1),..., D(n, n(n 1)) be the random digraph process where for every m is an element of {0,, n(n 1)}, D(n, m) is a digraph with vertex set {1,..., n}; D(n, 0) has no arcs and, for 1 <= m <= n(n 1), the digraph D(n, m) is obtained by adding an arc to D(n, m - 1), chosen uniformly at random among the not present arcs. In this paper we determine the hitting time for the existence of k arc -disjoint arborescences when k = k(n) << root log n (C) 2021 The Authors. Published by Elsevier B.V. (AU)

• FAPESP's process: 18/04876-1 - Ramsey theory, structural graph theory and applications in Bioinformatics
• Grantee: Guilherme Oliveira Mota
• Support Opportunities: Research Grants - Young Investigators Grants