Turán's extremal problem in random graphs: Forbidding odd cycles
Tóm tắt
For 0<γ≤1 and graphsG andH, we writeG→γH if any γ-proportion of the edges ofG span at least one copy ofH inG. As customary, we writeC
k for a cycle of lengthk. We show that, for every fixed integerl≥1 and real η>0, there exists a real constantC=C(l, η), such that almost every random graphG
n, p withp=p(n)≥Cn
−1+1/2l
satisfiesG
n,p→1/2+η
C
2l+1. In particular, for any fixedl≥1 and η>0, this result implies the existence of very sparse graphsG withG
→1/2+η
C
2l+1.
Tài liệu tham khảo
L. Babai, M. Simonovits, andJ. H. Spencer: Extremal subgraphs of random graphs,J. Graph Theory,14 (1990), 599–622.
B. Bollobás:Extremal Graph Theory, Academic Press, London, 1978.
B. Bollobás:Random Graphs, Academic Press, London, 1985.
P. Erdős andA. H. Stone: On the structure of linear graphs.Bull. Amer. Math. Soc.,52 (1946), 1089–1091.
P. Frankl, andV. Rödl: Large triangle-free subgraphs in graphs withoutK 4,Graphs and Combinatorics,2 (1986), 135–144.
Z. Füredi: Random Ramsey graphs for the four-cycle,Discrete Mathematics,126 (1994), 407–410.
P. E. Haxell, Y. Kohayakawa, andT. Luczak: The induced size-Ramsey number of cycles,Combinatorics, Probability and Computing (to appear).
P. E. Haxell, Y. Kohayakawa, andT. Luczak: Turán's extremal problem in random graphs: forbidding even cycles.J. Combin. Theory (Series B),64 (1995), 273–287.
W. Hoeffding: Probability inequalities for sums of bounded random variables,Jour. Amer. Statistical Assoc.,58 (1963), 13–30.
Y. Kohayakawa: The regularity lemma of Szemerédi for sparse graphs, manuscript, 1993.
T. Luczak, A. Ruciński, andB. Voigt: Ramsey properties of random graphs.J. Combin. Theory (Series B),56 (1992), 55–68.
C. J. H. McDiarmid:On the method of bounded differences, Surveys in Combinatorics, 1989, London Mathematical Society Lecture Notes Series 141 (Siemons, J., ed.), Cambridge University Press, Cambridge, 1989, 148–188.
V. Rödl: Personal communication, July 1993.
V. Rödl, andA. Ruciński: Lower bounds on probability thresholds for Ramsey properties, Combinatorics-Paul Erdős is Eighty (Volume 1) (D. Miklós, V. T. Sós, T. Szőnyi, eds.), Bolyai Soc. Math. Studies, Budapest, 1993, 317–346.
V. Rödl, andA. Ruciński: Random graphs with monochromatic triangles in every edge colouring.Random Structures and Algorithms,5 (1994), 253–270.
V. Rődl, andA. Ruciński: Threshold functions for Ramsey properties,J. Amer. Math. Soc. (to appear).
E. Szemerédi: Regular partitions of graphs, Problèmes Combinatoires et Théorie des Graphes, Proc. Colloque Inter. CNRS (J.-C. Bermond, J.-C. Fournier, M. Las Vergnas, D. Sotteau, eds), CNRS, Paris, 1978, 399–401.