Graphical designs and gale duality

DOI10.1007/S10107-022-01861-0zbMATH Open1517.05113arXiv2204.01873WikidataQ114228479 ScholiaQ114228479MaRDI QIDQ6160280FDOQ6160280

Rekha Thomas, Catherine Babecki

Publication date: 23 June 2023

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

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.

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

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

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)

Cites Work

• polymake: a framework for analyzing convex polytopes
• Wavelets on graphs via spectral graph theory
• Title not available (Why is that?)
• Lectures on Polytopes
• Spectra of graphs
• Error Detecting and Error Correcting Codes
• From graph to manifold Laplacian: the convergence rate
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Geometry of cuts and metrics
• Convex Polytopes
• The maximum numbers of faces of a convex polytope
• Explicit Concentrators from Generalized N-Gons
• Stable high-order quadrature rules with equidistant points
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Title not available (Why is that?)
• Title not available (Why is that?)
• Sampling in Paley-Wiener spaces on combinatorial graphs
• Discrete Signal Processing on Graphs: Sampling Theory
• Title not available (Why is that?)
• A graph discretization of the Laplace-Beltrami operator
• Title not available (Why is that?)
• Title not available (Why is that?)
• Eigenvectors of Distance-Regular Graphs
• An introduction to divisible codes
• Discrete Signal Processing on Graphs
• Sampling of Graph Signals With Successive Local Aggregations
• Signals on Graphs: Uncertainty Principle and Sampling
• Efficient Sampling Set Selection for Bandlimited Graph Signals Using Graph Spectral Proxies
• Numerical integration on graphs: Where to sample and how to weigh
• Title not available (Why is that?)
• Eigenpolytopes of Distance Regular Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Codes, cubes, and graphical designs
• Graphical designs and extremal combinatorics
• Generalized designs on graphs: Sampling, spectra, symmetries
• Introduction to Graph Signal Processing
• Fast Graph Sampling Set Selection Using Gershgorin Disc Alignment

Cited In (3)

• Quadrature formulas on combinatorial graphs
• Optimal and extremal graphical designs on regular graphs associated with classical parameters
• 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)