On sparse graphs with dense long paths (Q1226502)

An acyclic directed graph \(G\) is said to have property \(P(m,n)\) if for any set \(X\) of \(m\) vertices of \(G\), there is a directed path of length \(n\) in \(G\) which does not intersect \(X\). Let \(f(m,n)\) denote the minimum number of edges a graph with property \(P(m,n)\) can have. (Hereafter, \(c_1,c_2, \ldots\) denote suitable positive constants.) Theorem. \(c_1n \log n/ \log \log n<f(n,n)<c_2n \log n\). The graph constructed in order to establish the upper bound on \(f(n,n)\) has \(c_3n\) vertices. In this case, the upper bound is essentially best possible since it is shown that for \(c_4\) sufficiently large, if a graph on \(c_4n\) vertices has property \(P(n,n)\) then it must have at least \(c_5n \log n\) edges.