On Sparse Graphs with Dense Long Paths.

The following problem was raised by H.-J. Stoss in connection with certain questions related to the complexity of Boolean functions. An acyclic directed graph G is said to have property p m,n if for any set of X of m vertices of G , there is a directed path of length n in G which does not intersect X. Let fm,n denote the minimum number of edges a graph with property pm,n can have.