Quasirandom graphs

References for quasirandom graphs in chronological order

Keyword search:

V. R"odl, On the universality of graphs with uniformly distributed edges, Discrete Math. 59 (1986), 125--134. Abstract.
A. Thomason, Random graphs, strongly regular graphs and pseudo-random graphs, in Surveys in Combinatorics 1987 (C. Whitehead, ed.) LMS Lecture Notes Series 123, Cambridge Univ. Press, Cambridge, 173--196. Abstract and remarks.
A. Thomason, Pseudo-random graphs, Proceedings of Random Graphs, Poznan 1985 (M. Karonski, ed.) Annals of Dicrete Math. 33 (1987), 307--331. Abstract.
P. Frankl, V. R"odl and R. M. Wilson, The number of submatrices of a given type in a Hadamard matrix and related results, Journal of Comb. Theory, B, 44 (1988), 317--328. Abstract.

The 14 articles on quasirandom graphs between 1989 -- 1997.

F. Chung, R. L. Graham and R. M. Wilson, Quasi-random graphs, a short version appeared in Proc. Natl. Acad. Sci. USA, 85 (1988), 969--970, a long version appeared in Combinatorica 9 (1989), 345--362, Link.
F. Chung and R. L. Graham, Quasi-random hypergraphs, Proc. Natl. Acad. Sci. USA 86 (1989), 8175--8177, Long version appeared in Random Structures and Algorithms 1 (1990), 105--124. Link.
F. Chung and R. L. Graham, On graphs not containing prescribed induced subgraphs, in A Tribute to Paul Erdos, Cambridge University Press (1990), 111--120. Link.
F. Chung, Quasi-random classes of hypergraphs, Random Structures and Algorithms 1 (1990), 363--382. Corrigendum: Quasirandom hypergraphs revisited, Corrigendum of Quasi-random classes of hypergraphs, Random Sturctures and Algorithms, 40, (2012), 39--48.
F. Chung and R. L. Graham, Quasi-random set systems, J. Amer. Math. Soc. 4 (1991), 151--196. Link.
F. Chung, Regularity lemmas for hypergraphs and quasi-randomness, Random Structures and Algorithms 2 (1991), 241--252. Link.
F. Chung and R. L. Graham, Quasi-random tournaments, J. of Graph Theory 15 (1991), 173--198. Link.
M. Simonovits, V.T. Sos Szemeredi's partition and quasirandomness, Random Structures Algorithms, 2 (1991), 1--10 Link.
F. Chung and R. L. Graham, Maximum cuts and quasirandom graphs, in Random Graphs, John Wiley and Sons (1992), 23--33. Link.
F. Chung and R. L. Graham, Cohomological aspects of hypergraphs, Trans. Amer. Math. Soc. 334 (1992), 365--388. Link.
F. Chung and R. L. Graham, Quasi-ransom subsets of \( Z_n\), J. Comb. Theory (A) 61 (1992), 64--86. Link.
F. Chung and R. L. Graham, On hypergraphs having evenly distributed subhypergraphs, Disc. Math. 111 (1993), 125--129. Link
F. Chung and P. Tetali, Communication complexity and quasi-randomness, SIAM J. Discrete Math. 6 (1993), 110--123. Link.
M. Simonovits, V.T. Sos Hereditarily extended properties, quasi-random graphs and not necessarily induced subgraphs Combinatorica, 17 (1997), 577--596. Abstract.

References after 1997.

