Diameter and long paths in critical digraph

MaRDI QIDQ6435800zbMATH OpenFDO

Authors Arthur Blanc-Renaudie

Publication date 8 May 2023

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Geometric probability and stochastic geometry (60D05) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Abstract: We study the random directed graph $vecG(n,p)$ in which each of the $n(n-1)$ possible directed edges are present with probability $p$. We show that in the critical window the longest self avoiding oriented paths in $vecG(n,p)$ have length $O_{mathbbP}(n^{1/3})$ so $vecG(n,p)$ has diameter $O_{mathbbP}(n^{1/3})$.

This page was built for publication: Diameter and long paths in critical digraph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6435800)