­

Expander graphs and where to find them

Snapshots of modern mathematics from Oberwolfach

Expander graphs and where to find them

Graphs are mathematical objects composed of a collection of “dots” called vertices, some of which are joined by lines called edges. Graphs are ideal for visually representing relations between things, and mathematical properties of graphs can provide an insight into real-life phenomena. One interesting property is how connected a graph is, in the sense of how easy it is to move between the vertices along the edges. The topic dealt with here is the construction of particularly well-connected graphs, and whether or not such graphs can happily exist in worlds similar to ours.

If you are interested in translating this Snapshot, please contact us at info@imaginary.org

Mathematical subjects

Algebra and Number Theory
Analysis
Geometry and Topology

Connections to other fields

Engineering and Technology

Author(s)

Ana Khukhro

License

DOI (Digital Object Identifier)

10.14760/SNAP-2019-016-EN

Download PDF

snapshots-2019-016.pdf

PDF

snapshots: overview

      Michael Joswig
      Convex polytopes and linear programs
      Thorsten Heidersdorf
      Truncated fusion rules for supergroups
      Ralf Korn
      Uncertainty as an ingredient in financial modeling
      Sarah Hess, Angélica Torres, Mirte van der Eyden
      Voronoi Cells: Or How to Find the Nearest Bakery
      Ana Djurdjevac, Henri Elad Altman, Tommaso Rosati
      Randomness is natural - an introduction to regularisation by noise
      Po-Lam Yung
      Waves and incidences
      Luca Chiantini, Brian Harbourne
      Geproci sets: a new perspective in algebraic geometry
      Florian Frick
      The geometry of fair division
      Giuseppe Negro, Diogo Oliveira e Silva
      4 = 2 × 2, or the power of even integers in Fourier analysis
      Isabelle Baraquin, Nadia Lafrenière, Katharina Schuh
      Cutoff phenomenon: Surprising behaviour in card shuffling and other Markov chains
      Vern I. Paulsen
      Algebras and quantum games
      Ingmar Saberi
      Felder und Räume: Symmetrie und Lokalität in Mathematik und theoretischen Wissenschaften
      Pieter Belmans
      The periodic tables of algebraic geometry
      Jason J. Bramburger
      Patterns and waves in theory, experiment, and application
      Benjamin Dozier
      Closed geodesics on surfaces
      Kathrin Hellmuth, Christian Klingenberg
      Route planning for bacteria
      Fabian Mussnig
      Characterizations of intrinsic volumes on convex bodies and convex functions
      Jennifer S. Balakrishnan
      A tale of three curves
      Michael Baake, Uwe Grimm, Robert V. Moody
      What is Pattern?
      Saiteja Utpala, Nina Miolane
      Biological Shape Analysis with Geometric Statistics and Learning
      Ilya Dumanski, Valentina Kiritchenko
      Representations and degenerations
      Jonas Latz, Björn Sprungk
      Solving inverse problems with Bayes’ theorem
      Herbert Gangl
      Jewellery from tessellations of hyperbolic space
      Chr istina Frederick, Yunan Yang
      Seeing through rock with help from optimal transport
      David A. Craven
      Searching for the Monster in the Trees
      Hugh Thomas
      The Robinson–Schensted algorithm
      Franca Hoffmann, Sara Merino-Aceituno
      Emergence in biology and social sciences
      Jason D. Lotay
      Lagrangian mean curvature flow
      Leo Storme
      Finite geometries: pure mathematics close to applications
      Francesca Arici, Bram Mesland
      Describing distance: from the plane to spectral triples
      Martijn Caspers
      Quantum symmetry
      Fadoua Balabdaoui, Yulia Kulagina
      The Enigma behind the Good–Turing formula
      Anna Haensch
      Reflections on hyperbolic space
      Isaac Goldbring
      Ultrafilter methods in combinatorics
      Gandalf Lechner
      Zopfgruppen, die Yang–Baxter-Gleichung und Unterfaktoren
      Baptiste Rognerud
      Invitation to quiver representation and Catalan combinatorics
      Po-Ling Loh
      Searching for structure in complex data: A modern statistical quest
      David Kerr
      C∗-algebras: structure and classification
      Sara Lamboglia, Martin Ulirsch
      From the dollar game to the Riemann-Roch Theorem
      Steven Rayan, Laura P. Schaposnik
      Higgs bundles without geometry
      Behrend Heeren, Martin Rumpf
      Shape space - a paradigm for character animation in computer graphics
      Joshua Zahl
      Rotating needles, vibrating strings, and Fourier summation
      Moritz Weber
      Quantum symmetry
      Christian Berg
      Determinacy versus indeterminacy
      Jayadev S. Athreya, David Aulicino
      Vertex-to-Self Trajectories on the Platonic Solids
      Gianluca Finocchio
      Random matrix theory: Dyson Brownian motion
      Holger Kammeyer, Roman Sauer
      From Betti numbers to l2-Betti numbers
      Martin J. Gander
      Is it possible to predict the far future before the near future is known accurately?
      Jan-Bernhard Kordaß
      The Interaction of Curvature and Topology
      barbara Kaltenbacher, Igor Kukavica, Irena Lasiecka, Roberto Triggianti, Amjad Fuffaha, Justin Weber
      The Mathematics of Fluids and Solids
      Jake Fillman, Tom van den Boom
      A surprising connection between quantum mechanics and shallow water waves
      Daniel Zelazo, Shiyu Zhao
      Formation Control and Rigidity Theory
      Ana Khukhro
      Expander graphs and where to find them
      Simon Arridge, Maarten de Hoop, Peter Maass, Ozan Öktem, Carola Schönlie, Michael Unser
      Deep Learning and Inverse Problems
      Jan Martin Nordbotten
      Mixed-dimensional models for real-world applications
      Pietro Milici
      Touching the transcendentals: tractional motion from the birth of calculus to future perspectives
      Loïc Petitgirard
      Analogue mathematical instruments: Examples from the “theoretical dynamics” group (France, 1948–1964)
      Rita Jiménez Rolland, Miguel A. Xicoténcatl
      Configuration spaces and braid groups
      Tereza Klimošová
      Limits of graph sequences
      Paulo Oliva
      On Logic, Choices and Games
      Barbara Kaltenbacher, Rainer Brunnhuber
      Nonlinear Acoustics
      Volker Betz
      Random permutations
      Hugo Duminil-Copin
      Counting self-avoiding walks on the hexagonal lattice
      A. S. Detinko, D. L. Flannery, A. Hulpke
      Algebra, matrices, and computers
      Jonathan Rosenberg, David Wraith
      Positive Scalar Curvature and Applications
      Hector Pasten
      Diophantine equations and why they are hard
      Martin Buhmann, Janin Jäger
      On radial basis functions
      Ralf Schiffler
      Snake graphs, perfect matchings and continued fractions
      Nicolai Baldin
      Estimating the volume of a convex body
      Liran Rotem
      Mixed volumes and mixed integrals
      Filippo Santambrogio
      A short story on optimal transport and its many applications
      Sebastian Schönnenbeck
      Number theory in quantum computing
      Matthias Morzfeld, Sebastian Reich
      Data assimilation: mathematics for merging models and data
      Claus Hertling
      Geometry behind one of the Painlevé III differential equations
      Antonio Lerario
      The codimension
      Marius Tucsnak
      The mathematics of aquatic locomotion
      Erwan Brugallé, Ilia Itenberg, Kristin Shaw, Oleg Viro
      Tropical geometry
      Alex Barnett
      Fast Solvers for Highly Oscillatory Problems
      Greg Lupton, John Oprea, José Gabriel Carrasquel Vera
      Topological Complexity, Robotics and Social Choice
      Thomas Sauer
      Prony’s method: an old trick for new problems
      Colva M. Roney-Dougal
      Computing with symmetries
      Piotr Sułkowski
      Topological recursion
      Anna Seigal
      The Algebraic Statistics of an Oberwolfach Workshop
      Jean-Pierre Tignol
      Solving quadratic equations in many variables
      Chi-Wang Shu
      Mathematics plays a key role in scientific computing
      Mauricio Bustamante, Jan-Bernhard Kordaß
      Spaces of Riemannian metrics
      Shaula Fiorelli Vilmart, Gilles Vilmart
      Computing the long term evolution of the solar system with geometric numerical integrators
      Justin Solomon
      Computational Optimal Transport
      Justyna Szpond
      A few shades of interpolation
      George Hagedorn, Caroline Lasser
      Molecular quantum dynamics
      Marco Radeschi
      Closed geodesics on surfaces and Riemannian manifolds
      Christian Engwer, Markus Knappitsch
      Mathematische Modellierung von Krebswachstum
      Michael Baake, David Damanik, Uwe Grimm
      Aperiodic Order and Spectral Properties
      Lukas Pottmeyer
      News on quadratic polynomials
      Felix Günther
      Winkeltreue zahlt sich aus
      Jacob Bedrossian
      Towards a Mathematical Theory of Turbulence in Fluids
      Laurent Bartholdi
      Profinite groups
      Dietmar Gallistl
      The adaptive finite element method
      Steven Klee
      Footballs and donuts in four dimensions
      Nikolai Nowaczyk
      The Willmore Conjecture
      Lior Bary-Soroker
      Prime Tuples in Function Fields
      Rafael Guglielmetti, Matthieu Jacquemet
      Polyhedra and commensurability
      Manfred Deistler, Andreas Graef
      Fokus-Erkennung bei Epilepsiepatienten mithilfe moderner Verfahren der Zeitreihenanalyse
      Robert Altmann, Jan Heiland
      Wie steuert man einen Kran?
      Anthony T Patera, Karsten Urban
      High performance computing on smartphones
      Eugenio Giannelli, Jay Taylor
      Symmetry and characters of finite groups
      Maria Dostert, Stefan Krupp, Jan Hendrick Rolfes
      Das Problem der Kugelpackung
      Tomasz Szemberg
      On the containment problem
      Éric Fusy
      Random sampling of domino and lozenge tilings
      Magnus Egerstedt
      Swarming robots
      Ulrich Krähmer
      From computer algorithms to quantum field theory: an introduction to operads
      Juanjo Rué
      Domino tilings of the Aztec Diamond
      Sebastian Funk
      The mystery of sleeping sickness – why does it keep waking up?
      Antti Knowles
      Quantum diffusion
      Amanda Swan, Albert Murtha
      Modelling the spread of brain tumours
      J. Marron
      Visual Analysis of Spanish Male Mortality
      Christopher Sangwin
      Curriculum development in university mathematics: where mathematicians and education collide
      Jürg Kramer, Anna-Maria Pippich
      Special values of zeta functions and areas of triangles
      Victoria Powers
      How to choose a winner : the mathematics of social choice
      Valentina Kiritchenko, Evgeny Smirnov, Vladlen Timorin
      Ideas of Newton-Okounkov bodies
      Ben Schweizer
      Darcy’s law and groundwater flow modelling
      Raluca Eftimie
      Modelling communication and movement: from cells to animals and humans
      Tom Solomon
      Chaos and chaotic fluid mixing
      Thorsten Holm
      Friezes and tilings
      George Willis
      Zero-dimensional symmetry
      Christine Breiner
      Minimizing energy
      Diana Davis
      Billiards and flat surfaces
      Peter Benner, Hermann Mena, René Schneider
      Drugs, herbicides, and numerical simulation
      Gregory Knese
      Operator theory and the singular value decomposition
      Alain Valette
      The Kadison-Singer problem
      Ragnar-Olaf Buchweitz, Eleonore Faber
      Swallowtail on the shore
      Howell Tong
      Statistics and dynamical phenomena
      Brian Harbourne, Thomas Szemberg
      Arrangements of lines
      Bruce Reznick
      What does ">" really mean?
      Harald Helfgott
      The ternary Goldbach Problem
      Wolfgang Lerche
      Matrixfaktorisierungen
      John E. McCarthy
      Dirichlet Series

      Mathematical subjects

      Algebra and Number Theory
      Analysis
      Didactics and Education
      Discrete Mathematics and Foundations
      Geometry and Topology
      Numerics and Scientific Computing
      Probability Theory and Statistics

      Connections to other fields

      Chemistry and Earth Science
      Computer Science
      Engineering and Technology
      Finance
      Humanities and Social Sciences
      Life Science
      Physics
      Reflections on Mathematics

      These icons are available under the CC BY-SA 4.0 license. Please feel free to use them to classify your own content.
      The vector icons can be downloaded here.