Sparse quasi-random graphs
Let \(G_{1/2}(n)\) denote a random graph with \(n\) vertices in which each pair is selected to be an edge independently with probability \(1/2\). Almost all of them satisfy several basic properties which turn out to be equivalent. Families of graphs satisfying this equivalence class of properties are called quasi-random, see e.g. \textit{F. R. K. Chung}, textit{R. L. Graham} and \textit{R. M. Wilson} [Combinatorica 9, 345--362 (1989; Zbl 0715.05057)]. So far most of the results dealt with dense quasi-random graphs (having \(cn^2\) edges for some \(c>0\) as \(n \rightarrow \infty\)). This article studies quasi-random graphs with \(o(n^2)\) edges for analogous results, which are more difficult, due for example to the possible absence of certain local structures, such as 4-cycles.
- Large holes in quasi-random graphs
- Hermitian matrices and graphs: Singular values and discrepancy
- Embedding graphs with bounded degree in sparse pseudorandom graphs
- Regularity lemmas for clustering graphs
- Eigenvalues of Cayley graphs
- Clustering coefficients of large networks
- Counting results for sparse pseudorandom hypergraphs. I.
- Counting results for sparse pseudorandom hypergraphs. II.
- Extremal results in sparse pseudorandom graphs
- On the Turán number for the hexagon
- Quasi-random graphs of given density and Ramsey numbers
- Discrepancy and eigenvalues of Cayley graphs
- On an anti-Ramsey property of random graphs
- Quasi-random oriented graphs
- A spectral approach to analysing belief propagation for 3-colouring
- Graph partitioning via adaptive spectral techniques
- Random walks on quasirandom graphs
- From quasirandom graphs to graph limits and graphlets
- Regular pairs in sparse random graphs I
- On a theorem of Razborov
- Forcing quasirandomness with triangles
- Quasirandom Cayley graphs
- An analytic approach to sparse hypergraphs: hypergraph removal
- scientific article; zbMATH DE number 747030 (Why is no real title available?)
- Decompositions of quasirandom hypergraphs into hypergraphs of bounded degree
- The poset of hypergraph quasirandomness
- Structural Properties of Sparse Graphs
- Quasi‐random graphs with given degree sequences
- Quasi-random graphs
- Quasi-random graphs
- The cut metric, random graphs, and branching processes
- Powers of Hamilton cycles in pseudorandom graphs
- Subgraphs of the projective norm graph
- Eigenvalues and extremal degrees of graphs
This page was built for publication: Sparse quasi-random graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1848147)