Graphical designs and gale duality

DOI10.1007/S10107-022-01861-0MaRDI QIDQ6160280zbMATHWikidataFDO

Authors Catherine Babecki, Rekha Thomas

Publication date 23 June 2023

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

polytopesHamming codequadrature rulesGale dualitygraph Laplacianstable setsgraph samplinggraphical designseigenpolytopes

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Graph theory (including graph drawing) in computer science (68R10) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Structural characterization of families of graphs (05C75) Graph designs and isomorphic decomposition (05C51) Gale and other diagrams (52B35)

Abstract: A graphical design is a subset of graph vertices such that the weighted averages of certain graph eigenvectors over the design agree with their global averages. We use Gale duality to show that positively weighted graphical designs in regular graphs are in bijection with the faces of a generalized eigenpolytope of the graph. This connection can be used to organize, compute and optimize designs. We illustrate the power of this tool on three families of Cayley graphs -- cocktail party graphs, cycles, and graphs of hypercubes -- by computing or bounding the smallest designs that average all but the last eigenspace in frequency order.

Recommendations

• Generalized designs on graphs: Sampling, spectra, symmetries
• Graphical designs and extremal combinatorics
• Codes, cubes, and graphical designs
• Optimal and extremal graphical designs on regular graphs associated with classical parameters
• An enumeration of graphical designs

Cites work

• scientific article; zbMATH DE number 1601795 (Why is no real title available?)
• scientific article; zbMATH DE number 3121295 (Why is no real title available?)
• scientific article; zbMATH DE number 3499621 (Why is no real title available?)
• scientific article; zbMATH DE number 3552764 (Why is no real title available?)
• scientific article; zbMATH DE number 3634287 (Why is no real title available?)
• scientific article; zbMATH DE number 1054726 (Why is no real title available?)
• scientific article; zbMATH DE number 4119096 (Why is no real title available?)
• scientific article; zbMATH DE number 782048 (Why is no real title available?)
• scientific article; zbMATH DE number 3894973 (Why is no real title available?)
• scientific article; zbMATH DE number 3349875 (Why is no real title available?)
• scientific article; zbMATH DE number 2232233 (Why is no real title available?)
• A graph discretization of the Laplace-Beltrami operator
• An introduction to divisible codes
• Codes, cubes, and graphical designs
• Convex Polytopes
• Discrete Signal Processing on Graphs
• Discrete Signal Processing on Graphs: Sampling Theory
• Efficient Sampling Set Selection for Bandlimited Graph Signals Using Graph Spectral Proxies
• Eigenpolytopes of Distance Regular Graphs
• Eigenvectors of Distance-Regular Graphs
• Error detecting and error correcting codes
• Explicit Concentrators from Generalized N-Gons
• Fast Graph Sampling Set Selection Using Gershgorin Disc Alignment
• From graph to manifold Laplacian: the convergence rate
• Generalized designs on graphs: Sampling, spectra, symmetries
• Geometry of cuts and metrics
• Graph Laplacians and their convergence on random neighborhood graphs
• Graphical designs and extremal combinatorics
• Introduction to graph signal processing
• Lectures on Polytopes
• Numerical integration on graphs: Where to sample and how to weigh
• Sampling in Paley-Wiener spaces on combinatorial graphs
• Sampling of Graph Signals With Successive Local Aggregations
• Signals on Graphs: Uncertainty Principle and Sampling
• Spectra of graphs
• Stable high-order quadrature rules with equidistant points
• The maximum numbers of faces of a convex polytope
• Wavelets on graphs via spectral graph theory
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• polymake: a framework for analyzing convex polytopes

Cited in

(5)

• Quadrature formulas on combinatorial graphs
• Optimal and extremal graphical designs on regular graphs associated with classical parameters
• Graphical designs and extremal combinatorics
• Codes, cubes, and graphical designs
• Eigenpolytope Universality and Graphical Designs

This page was built for publication: Graphical designs and gale duality

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