Dense expanders and pseudo-random bipartite graphs
From MaRDI portal
Publication:2640620
DOI10.1016/0012-365X(89)90101-5zbMath0721.05051MaRDI QIDQ2640620
Publication date: 1989
Published in: Discrete Mathematics (Search for Journal in Brave)
Random graphs (graph-theoretic aspects) (05C80) Structural characterization of families of graphs (05C75)
Related Items (13)
Sandwiching biregular random graphs ⋮ Hermitian matrices and graphs: Singular values and discrepancy ⋮ Inverse expander mixing for hypergraphs ⋮ Quasi-Random Set Systems ⋮ Incidence‐free sets and edge domination in incidence graphs ⋮ Matrix and discrepancy view of generalized random and quasirandom graphs ⋮ Quasi-random subsets of \(\mathbb{Z}_ n\) ⋮ On testing the `pseudo-randomness' of a hypergraph ⋮ Discrepancy minimizing spectral clustering ⋮ The normalized matching property in random and pseudorandom bipartite graphs ⋮ Generalized quasirandom properties of expanding graph sequences ⋮ The Effect of Adding Randomly Weighted Edges ⋮ Relating multiway discrepancy and singular values of nonnegative rectangular matrices
Cites Work
- Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
- Sorting in \(c \log n\) parallel steps
- Explicit constructions of linear-sized superconcentrators
- Pseudo-random hypergraphs
- Parallel sorting
- On Concentrators, Superconcentrators, Generalizers, and Nonblocking Networks
- Explicit Concentrators from Generalized N-Gons
- Parallel Sorting with Constant Time for Comparisons
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Dense expanders and pseudo-random bipartite graphs
