Search Clay Mathematics Institute

  • About
    About
    • About
    • History
    • Principal Activities
    • Who’s Who
    • CMI Logo
    • Policies
  • Programs & Awards
    Programs & Awards
    • Programs & Awards
    • Funded programs
    • Fellowship Nominations
    • Clay Research Award
    • Dissemination Award
  • People
  • The Millennium Prize Problems
    The Millennium Prize Problems
    • The Millennium Prize Problems
    • Birch and Swinnerton-Dyer Conjecture
    • Hodge Conjecture
    • Navier-Stokes Equation
    • P vs NP
    • Poincaré Conjecture
    • Riemann Hypothesis
    • Yang-Mills & the Mass Gap
    • Rules for the Millennium Prize Problems
  • Online resources
    Online resources
    • Online resources
    • Books
    • Video Library
    • Lecture notes
    • Collections
      Collections
      • Collections
      • Euclid’s Elements
      • Ada Lovelace’s Mathematical Papers
      • Collected Works of James G. Arthur
      • Klein Protokolle
      • Notes of the talks at the I.M.Gelfand Seminar
      • Quillen Notebooks
      • Riemann’s 1859 Manuscript
  • Events
  • News

Home — Resource — Expanders — how to find them, and what to find in them

Expanders — how to find them, and what to find in them

Abstract: A graph G = (V,E) is called an expander if every vertex subset U of size up to |V|/2 has an external neighborhood whose size is comparable to |U|. Expanders have been a subject of intensive research for more than three decades and have become one of the central notions of modern graph theory.

We first discuss the above definition of an expander and its alternatives. Then we present examples of families of expanding graphs and state basic properties of ex- panders. Next, we introduce a way to argue that a given graph contains a large expand- ing subgraph. Finally we research properties of expanding graphs, such as existence of small separators, of cycles (including cycle lengths), and embedding of large minors.

Details

Speaker: Michael Krivelevich

Venue: British Combinatorial Conference 2019, University of Birmingham

Downloads

Expanders -- how to find them, and what to find in them
  • Privacy Policy
  • Contact CMI

© 2025 Clay Mathematics Institute

Site by One