Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
|
   
Mobile Device Pairing
 Journal of the American Mathematical Society
Journal of the American Mathematical Society
ISSN 1088-6834(e) ISSN 0894-0347(p)

     

Quasi-random set systems

Author(s): F. R. K. Chung; R. L. Graham
Journal: J. Amer. Math. Soc. 4 (1991), 151-196.
MSC: Primary 05C65; Secondary 03C13, 05C80
MathSciNet review: 1077279
Retrieve article in: PDF
This article is available free of charge

References | Similar articles | Additional information

References:

[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: 10.1090/S0894-0347-1991-1077279-1
PII: S0894-0347-1991-1077279-1
Copyright of article: Copyright 1991, American Mathematical Society




AMS and Social Media LinkedIn Facebook Podcasts Twitter YouTube RSS Feeds Blogs Wikipedia