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 — Codes and designs in Johnson graphs with high symmetry

Codes and designs in Johnson graphs with high symmetry

Abstract: The Johnson graph J(v,k) has, as vertices, all k-subsets of a v-set V, with two k-subsets adjacent if and only if they share k − 1 common elements of V. Subsets of vertices of J(v,k) can be interpreted as the blocks of an incidence structure, or as the codewords of a code, and automorphisms of J(v,k) leaving the subset invariant are then automorphisms of the corresponding incidence structure or code. This approach leads to interesting new designs and codes. For example, numerous actions of the Mathieu sporadic simple groups give rise to examples of Delandtsheer designs (which are both flag-transitive and anti-flag transitive), and codes with large minimum distance (and hence strong error-correcting properties). The paper surveys recent progress, explores links between designs and codes in Johnson graphs which have a high degree of symmetry, and discusses several open questions.

Details

Speaker: Cheryl Praeger

Venue: British Combinatorial Conference 2021

Downloads

Codes and designs in Johnson graphs with high symmetry
  • Privacy Policy
  • Contact CMI

© 2025 Clay Mathematics Institute

Site by One