Approximate Moore graphs are good expanders

DOI10.1016/J.JCTB.2019.08.003MaRDI QIDQ2284745zbMATH OpenOpenAlexFDO

Authors Michael Dinitz, Michael Schapira, Gal Shahaf

Publication date 15 January 2020

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

Full work available at URL https://arxiv.org/abs/1611.01755

zbMATH Keywords

expander graphsnetwork designspectral graph theory

Mathematics Subject Classification ID

Distance in graphs (05C12) Expander graphs (05C48)

Abstract: We revisit the classical question of the relationship between the diameter of a graph and its expansion properties. One direction is well understood: expander graphs exhibit essentially the lowest possible diameter. We focus on the reverse direction, showing that "sufficiently large" graphs of fixed diameter and degree must be "good" expanders. We prove this statement for various definitions of "sufficiently large" (multiplicative/additive factor from the largest possible size), for different forms of expansion (edge, vertex, and spectral expansion), and for both directed and undirected graphs. A recurring theme is that the lower the diameter of the graph and (more importantly) the larger its size, the better the expansion guarantees. Aside from inherent theoretical interest, our motivation stems from the domain of network design. Both low-diameter networks and expanders are prominent approaches to designing high-performance networks in parallel computing, HPC, datacenter networking, and beyond. Our results establish that these two approaches are, in fact, inextricably intertwined. We leave the reader with many intriguing questions for future research.

Recommendations

• scientific article; zbMATH DE number 7378741
• Expander graphs and their applications
• Diameters and Eigenvalues
• Moore graphs and beyond: a survey of the degree/diameter problem
• Expanders -- how to find them, and what to find in them

Cites work

• A connection between a question of Bermond and Bollobás and Ramanujan graphs
• A new proof of Friedman's second eigenvalue theorem and its extension to random lifts
• A note on large graphs of diameter two and given maximum degree
• A Survey of Full Length Nonlinear Shift Register Cycle Algorithms
• A VLSI decomposition of the deBruijn graph
• Asymptotically large (\(\Delta,D\))-graphs
• Computational Complexity
• Expandable and Cost-Effective Network Structures for Data Centers Using Dual-Port Servers
• Expander graphs and their applications
• Fault-Tolerant Multiprocessor Link and Bus Network Architectures
• Fault-Tolerant Routing in DeBruijn Comrnunication Networks
• Girth and Euclidean distortion
• scientific article; zbMATH DE number 4165188 (Why is no real title available?)
• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 1460605 (Why is no real title available?)
• scientific article; zbMATH DE number 7378741 (Why is no real title available?)
• scientific article; zbMATH DE number 3095523 (Why is no real title available?)
• Large fault-tolerant interconnection networks
• Moore graphs and beyond: a survey of the degree/diameter problem
• NON-BACKTRACKING RANDOM WALKS MIX FASTER
• On a Homomorphism of the de Bruijn Graph and its Applications to the Design of Feedback Shift Registers
• On a problem of a. kotzig concerning factorizations of 4‐regular graphs
• On Graphs that do not Contain a Thomsen Graph
• On Minimal graphs of maximum even girth
• On Moore Graphs with Diameters 2 and 3
• On the second eigenvalue of a graph
• Regular graphs with excess one
• Spectral redemption in clustering sparse networks
• The second eigenvalue of regular graphs of given girth
• The spectrum of de Bruijn and Kautz graphs

Cited in

(4)

• On the spectrum and linear programming bound for hypergraphs
• scientific article; zbMATH DE number 7378741 (Why is no real title available?)
• Edge-disjoint Hamilton cycles in the McKay-Miller-Širáň graphs
• Radio gracefulness of Moore graphs and beyond

This page was built for publication: Approximate Moore graphs are good expanders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2284745)