BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-75-504
       ENTRY:: August 23, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: On sparse graphs with dense long paths.
        TYPE:: Technical Report
      AUTHOR:: Erdoes, Paul
      AUTHOR:: Graham, Ronald L.
      AUTHOR:: Szemeredi, Endre
        DATE:: September 1975
       PAGES:: 15
    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.
       NOTES:: [Adminitrivia V1/Prg/19950823]
         END:: STAN//CS-TR-75-504