Quasi-random set systems
HTML articles powered by AMS MathViewer
- by F. R. K. Chung and R. L. Graham
- J. Amer. Math. Soc. 4 (1991), 151-196
- DOI: https://doi.org/10.1090/S0894-0347-1991-1077279-1
- PDF | Request permission
References
- L. Babai, N. Nisan, and M. Szégedy, Multi-party protocols and logspace-hard pseudorandom sequences, Proc. 21st Sympos. Theory of Computing, ACM, 1989, pp. 1-11.
- Claude Berge, Hypergraphs, North-Holland Mathematical Library, vol. 45, North-Holland Publishing Co., Amsterdam, 1989. Combinatorics of finite sets; Translated from the French. MR 1013569
- Béla Bollobás, Random graphs, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London, 1985. MR 809996
- Béla Bollobás, Graph theory, Graduate Texts in Mathematics, vol. 63, Springer-Verlag, New York-Berlin, 1979. An introductory course. MR 536131
- Béla Bollobás and Andrew Thomason, Graphs which contain all small graphs, European J. Combin. 2 (1981), no. 1, 13–15. MR 611926, DOI 10.1016/S0195-6698(81)80015-7
- J. A. Bondy and U. S. R. Murty, Graph theory with applications, American Elsevier Publishing Co., Inc., New York, 1976. MR 0411988
- D. A. Burgess, On character sums and primitive roots, Proc. London Math. Soc. (3) 12 (1962), 179–192. MR 132732, DOI 10.1112/plms/s3-12.1.179
- F. R. K. Chung, Diameters and eigenvalues, J. Amer. Math. Soc. 2 (1989), no. 2, 187–196. MR 965008, DOI 10.1090/S0894-0347-1989-0965008-X
- Fan R. K. Chung, Quasi-random classes of hypergraphs, Random Structures Algorithms 1 (1990), no. 4, 363–382. MR 1138430, DOI 10.1002/rsa.3240010401
- Fan R. K. Chung, Regularity lemmas for hypergraphs and quasi-randomness, Random Structures Algorithms 2 (1991), no. 2, 241–252. MR 1099803, DOI 10.1002/rsa.3240020208
- F. R. K. Chung and R. L. Graham, Quasi-random hypergraphs, Random Structures Algorithms 1 (1990), no. 1, 105–124. MR 1068494, DOI 10.1002/rsa.3240010108 —, On graphs with missing prescribed induced subgraphs, A Tribute to Paul Erdös (A. Baker et al., eds.), Cambridge Univ. Press, 1990, pp. 111-120. —, Maximum cuts and quasi-random graphs (to appear).
- F. R. K. Chung and R. L. Graham, Cohomological aspects of hypergraphs, Trans. Amer. Math. Soc. 334 (1992), no. 1, 365–388. MR 1089416, DOI 10.1090/S0002-9947-1992-1089416-0 —, Quasi-random tournaments (to appear).
- F. R. K. Chung, R. L. Graham, and R. M. Wilson, Quasirandom graphs, Proc. Nat. Acad. Sci. U.S.A. 85 (1988), no. 4, 969–970. MR 928566, DOI 10.1073/pnas.85.4.969
- F. R. K. Chung, R. L. Graham, and R. M. Wilson, Quasi-random graphs, Combinatorica 9 (1989), no. 4, 345–362. MR 1054011, DOI 10.1007/BF02125347
- Dragoš M. Cvetković, Michael Doob, Ivan Gutman, and Aleksandar Torgašev, Recent results in the theory of graph spectra, Annals of Discrete Mathematics, vol. 36, North-Holland Publishing Co., Amsterdam, 1988. MR 926481
- Dragoš M. Cvetković, Michael Doob, and Horst Sachs, Spectra of graphs, Pure and Applied Mathematics, vol. 87, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1980. Theory and application. MR 572262
- P. Erdős and J. Spencer, Imbalances in $k$-colorations, Networks 1 (1971/72), 379–385. MR 299525, DOI 10.1002/net.3230010407 —, Probabilistic methods in combinatorics, Akadémiai Kiadó, Budapest, 1974.
- P. Erdős and Vera T. Sós, On Ramsey-Turán type theorems for hypergraphs, Combinatorica 2 (1982), no. 3, 289–295. MR 698654, DOI 10.1007/BF02579235
- Ronald Fagin, Probabilities on finite models, J. Symbolic Logic 41 (1976), no. 1, 50–58. MR 476480, DOI 10.2307/2272945 P. Frankl and V. Rödl, personal communication.
- P. Frankl and V. Rödl, Some Ramsey-Turán type results for hypergraphs, Combinatorica 8 (1988), no. 4, 323–332. MR 981890, DOI 10.1007/BF02189089
- P. Frankl, V. Rödl, and R. M. Wilson, The number of submatrices of a given type in a Hadamard matrix and related results, J. Combin. Theory Ser. B 44 (1988), no. 3, 317–328. MR 941440, DOI 10.1016/0095-8956(88)90040-8
- Z. Füredi and J. Komlós, The eigenvalues of random symmetric matrices, Combinatorica 1 (1981), no. 3, 233–241. MR 637828, DOI 10.1007/BF02579329 Y. V. Glebskii, D. I. Kogan, I. M. Liogonki, and V. A. Talanov, The extent and degree of satisfiability of a form of the restricted predicate calculus, Kibernetika 2 (1969), 31-42.
- Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete mathematics, 2nd ed., Addison-Wesley Publishing Company, Reading, MA, 1994. A foundation for computer science. MR 1397498
- R. L. Graham and J. H. Spencer, A constructive solution to a tournament problem, Canad. Math. Bull. 14 (1971), 45–48. MR 292715, DOI 10.4153/CMB-1971-007-1 J. Haviland, Cliques and independent sets, Ph.D. thesis, Cambridge Univ., 1989.
- Julie Haviland and Andrew Thomason, Pseudo-random hypergraphs, Discrete Math. 75 (1989), no. 1-3, 255–278. Graph theory and combinatorics (Cambridge, 1988). MR 1001401, DOI 10.1016/0012-365X(89)90093-9 —, Note on testing the ‘pseudo-randomness’ of a hypergraph (to appear).
- Sze-tsen Hu, A cohomology theory with higher coboundary operators. I. (Construction of the groups.), Nederl. Akad. Wetensch., Proc. 52 (1949), 1144–1150 = Indagationes Math. 11, 418–424 (1949). MR 33524 L. Lovaśz, personal communication.
- John W. Moon, Topics on tournaments, Holt, Rinehart and Winston, New York-Montreal, Que.-London, 1968. MR 0256919
- Vojtěch Rödl, On universality of graphs with uniformly distributed edges, Discrete Math. 59 (1986), no. 1-2, 125–134. MR 837962, DOI 10.1016/0012-365X(86)90076-2
- C. E. Shannon, A mathematical theory of communication, Bell System Tech. J. 27 (1948), 379–423, 623–656. MR 26286, DOI 10.1002/j.1538-7305.1948.tb01338.x
- Saharon Shelah and Joel Spencer, Zero-one laws for sparse random graphs, J. Amer. Math. Soc. 1 (1988), no. 1, 97–115. MR 924703, DOI 10.1090/S0894-0347-1988-0924703-8 M. Simonovits and V. T. Sós, Szemerédi partitions and quasi-randomness, Random Structures and Algorithms 2 (1991), 1-10. J. Spencer, personal communication. J. Spencer and P. Tetali, Quasi-random graphs with tolerance $\varepsilon$, preprint.
- Endre Szemerédi, Regular partitions of graphs, Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) Colloq. Internat. CNRS, vol. 260, CNRS, Paris, 1978, pp. 399–401 (English, with French summary). MR 540024
- Andrew Thomason, Random graphs, strongly regular graphs and pseudorandom graphs, Surveys in combinatorics 1987 (New Cross, 1987) London Math. Soc. Lecture Note Ser., vol. 123, Cambridge Univ. Press, Cambridge, 1987, pp. 173–195. MR 905280 —, Pseudo-random graphs, Proc. Random Graphs, Poznań 1985 (M. Karonski, ed.), Ann. Discrete Math., no. 33, North-Holland, 1987, pp. 307-331.
- Andrew Thomason, Dense expanders and pseudo-random bipartite graphs, Discrete Math. 75 (1989), no. 1-3, 381–386. Graph theory and combinatorics (Cambridge, 1988). MR 1001409, DOI 10.1016/0012-365X(89)90101-5
- W. D. Wallis, Combinatorial designs, Monographs and Textbooks in Pure and Applied Mathematics, vol. 118, Marcel Dekker, Inc., New York, 1988. MR 944533
- André Weil, Variétés abéliennes et courbes algébriques, Publ. Inst. Math. Univ. Strasbourg, vol. 8, Hermann & Cie, Paris, 1948 (French). MR 0029522
- Richard M. Wilson, Cyclotomy and difference families in elementary abelian groups, J. Number Theory 4 (1972), 17–47. MR 309755, DOI 10.1016/0022-314X(72)90009-1
- R. M. Wilson, Constructions and uses of pairwise balanced designs, Combinatorics (Proc. NATO Advanced Study Inst., Breukelen, 1974) Math. Centre Tracts, No. 55, Math. Centrum, Amsterdam, 1974, pp. 18–41. MR 0363939
- Richard M. Wilson, A diagonal form for the incidence matrices of $t$-subsets vs. $k$-subsets, European J. Combin. 11 (1990), no. 6, 609–615. MR 1078717, DOI 10.1016/S0195-6698(13)80046-7
Bibliographic Information
- © Copyright 1991 American Mathematical Society
- Journal: J. Amer. Math. Soc. 4 (1991), 151-196
- MSC: Primary 05C65; Secondary 03C13, 05C80
- DOI: https://doi.org/10.1090/S0894-0347-1991-1077279-1
- MathSciNet review: 1077279