eigenpolytopesGale dualitygraph Laplaciangraph samplinggraphical designsHamming codepolytopesquadrature rulesstable sets
Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph designs and isomorphic decomposition (05C51) Structural characterization of families of graphs (05C75) Gale and other diagrams (52B35) Graph theory (including graph drawing) in computer science (68R10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)
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
Cites work
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
- 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
- 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?)
- Introduction to graph signal processing
- Lectures on Polytopes
- Numerical integration on graphs: Where to sample and how to weigh
- polymake: a framework for analyzing convex polytopes
- 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
Cited in
(8)- Codes, cubes, and graphical designs
- Graphical designs and extremal combinatorics
- Optimal and extremal graphical designs on regular graphs associated with classical parameters
- Eigenpolytope Universality and Graphical Designs
- Quadrature formulas on combinatorial graphs
- Exact positive quadrature formulas on combinatorial graphs via local average sampling
- Spectrahedral geometry of graph sparsifiers
- Random walks, equidistribution 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)
