Dense expanders and pseudo-random bipartite graphs

DOI10.1016/0012-365X(89)90101-5zbMath0721.05051MaRDI QIDQ2640620

Andrew G. Thomason

Publication date: 1989

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

dense bipartite graphexpanding properties

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Structural characterization of families of graphs (05C75)

Related Items

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