References for quasirandom graphs in chronological order
Keyword search:
|
Early papers
|
14 papers
|
sparse random graphs
|
hypergraphs
|
permutations
|
graph limits
(back to the full list) |
(back to the resourses page)
Early references before the introduction of quasirandom graphs.
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)