J. S. Myers, Graphs without large complete minors are quasi-random, Combinatorics, Probability and Computing (2002) 11, 571--585. Link.
F. Chung and R. L. Graham, Sparse quasi-random graphs, Combinatorica 22 (2002), 217--244. Link.
M. Simonovits, V.T. Sos Hereditary extended properties, quasi-random graphs and induced subgraphs Combin. Probab. Comput., 12 (2003), 319--344. Link.
Y. Kohayakawa, V. Rodl and J. Skokan, Hypergraphs, Quasi-randomness, and Conditions for Regularity, Journal of Combinatorial Theory, Series A 97, (2002), 307--352 Link.
Y. Kohayakawa and V. Rodl, Regular pairs in sparse random graphs I, Random Structures & Algorithms, 22, no. 4, (2003), 359--434.
Y. Kohayakawa, V. Rodl and L. Thoma, An optimal algorithm for checking regularity, SIAM Journal on Computing, 32, no. 5, (2003), 1210--1235. Link.
J. N. Cooper, Quasirandom permutations, Journal of Combinatorial Theory, Series A 106, no. 1, (2004), 123--143. Link
J. Skokan and L. Thoma, Bipartite subgraphs and quasi-randomness, Graphs Combin. 20 (2004), 255--262. Link.
B. Bollobas and V. Nikiforov, Hermitian matrices and graphs: singular values and discrepancy, Discrete Math, 285 (2004), 17--32. Link.
B. Bollobas and V. Nikiforov, Graphs and Hermitian matrices: eigenvalue interlacing, Discrete Math, 289 (2004), 119--127. Link.
V. Nikiforov, C.C. Rousseau and R. H. Schelp, Book Ramsey numbers and quasi-randomness, Combin. Probab. Comp. 14 (2005), 851--860. Link.
V. Rodl and J. Skokan, Counting subgraphs in quasi-random 4-uniform hypergraphs, Random Structures and Algorithms, 26, (2005), 160-203. Link.
W. T. Gowers, Quasirandomness, counting and regularity for 3-uniform hypergraphs, Combinatorics, Probability and Computing, 15 (2006), 143--184. Link.
T. Tao, A variant of the hypergraph removal lemma, J. Combin. Theory Ser. A 113 (2006), 1257--1280. Link.
B. Nagle, V. Rodl, and M. Schacht, The counting lemma for regular k-uniform hypergraphs, Random Structures Algorithms 28 (2006), 113--179. Link.
N. Alon, A. Coja-Oghlan, H. Han, M. Kang, V. Rodl and M. Schacht, Quasi-randomness and Algorithmic Regularity for Graphs with General Degree Distributions, Lecture Notes in Computer Science, Volume 4596. (2007), 789-800. Link.
A. Shapira, Quasi-randomness and the distribution of copies of a fixed graph, Combinatorica, 28 (2008), 735--745. Link.
F. Chung and R. L. Graham, Quasi-random graphs with given degree sequences, Random Structures and Algorithms, 12 (2008), 1--19. Link.
L. Lovasz and V. T. Sos, Generalized quasirandom graphs, Journal of Combinatorial Theory, B, 98 (2008), 146--163. Link.
A. Shapira and R. Yuster. The Effect of Induced Subgraphs on Quasi-Randomness Proc. of SODA 2008, 789-798. Random Structures and Algorithms, 36 (2010), 90--109. Link.
R. Yuster, Quasi-randomness is determined by the distribution of copies of a fixed graph in equicardinal large sets, Lecture Notes in Computer Science, Volume 5171, (2008), 596-601. Link.
W. T. Gowers, Quasirandom groups, Combinatorics, Probability and Computing, 17, (2008), 363--387. Link.
D. Conlon, J. Fox and B. Sudakov, An approximate version of Sidorenko's conjecture, GAFA, 20, no. 6, (2010), 1354--1366. Link.
Y. Kohayakawa, B. Nagle, V. Rodl and M. Schacht, Weak hypergraph regularity and linear hypergraphs, Journal of Combinatorial Theory, Series B 100, (2010), 151--160. Link
H. Hatami, Graph norms and Sidorenko's conjecture, Israel J. Math. (2010), 125--150.
D. Dellamonica and V. Rodl, Hereditary quasirandom properties of hypergraphs, Combinatorica, 31, No. 2 (2011), 165-182. Link.
S. Janson, Quasi-random graphs and graph limits, European Journal of Combinatorics, 32, no. 7, (2011), 1054--1083. Link.
L. Lovasz, B. Szegedy: Finitely forcible graphons, J. Combin. Theory Ser. B 101 (2011), 269--301. Link.
C. Hoppen, Y. Kohayakawa, C. G. Moreira, R. M. Sampaio: Testing permutation properties through subpermutations, Theoretical Computer Science 412, (2011), 3555--3567.
D. Conlon, H. H`an, Y. Person, and M. Schacht, Weak quasi-randomness for uniform hypergraphs, Random Sturctures and Algorithms, 40, (2012), 1--38. Link.
H. Han, Y. Person and M. Schacht, Note on forcing pairs, Electronic Notes in Discrete Mathematics, 38, (2011), 437--442. link
H. Huang, C. Lee, Quasi-randomness of graph balanced cut properties Random Structures and Algorithms, 16 (2012), 124--145. Link.
A. Shapira and R. Yuster, The Quasi-Randomness of Hypergraph Cut Properties, Random Structures and Algorithms 40 (2012), 105--131. Link.
F. Chung, From quasirandom graphs to graph limits and graphlets , preprint. Link.
C. Hoppen, Y. Kohayakawa, C. G. Moreira, B. Rath, R. M. Sampaio: Limits of permutation sequences, preprint, arXiv:1103.5844. Link
S. Kalyanasundaram and A. Shapira, A Note on Even Cycles and Quasi-Random Tournaments, Journal of Graph Theory, 73 (3) (2013), 260--266. Link.
D. Kral, O.Pikhurko Quasirandom permutations are characterized by 4-point densities, preprint, arXiv:1205.3074. Link
J. Lenz and D. Mubayi, Eigenvalues and quasirandom hypergraphs, preprint. Link.
S. Griffiths, Quasi-random oriented graphs, J. of Graph Theory, 74 (2), (2013), 198--209. Link
L. N. Coregliano and A. A. Razborov, On the density of transitive tournaments, preprint.

(back to the full list) | (back to the resourses page)