Pseudo-random Graphs

By Michael Krivelevich, Benny Sudakov. 2005

452 citations recorded by the source corpus.

Random graphs have proven to be one of the most important and fruitful concepts in modern Combinatorics and Theoretical Computer Science. Besides being a fascinating study subject for their own sake, they serve as essential instruments in proving an enormous number of combinatorial statements, making their role quite hard to overestimate. Their tremendous success serves as a natural motivation for the following very general and deep informal questions: what are the essential properties of random graphs? How can one tell when a given graph behaves like a random graph? How to create deterministically graphs that look random-like? This leads us to a concept of pseudo-random graphs.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics

View Paper: https://www.semanticscholar.org/paper/ac296d5febd86f556f1e8d543cebfda28dfd2ab7

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

Citations in the corpus

Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges (2009, background): “…discrepancy-like properties, path congestion, chromatic number and the mixing time for random walk; see e.g. [22] for a compendium of these results, [43, 24, 25, 23] for the relationship between the two matrices and “pseudo-random” properties of graphs and [4, 33, 30] for algorithmic applications.”
MaxCut in ${\bm H)$-Free Graphs (2005, background): “Moreover, this is a strongly-regular graph and its smallest eigenvalue is − k (see, e.g., [18]).”
EIGENVALUES AND LINEAR QUASIRANDOM HYPERGRAPHS (2012, methodology): “For details on quasirandomness, we refer the reader to a survey of Krivelevich and Sudakov [30] for graphs and recent papers of Gowers [23, 24, 25] for general quasirandom structures including hypergraphs.”
Large matchings from eigenvalues (2007, background): “We refer the reader to the survey [8].”
Mixing Complexity and its Applications to Neural Networks (2017, background): “More formally, We remark that the latter deﬁnition can be stated for graphs whose density, e ( A,B ) | A || B | , is differs from half (Krivelevich & Sudakov, 2006) 1 .”
Metrics for sparse graphs (2007, background): “It is natural to view a sequence (Gn) converging to κ in dsub as a sequence of ‘inhomogeneous quasi-random graphs’: when κ is constant, the convergence condition is equivalent to the standard notion of quasi-randomness, introduced by Thomason [37] in 1987 (although he called it pseudo-randomness) an”
An exponential improvement for diagonal Ramsey (2023, methodology): “The approach to bounding R(k) using quasirandomness, which was pioneered in [21] and later refined in [5,18], has been extremely influential in combinatorics and computer science, with many exciting developments over the past 35 years, see for example the survey [16].”
Many T copies in H-free graphs (2015, unknown): “As shown in [3] (see also [34], Theorem 4.”
Eigenvalues and edge-connectivity of regular graphs (2010, background): “These results improve the previous bound of Krivelevich and Sudakov.”
Non-backtracking random walks mix faster (2006, background): “We mention a few of the properties of these graphs, and refer the readers to [11] for an extensive survey of the subject.”
Distribution of subgraphs of random regular graphs (2008, unknown): “The reader is referred to [ 30 , 32] for discussions on pseudo-random graphs.”