Ramsey properties of orientations of graphs
作者： G. R. Brightwell , Y. Kohayakawa
关键词: Combinatorics 、 Graph 、 Discrete mathematics 、 Gallai–Hasse–Roy–Vitaver theorem 、 Binary logarithm 、 Paley graph 、 Digraph 、 Mathematics 、 Acyclic orientation
摘要: 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 every orientation contains an induced copy D. recent Winkler (SIAM J. Discrete Math., 2: 402–406, 1989) implies order O(n3 (log n)2), where n |D| the Here we show by probabilistic means almost Gn [(4/9)n2n/2] has property on vertices. We also be greater than (1/10)n2n/2. Thus our results are essentially best possible. Moreover, Paley graphs O(n24n) having above. consider some problems raised Cochand Duchet (Irregularities Partitions, Springer-Verlag, Berlin, 1989, 39–46.) related topics. © 1993 John Wiley & Sons, Inc.
sci-hub.se 参考文章(12)
L. J. Mordell, G. H. Hardy, E. M. Wright, An Introduction to the Theory of Numbers The Mathematical Gazette. ,vol. 23, pp. 174- ,(1939) , 10.2307/3607021
Colin McDiarmid, Surveys in Combinatorics, 1989: On the method of bounded differences Cambridge University Press. pp. 148- 188 ,(1989) , 10.1017/CBO9781107359949.008
M. Cochand, P. Duchet, A Few Remarks on Orientation of Graphs and Ramsey Theory Springer, Berlin, Heidelberg. pp. 39- 46 ,(1989) , 10.1007/978-3-642-61324-1_3
Michael H. Albert, Alan M. Frieze, Random graph orders Order. ,vol. 6, pp. 19- 30 ,(1989) , 10.1007/BF00341633
Fan R. K. Chung, Universal graphs and induced-universal graphs Journal of Graph Theory. ,vol. 14, pp. 443- 454 ,(1990) , 10.1002/JGT.3190140408
Jaroslav Nešetřil, Vojtěch R{ödl, On a probabilistic graph-theoretical method Proceedings of the American Mathematical Society. ,vol. 72, pp. 417- 421 ,(1978) , 10.1090/S0002-9939-1978-0507350-7
Béla Bollobás, Andrew Thomason, Graphs which Contain all Small Graphs European Journal of Combinatorics. ,vol. 2, pp. 13- 15 ,(1981) , 10.1016/S0195-6698(81)80015-7
Noga Alon, Bela Bollobas, Graham Brightwell, Svante Janson, LINEAR EXTENSIONS OF A RANDOM PARTIAL ORDER Annals of Applied Probability. ,vol. 4, pp. 108- 123 ,(1994) , 10.1214/AOAP/1177005202
Vojtech Rödl, Peter Winkler, A Ramsey-type theorem for orderings of a graph SIAM Journal on Discrete Mathematics. ,vol. 2, pp. 402- 406 ,(1989) , 10.1137/0402035
B. Bollobás, The chromatic number of random graphs Combinatorica. ,vol. 8, pp. 49- 55 ,(1988) , 10.1007/BF02122551