×

Embedding graphs with bounded degree in sparse pseudorandom graphs. (English) Zbl 1055.05138

A quasi-random graph sequence \(G(n)\) is defined consisting of sparse graphs of increasing order \(n\). Conditions are given to find in \(G(n)\) the asymptotic number of labeled copies of a fixed triangle-free graph \(H\).

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C10 Planar graphs; geometric and topological aspects of graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon, N., Eigenvalues and expanders, Combinatorica, 6, 83-96 (1986) · Zbl 0661.05053 · doi:10.1007/BF02579166
[2] Alon, N., Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory, Combinatorica, 6, 207-219 (1986) · Zbl 0625.05026 · doi:10.1007/BF02579382
[3] N. Alon,Explicit Ramsey graphs and orthonormal labelings, European Journal of Combinatorics1 (1994), Research Paper 12, approx. 8 pp. (electronic). · Zbl 0814.05056
[4] Alon, N.; Chung, F. R. K., Explicit construction of linear sized tolerant networks, Discrete Mathematics, 72, 15-19 (1988) · Zbl 0657.05068 · doi:10.1016/0012-365X(88)90189-6
[5] Alon, N.; Duke, R. A.; Lefmann, H.; Rödl, V.; Yuster, R., The algorithmic aspects of the regularity lemma, Journal of Algorithms, 16, 80-109 (1994) · Zbl 0794.05119 · doi:10.1006/jagm.1994.1005
[6] Alon, N.; Spencer, J. H., The Probabilistic Method (2000), New York: Wiley Interscience, New York · Zbl 0996.05001
[7] Chung, F. R. K.; Graham, R. L., Quasi-random tournaments, Journal of Graph Theory, 15, 173-198 (1991) · Zbl 0728.05025 · doi:10.1002/jgt.3190150206
[8] Chung, F. R. K.; Graham, R. L., Sparse quasi-random graphs, Combinatorica, 22, 217-244 (2002) · Zbl 0997.05090 · doi:10.1007/s004930200010
[9] Chung, F. R. K.; Graham, R. L.; Wilson, R. M., Quasi-random graphs, Combinatorica, 9, 345-362 (1989) · Zbl 0715.05057 · doi:10.1007/BF02125347
[10] Duke, R. A.; Lefmann, H.; Rödl, V., A fast approximation algorithm for computing the frequencies of subgraphs in a given graph, SIAM Journal on Computing, 24, 598-620 (1995) · Zbl 0831.68049 · doi:10.1137/S0097539793247634
[11] Frankl, P.; Rödl, V.; Wilson, R. M., The number of submatrices of a given type in a Hadamard matrix and related results, Journal of Combinatorial Theory, Series B, 44, 317-328 (1988) · Zbl 0658.05015 · doi:10.1016/0095-8956(88)90040-8
[12] Janson, S.; Łuczak, T.; Ruciński, A., Random Graphs (2000), New York: Wiley-Interscience, New York · Zbl 0968.05003
[13] Kohayakawa, Y.; Cucker, F.; Shub, M., Szemerédi’s regularity lemma for sparse graphs, Foundations of Computational Mathematics (Berlin, Heidelberg), 216-230 (1997), Berlin: Springer-Verlag, Berlin · Zbl 0868.05042
[14] Kohayakawa, Y.; Rödl, V., Regular pairs in sparse random graphs I, Random Structures and Algorithms, 22, 359-434 (2003) · Zbl 1022.05076 · doi:10.1002/rsa.10081
[15] Y. Kohayakawa, V. Rödl and M. Schacht,The Turán theorem for random graphs, Combinatorics, Probability and Computing, to appear. · Zbl 1048.05075
[16] Kohayakawa, Y.; Rödl, V.; Thoma, L., An optimal algorithm for checking regularity, SIAM Journal on Computing, 32, 1210-1235 (2003) · Zbl 1025.05056 · doi:10.1137/S0097539702408223
[17] T. Łuczak, personal communication, 2000.
[18] Rödl, V., On universality of graphs with uniformly distributed edges, Discrete Mathematics, 59, 125-134 (1986) · Zbl 0619.05035 · doi:10.1016/0012-365X(86)90076-2
[19] Rödl, V.; Ruciński, A., Threshold functions for Ramsey properties, Journal of the American Mathematical Society, 8, 917-942 (1995) · Zbl 0846.05079 · doi:10.2307/2152833
[20] Simonovits, M.; Sós, V. T., Hereditarily extended properties, quasi-random graphs and not necessarily induced subgraphs, Combinatorica, 17, 577-596 (1997) · Zbl 0906.05066 · doi:10.1007/BF01195005
[21] Thomason, A. G., Pseudorandom graphs, Random Graphs ′85 (Poznań, 1985), 307-331 (1987), Amsterdam: North-Holland, Amsterdam · Zbl 0632.05045
[22] Thomason, A. G.; Whitehead, C., Random graphs, strongly regular graphs and pseudorandom graphs, Surveys in Combinatorics 1987, 173-195 (1987), Cambridge-New York: Cambridge University Press, Cambridge-New York · Zbl 0672.05068
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.