Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)

DOI10.1006/JCTB.1994.1054zbMath0814.68098OpenAlexW2036871172WikidataQ56442223 ScholiaQ56442223MaRDI QIDQ1333324

Moshe Morgenstern

Publication date: 12 June 1995

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jctb.1994.1054

zbMATH Keywords

Cayley graphsexpandersRamanujan graphexplicit construction

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items (only showing first 100 items - show all)

Equitable partition for some Ramanujan graphs ⋮ Constructions of strongly regular Cayley graphs derived from weakly regular bent functions ⋮ Strong blocking sets and minimal codes from expander graphs ⋮ Spectrum of the weighted adjacency operator on a nonuniform arithmetic quotient of \(\mathrm{PGL}_3\) ⋮ Weak Ramanujan property of the standard non-uniform arithmetic quotient of \(\mathrm{PGL}_4\) ⋮ Degree Ramsey Numbers of Graphs ⋮ Shift lifts preserving Ramanujan property ⋮ Tight products and graph expansion ⋮ Quantum ergodicity for quantum graphs without back-scattering ⋮ Expanders and time-restricted branching programs ⋮ Linear-time list recovery of high-rate expander codes ⋮ Upper bounds on the bisection width of 3- and 4-regular graphs ⋮ An application of Ramanujan graphs to \(C^*\)-algebra tensor products ⋮ Explicit construction of a Ramanujan \((n_1,n_2,\dots,n_{d-1})\)-regular hypergraph ⋮ Finite fields and Ramanujan graphs ⋮ Local expanders ⋮ A bipartite analogue of Dilworth's theorem ⋮ Minors in graphs of large \(\theta_r\)-girth ⋮ New spectral lower bounds on the bisection width of graphs ⋮ Large cuts with local algorithms on triangle-free graphs ⋮ Ramanujan coverings of graphs ⋮ Pseudorandom generators for combinatorial checkerboards ⋮ Graphs with high second eigenvalue multiplicity ⋮ A randomized construction of high girth regular graphs ⋮ On regular hypergraphs of high girth ⋮ A simple proof for the lower bound of the girth of graphs \(D(n,q)\) ⋮ Optimal strong approximation for quadrics over \(\mathbb{F}_q [t\)] ⋮ A spectral bound for vertex-transitive graphs and their spanning subgraphs ⋮ Routing with bounded buffers and hot-potato routing in vertex-symmetric networks ⋮ Explicit construction of \(q+1\) regular local Ramanujan graphs, for all prime-powers \(q\) ⋮ Low Polynomial Exclusion of Planar Graph Patterns ⋮ Graph rigidity properties of Ramanujan graphs ⋮ On the eigenvalues of the graphs \(D(5,q)\) ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Classical Kloosterman sums: representation theory, magic squares, and Ramanujan multigraphs ⋮ Parameterized Counting and Cayley Graph Expanders ⋮ Ramanujan graphs and exponential sums over function fields ⋮ Expander graphs and their applications ⋮ Finite simple groups of Lie type as expanders. ⋮ Simply transitive quaternionic lattices of rank 2 over_q(t) and a non-classical fake quadric ⋮ A Tight Erdös--Pósa Function for Wheel Minors ⋮ Relative expanders or weakly relatively Ramanujan graphs. ⋮ Kesten's theorem for invariant random subgroups. ⋮ Almost-Ramanujan graphs and prime gaps ⋮ Regular partitions of gentle graphs ⋮ Ramanujan complexes and high dimensional expanders ⋮ Finite simple groups as expanders ⋮ Formal Zeta function expansions and the frequency of Ramanujan graphs ⋮ Regular graphs of large girth and arbitrary degree ⋮ A connection between a question of Bermond and Bollobás and Ramanujan graphs ⋮ Lower bounds for tropical circuits and dynamic programs ⋮ Problems and results in extremal combinatorics. II ⋮ Expansion of random graphs: new proofs, new results ⋮ Deterministic methods of Ramanujan graph construction for use in cryptographic algorithms based on generalized cellular automata ⋮ Explicit expanders of every degree and size ⋮ Corrigendum to: ``Almost-Ramanujan graphs and prime gaps ⋮ On the planar split thickness of graphs ⋮ Erdős-Hajnal-type results for monotone paths ⋮ On sensitivity of mixing times and cutoff ⋮ L ^p -distortion and p -spectral gap of finite graphs ⋮ Keyed hash function from large girth expander graphs ⋮ Combinatorial algorithms for distributed graph coloring ⋮ On cycle lengths in claw-free graphs with complete closure ⋮ Sparse regular random graphs: spectral density and eigenvectors ⋮ Character sums, automorphic forms, equidistribution, and Ramanujan graphs. Part II. Eigenvalues of Terras ⋮ No sublogarithmic-time approximation scheme for bipartite vertex cover ⋮ A lower bound on the spectral radius of the universal cover of a graph ⋮ Explicit constructions of Ramanujan complexes of type \(\widetilde A_d\). ⋮ Optimal configurations for peer-to-peer user-private information retrieval ⋮ On the girth of random Cayley graphs ⋮ A strengthening and a multipartite generalization of the Alon-Boppana-Serre theorem ⋮ Minimal selectors and fault tolerant networks ⋮ Quaternionic arithmetic lattices of rank 2 and a fake quadric in characteristic 2 ⋮ Unnamed Item ⋮ The measurable Kesten theorem ⋮ Character sums, automorphic forms, equidistribution, and Ramanujan graphs Part I. The Kloosterman sum conjecture over function fields ⋮ Ramanujan graphs and expander families constructed from \(p\)-ary bent functions ⋮ Recent progress on graphs with fixed smallest adjacency eigenvalue: a survey ⋮ An explicit infinite family of \(\mathbb{M}\)-vertex graphs with maximum degree \(K\) and diameter \([1+o(1)\log_{K-1}\mathbb{M}\) for each \(K-1\) a prime power] ⋮ A combinatorial proof of Bass's determinant formula for the zeta function of regular graphs ⋮ Ramanujan Graphs for Post-Quantum Cryptography ⋮ A fast new algorithm for weak graph regularity ⋮ Opinion forming in Erdős-Rényi random graph and expanders ⋮ Opinion Forming in Erdös-Rényi Random Graph and Expanders ⋮ On non-uniform Ramanujan complexes ⋮ ON CONSTRUCTION OF ALMOST-RAMANUJAN GRAPHS ⋮ Expanding graphs and invariant means ⋮ Packing and Covering Induced Subdivisions ⋮ Improved Ramsey-type results for comparability graphs ⋮ Not every uniform tree covers Ramanujan graphs ⋮ Expander graphs in pure and applied mathematics ⋮ The Ramanujan conjecture and its applications ⋮ From Ramanujan graphs to Ramanujan complexes ⋮ On \(k\)-chromatically connected graphs ⋮ Ramanujan graphs on cosets of \(\operatorname{PGL}_2(\mathbb F_q)\) ⋮ Natural bounded concentrators ⋮ The Ramanujan property for regular cubical complexes ⋮ Explicit Near-Ramanujan Graphs of Every Degree ⋮ Kissing numbers of regular graphs ⋮ Ramanujan edge-indexed graphs

This page was built for publication: Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)