Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)

 
 

 

Quasi-random set systems


Authors: F. R. K. Chung and R. L. Graham
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
Full-text PDF

References | Similar Articles | Additional Information

References [Enhancements On Off] (What's this?)

  • [BNS89] 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.
  • [Be89] C. Berge, Hypergraphs, North-Holland, Amsterdam, 1989. MR 1013569 (90h:05090)
  • [Bo85] B. Bollobás, Random graphs, Academic Press, New York, 1985. MR 809996 (87f:05152)
  • [Bo79] -, Graph theory, Springer-Verlag, New York, 1979. MR 536131 (80j:05053)
  • [BT81] B. Bollobás and A. Thomason, Graphs which contain all small graphs, European J. Combin. 2 (1981), 13-15. MR 611926 (82d:05071)
  • [BM76] J. A. Bondy and U. S. R. Murty, Graph theory with applications, Elsevier, New York, 1976. MR 0411988 (54:117)
  • [B62] D. A. Burgess, On character sums and primitive roots, Proc. London Math. Soc. 12 (1962), 179-192. MR 0132732 (24:A2569)
  • [C89] F. R. K. Chung, Diameters and eigenvalues, J. Amer. Math. Soc. 2 (1989), 187-196. MR 965008 (89k:05070)
  • [C90] -, Quasi-random classes for hypergraphs, Random Structures and Algorithms 1 (1990), 363-382. MR 1138430 (93b:05126)
  • [C91] -, Regularity lemmas for hypergraphs and quasi-randomness, Random Structures and Algorithms 2 (1991) (to appear). MR 1099803 (92d:05117)
  • [CG90(a)] F. R. K. Chung and R. L. Graham, Quasi-random hypergraphs, Random Structures and Algorithms 1 (1990), 105-124. MR 1068494 (91h:05089)
  • [CG90(b)] -, 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.
  • [CG(a)] -, Maximum cuts and quasi-random graphs (to appear).
  • [CG(b)] -, Cohomological aspects of hypergraphs, Trans. Amer. Math. Soc. (to appear). MR 1089416 (93a:05097)
  • [CG(c)] -, Quasi-random tournaments (to appear).
  • [CGW88] F. R. K. Chung, R. L. Graham, and R. M. Wilson, Quasi-random graphs, Proc. Nat. Acad. U.S.A. 85 (1988), 969-970. MR 928566 (89a:05116)
  • [CGW89] -, Quasi-random graphs, Combinatorica 9 (1989), 345-362. MR 1054011 (91e:05074)
  • [CDGT88] D. Cvetković, M. Doob, I. Gutman, and A. Torgasev, Recent results in the theory of graph spectra, Ann. Discrete Math., no. 36, North-Holland, Amsterdam, 1988. MR 926481 (89d:05130)
  • [CDS80] D. Cvetković, M. Doob, and H. Sacks, Spectra of graphs, Academic Press, New York, 1980. MR 572262 (81i:05054)
  • [ES72] P. Erdös and J. Spencer, Imbalances in $ k$-colorations, Networks 1 (1972), 379-385. MR 0299525 (45:8573)
  • [ES74] -, Probabilistic methods in combinatorics, Akadémiai Kiadó, Budapest, 1974.
  • [ES82] P. Erdös and V. T. Sós, On Ramsey-Turàn type theorems for hypergraphs, Combinatorica 2 (1982), 289-295. MR 698654 (85d:05185)
  • [F76] R. Fagin, Probabilistic on finite models, J. Symbolic Logic 41 (1976), 51-58. MR 0476480 (57:16042)
  • [FR89] P. Frankl and V. Rödl, personal communication.
  • [FR88] -, Some Ramsey-Turán type results for hypergraphs, Combinatorica 8 (1988), 323-332. MR 981890 (90a:05106)
  • [FRW88] P. Frankl, V. Rödl, and R. M. Wilson, The number of submatrices of given type in a Hadamard matrix and related results, J. Combin. Theory Ser. B 44 (1988), 317-328. MR 941440 (89f:05044)
  • [FK81] Z. Füredi and J. Komlós, The eigenvalues of random symmetric matrices, Combinatorica 1 (1981), 233-241. MR 637828 (83e:15010)
  • [GKLT69] 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.
  • [GKP89] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete mathematics, Addison-Wesley, Reading, MA, 1989. MR 1397498 (97d:68003)
  • [GS71] R. L. Graham and J. H. Spencer, A constructive solution to a tournament problem, Canad. Math. Bull. 14 (1971), 45-48. MR 0292715 (45:1798)
  • [H89] J. Haviland, Cliques and independent sets, Ph.D. thesis, Cambridge Univ., 1989.
  • [HT89] J. Haviland and A. Thomason, Pseudo-random hypergraphs, Discrete Math. 75 (1989), 255-278. MR 1001401 (90d:05185)
  • [HT(a)] -, Note on testing the `pseudo-randomness' of a hypergraph (to appear).
  • [H49] S. T. Hu, A cohomology theory with higher coboundary operators. I, Nederl. Akad. Wetensch. Proc. 52 (1949), 1144-1150. MR 0033524 (11:452a)
  • [L89] L. Lovaśz, personal communication.
  • [M68] J. Moon, Topics on tournaments, Holt, Rinehart, and Winston, New York, 1968. MR 0256919 (41:1574)
  • [R86] V. Rödl, On the universality of graphs with uniformly distributed edges, Discrete Math. 59 (1986), 125-134. MR 837962 (88b:05098)
  • [S48] C. Shannon, A mathematical theory of communication, Bell System Tech. J. 27 (1948), 379-423. MR 0026286 (10:133e)
  • [SS88] S. Shelah and J. Spencer, Zero-one laws for sparse random graphs, J. Amer. Math. Soc. 1 (1988), 97-106. MR 924703 (89i:05249)
  • [SS91] M. Simonovits and V. T. Sós, Szemerédi partitions and quasi-randomness, Random Structures and Algorithms 2 (1991), 1-10.
  • [S89] J. Spencer, personal communication.
  • [ST(a)] J. Spencer and P. Tetali, Quasi-random graphs with tolerance $ \varepsilon $, preprint.
  • [Sz78] E. Szemerédi, On regular partitions of graphs, Problèmes Combinatoire et Théorie des Graphes (J. Bermond et al., eds.) CNRS, Paris, 1978, pp. 399-401. MR 540024 (81i:05095)
  • [T87(a)] A. Thomason, Random graphs, strongly regular graphs and pseudo-random graphs, Surveys in Combinatorics 1987 (C. Whitehead, ed.), London Math. Soc. Lecture Notes Ser., no. 123, Cambridge Univ. Press, Cambridge, 1987, pp. 173-196. MR 905280 (88m:05072)
  • [T87(b)] -, Pseudo-random graphs, Proc. Random Graphs, Poznań 1985 (M. Karonski, ed.), Ann. Discrete Math., no. 33, North-Holland, 1987, pp. 307-331.
  • [T89] -, Dense expanders and pseudo-random bipartite graphs, Discrete Math. 75 (1989), 381-386. MR 1001409 (90i:05085)
  • [Wa88] W. D. Wallis, Combinatorial designs, Marcel Dekker, New York, 1988 (Example 8.5.5 on graphical Hadamard matrices, p. 160). MR 944533 (89d:05023)
  • [We48] A. Weil, Sur les courbes algébrique et les variétés qui śen déduisent, Actualités Sci. Indust., no. 1041, Hermann, Paris, 1948. MR 0029522 (10:621d)
  • [Wi72] R. M. Wilson, Cyclotomy and difference families on abelian groups, J. Number Theory 4 (1972), 17-47. MR 0309755 (46:8860)
  • [Wi74] -, Constructions and uses of pairwise balanced designs, Combinatorics (M. Hall, Jr. and J. H. van Lint, eds.), Math. Centre Tracts, no. 55, Amsterdam, 1974, pp. 18-41. MR 0363939 (51:194)
  • [Wi90] -, A diagonal form for the incidence matrices of $ t$-subsets vs. $ k$-subsets, European J. Combin. 11 (1990), 609-615. MR 1078717 (91i:05010)

Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC: 05C65, 03C13, 05C80

Retrieve articles in all journals with MSC: 05C65, 03C13, 05C80


Additional Information

DOI: https://doi.org/10.1090/S0894-0347-1991-1077279-1
Article copyright: © Copyright 1991 American Mathematical Society

American Mathematical Society