RAMSEY PROPERTIES OF ORIENTATIONS OF GRAPHS

A classical result of Rodl (in Graphs, Hypergraphs and Block Systems, 1976, pp. 211 to 220) says that for any acyclic digraph D there is a graph G = G(D) such that every acyclic orientation of G contains an induced copy of D. A recent result of Rodl and Winkler (SIAM J. Discrete Math., 2: 402-406. 1989) implies that there is such a graph G of order O(n3(log n)2), where n = Absolute value of D is the order of D. Here we show by probabilistic means that almost every graph G(n) of order [(4/9)n2n/2] has the property that every acyclic orientation of G(n) contains an induced copy of every acyclic digraph on n vertices. We also show that the order of any such graph G(n) has to be greater than (1/10)n2n/2. Thus our results are essentially best possible. Moreover, we show that there are Paley graphs of order O(n24n) having the property above. We also consider some problems raised by Cochand and Duchet (Irregularities of Partitions, Springer-Verlag, Berlin, 1989. pp. 39-46.) on related topics. (C) 1993 John Wiley & Sons, Inc.