On the number of arcs in primitive digraphs with large exponents (Q1870076): Difference between revisions

A digraph \(G\) is primitive if there is a walk of length exactly \(k\) from each vertex \(u\) to each vertex \(v\) (possibly \(u\)) for a positive integer \(k\). The smallest such \(k\) is \(\exp(G)\). Suppose \(f(n,r)\) is the maximum number of arcs in a primitive digraph with \(n\) vertices and \(\exp(G)\geq r^2 n^2\) where \(r\) satisfies \(0< r< 1\). The authors establish the property that \(f(n,r)/n^2\) is asymptotically \((1- r)^2/3\) whenever \(r\geq \sqrt{2}/2\).