Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
From MaRDI portal
Publication:1333324
DOI10.1006/jctb.1994.1054zbMath0814.68098OpenAlexW2036871172WikidataQ56442223 ScholiaQ56442223MaRDI QIDQ1333324
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
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
Constructions of strongly regular Cayley graphs derived from weakly regular bent functions, 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, Equitable partition for some Ramanujan graphs, Expander graphs and their applications, Finite simple groups of Lie type as expanders., Simply transitive quaternionic lattices of rank 2 overq(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, 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, Local correctability of expander codes, Interlacing families. I: Bipartite Ramanujan graphs of all degrees, New and explicit constructions of unbalanced Ramanujan bipartite graphs, Ramanujan complexes of type \(\widetilde A_d\)
