2024/05/03 by Jiyun Park, Park, Jiyun · 1 citation
Mathematics · Physics and Astronomy · #05C35 #05C80 #60C05 #60F10 #Combinatorics (math.CO) #Complex Network Analysis Techniques #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.2405.01980
openalex publication_date 2024/05/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The upper tail problem in a sparse Erdős-Rényi graph asks for the probability that the number of copies of some fixed subgraph exceeds its expected value by a constant factor. We study the analogous problem for oriented subgraphs in directed random graphs. By adapting the proof of Cook, Dembo, and Pham, we reduce this upper tail problem to the asymptotic of a certain variational problem over edge weighted directed graphs. We give upper and lower bounds for the solution to the corresponding variational problem, which differ by a constant factor of at most 2. We provide a host of subgraphs where the upper and lower bounds coincide, giving the solution to the upper tail problem. Examples of such digraphs include triangles, stars, directed k-cycles, and balanced digraphs.