Report Number: CS-TR-75-504
Institution: Stanford University, Department of Computer Science
Title: On sparse graphs with dense long paths.
Author: Erdoes, Paul
Author: Graham, Ronald L.
Author: Szemeredi, Endre
Date: September 1975
Abstract: 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 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 porperty P(m,n) can have. The problem is to estimate f(m,n). For the remainder of the paper, we shall restrict ourselves to the case m = n. We shall prove (1) $c_1$n log n/log log n < f(n,n) < $c_2$n log n (where $c_1$,$c_2$,..., will hereafter denote suitable positive constaints). In fact, the graph we construct in order to establish the upper bound on f(n,n) in (1) will have just $c_3$n vertices. In this case the upper bound in (1) is essentially best possible since it will also be shown that for $c_4$ sufficiently large, every graph on $c_4$n vertices having property P(n,n) must have at least $c_5$n log n edges.
http://i.stanford.edu/pub/cstr/reports/cs/tr/75/504/CS-TR-75-504.pdf