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.