zbMATH — the first resource for mathematics

Hereditarily extended properties, quasi-random graphs and not necessarily induced subgraphs. (English) Zbl 0906.05066
The work can be considered as continuation of F. R. K. Chung, R. L. Graham and R. M. Wilson [Combinatorica 9, No. 4, 345-362 (1989; Zbl 0715.05057)] on quasi-random properties of graphs. A \(G_n\) sequence of graphs is quasi-random if it exhibits some behavior of random graph properties asymptotically, and it turns out that a number of equivalent properties ensure this. Informally these assumtions can be summerized as \(G_n\) contains about the same number of subgraphs as the appropriate \(G_{n, p}\) does. However, assumptions on certain subgraphs do not imply quasi randomness, such as the subgraphs having 3 vertices, the odd cycles, or the cutsets of size \(\lfloor n/2 \rfloor\), where \(n\) is the number of vertices. The main idea of the paper is that the properties above still imply the quasi randomness of \(G_n\) if one imposes them not only on the members of \(G_n\) but on the induced subgraphs also. The proofs heavily use the so-called Szemerédi partitions and the celebrated regularity lemma.

05C80 Random graphs (graph-theoretic aspects)
05C99 Graph theory
Full Text: DOI
[1] B. Bollob?s:Random Graphs, Academic Press, 1985.
[2] F. R. K. Chung, R. L. Graham andR. M. Wilson: Quasi-random graphs,Combinatorica,9 (4), (1989), 345-362. · Zbl 0715.05057
[3] F. R. K. Chung, R. Graham andR. L. Graham: Quasi-random hypergraphs,Random Structures and Algorithms,1 (1990), 105-124. · Zbl 0708.05044
[4] F. R. K. Chung: Regularity lemmas for hypergraphs and quasi-randomness,Random Structures and Algorithms, Vol.2 (2) (1991), 241-252. · Zbl 0756.05081
[5] F. R. K. Chung andR. L. Graham: Quasi-random set systems,Journal of the American Math. Society,4 (1) January, (1991), 151-196. · Zbl 0761.05072
[6] F. R. K. Chung andR. L. Graham: Maximum cuts and quasi-random graphs,in Random Graphs, (Poznan Conf, 1989) Wiley-Intersci, Publ. vol 2, 23-33. · Zbl 0823.05051
[7] F. R. K. Chung andR. L. Graham: On hypergraphs having evenly distributed subhypergraphs, (in the Proc. Conf. Marseille-Luminy, 1990) Discrete Mathematics,111 (1-3) (1993), 125-129. · Zbl 0785.05070
[8] M. Dyer andA. Frieze: Computing the volume of convex bodies: a case where randomness provably helps, inProbabilistic Combinatorics and Its Applications (ed. B?la Bollob?s), Proceedings of Symposia in Applied Mathematics, Vol. 44 (1992), 123-170.
[9] P. Frankl, V. R?dl andR. M. Wilson: The number of submatrices of given type in an Hadamard matrix and related results,Journal of Combinatorial Theory, (B) 44 (3) (1988), 317-328. · Zbl 0658.05015
[10] A. N. Kolmogorov: Three approaches to the quantitative definition of information,Problems Inform. Transmition,1 (1965), 1-7.
[11] J. Koml?s, G. N. S?rk?zy andE. Szemer?di: Blow-up Lemma,Combinatorica,17 (1) (1997), 109-123. · Zbl 0880.05049
[12] J. Koml?s andM. Simonovits: Szemer?di Regularity lemma and its applications in Extremal Graph Theory, in:Paul Erd?s is 80, II. Bolyai J. Math. Soc. 2, (1996), 295-352.
[13] M. Simonovits andV. T. S?s: Szemer?di’s Partition and quasi-randomness,Random Structures and Algorithms,2 (1991), 1-10. · Zbl 0766.05080
[14] M. Simonovits andV. T. S?s: Hereditarily extended properties, quasi-random graphs and induced subgraphs, manuscript. · Zbl 0906.05066
[15] E. Szemer?di: On regular partitions of graphs,Problemes Combinatoires et Th?orie des Graphes (ed. J. Bermond et al.), CNRS Paris, 1978, 399-401.
[16] E. Szemer?di: On graphs containing no complete subgraphs with 4 vertices (in Hungarian)Mat. Lapok 23 (1972), 111-116.
[17] A. Thomason: Random graphs, strongly regular graphs and pseudo-random graphs, in:Surveys in Combinatorics, 1987 (Whitehead, ed.) LMS Lecture Notes Series 123, Cambridge Univ. Press, Cambridge, 1987, 173-196. · Zbl 0672.05068
[18] A. Thomason: Pseudo-random graphs, in:Proceedings of Random graphs, Poznan, 1985, (M. Karonski, ed.);Annals of Discrete Math.,33 (1987), 307-331.
[19] A. Thomason: A disproof of a theorem of Erd?s in Ramsey theory,J. London Math. Soc,39 (2) (1989), 246-255. · Zbl 0638.05037
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.