Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Graphical designs and gale duality

  • Full Length Paper
  • Series B
  • Published:
Mathematical Programming Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14

Similar content being viewed by others

References

  1. Anis, A., Gadde, A., Ortega, A.: Effcient sampling set selection for bandlimited graph signals using graph spectral proxies. IEEE Trans. on Signal Process., a Publication of the IEEE Signal Process. Soci. 64(14), 3775–3789 (2016)

    Article  MATH  Google Scholar 

  2. Alon, N., Milman, V.D.: \(\lambda \)1, Isoperimetric inequalities for graphs, and superconcentrators. J. of Comb. Theory 38(1), 73–88 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  3. Babecki, C.: Cubes, codes, and graphical designs. J. Fourier Anal. Appl. 27(81), 1–34 (2021)

    MathSciNet  MATH  Google Scholar 

  4. Bai, Y., et al.: Fast graph sampling set selection using Gershgorin disc alignment. IEEE Trans. on Signal Process. 68, 2419–2434 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  5. Brouwer, A.E., Haemers, W.H.: Spectra of Graphs. Springer, New York, NY (2012)

    Book  MATH  Google Scholar 

  6. Burago, D., Ivanov, S., Kurylev, Y.: A graph discretization of the Laplace-Beltrami operator. In: Journal of Spectral Theory. 4 (2013)

  7. Blake, I.F., Mullin, R.C.: The Mathematical Theory of Coding. Academic Press Inc, New York (1975)

    MATH  Google Scholar 

  8. Bonisoli, A.: Every equidistant linear code is a sequence of dual Hamming codes. Ars Combin. 18, 181–186 (1984)

    MathSciNet  MATH  Google Scholar 

  9. Caratheodory, C.: Über den Variabilitätsbereich der Fourier’schen Konstanten von positiven harmonischen Funktionen. : Rendiconti del Circolo Matematico di Palermn. 32(1), 193–217 (1911). (in German)

    Article  MATH  Google Scholar 

  10. Chan, A., Godsil, C.D.: Symmetry and eigenvectors. In: Graph Symmetry (Montreal, PQ, 1996). Vol. 497. NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci. pp. 75–106. Kluwer Acad. Publ., Dordrecht (1997)

  11. Chen, S., et al.: Discrete signal processing on graphs: sampling theory. IEEE Trans. on Signal Process. 63(24), 6510–6523 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  12. Delsarte, P.: An Algebraic Approach to the Association Schemes of Coding Theory. Philips Res. Repts Suppl. 10, (1973)

  13. Deza, M.M., Laurent, M.: Geometry of Cuts and Metrics. Vol. 15 Algorithms and Combinatorics. Springer-Verlag, Berlin (1997)

    Book  MATH  Google Scholar 

  14. Gale, D.: Neighboring vertices on a convex polyhedron. In: Linear Inequalities and Related System. Annals of Mathematics Studies, no. 38. Princeton University Press, Princeton, N.J., pp. 255–263 (1956)

  15. Gawrilow, E., Joswig, M.: polymake: A framework for analyzing convex polytopes. In: Polytopes|Combinatorics and Computation (Ober-wolfach, 1997). Vol. 29. DMV Sem. pp. 43–73. Birkhäuser, Basel (2000)

  16. Godsil, C.D.: Graphs, groups and polytopes. In: Combinatorial Mathematics (Proc. Internat. Conf. Combinatorial Theory, Australian Nat. Univ., Canberra, 1977). Vol. 686. Lecture Notes in Math. pp. 157–164. Springer, Berlin (1978)

  17. Godsil, C.D.: Euclidean geometry of distance regular graphs. In: Surveys in Combinatorics, (Stirling). Vol. 218. London Math. Soc. Lecture Note Ser. pp. 1–23. Cambridge Univ. Press, Cambridge (1995)

  18. Godsil, C.D.: Eigenpolytopes of distance regular graphs. Canad. J. Math. 50(4), 739–755 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  19. Golubev, K.: Graphical designs and extremal combinatorics. Linear Algebra and its Appl. 604, 490–506 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  20. Grünbaum, B.: Convex Polytopes. Second. Vol. 221. Graduate Texts in Mathematics. Springer-Verlag, New York (2003)

    Google Scholar 

  21. Haemers, W.H.: Hoffman’s ratio bound. (2021). arXiv: 2102.05529

  22. Hein, M., Audibert, J.-Y., von Luxburg, U.: Graph Laplacians and their convergence on random neighborhood graphs. Journal of Machine Learning Reseach. 8 (2007)

  23. Hamming, R.W.: Error detecting and error correcting codes. The Bell Syst. Technical J. 29(2), 147–160 (1950)

    Article  MathSciNet  MATH  Google Scholar 

  24. Hoffman, A.J.: On eigenvalues and colorings of graphs. In: Graph Theory and Its Applications. Ed. by B. Harris. (1970)

  25. Huybrechs, D.: Stable high-order quadrature rules with equidistant points. J. of Comput. and Appl. Math. 231(2), 933–947 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  26. Hammond, P.K., Vandergheynst, P., Gribonval, R.: Wavelets on graphs via spectral graph theory. Appl. and Comput. Harmonic Anal. 30(2), 129–150 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  27. Linderman, G.C., Steinerberger, S.: Numerical integration on graphs: where to sample and how to weigh. Math. of Comput. 89(324), 1933–1952 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  28. Marques, A.G., et al.: Sampling of graph signals With successive local aggregations. IEEE Trans. on Signal Process. 64(7), 1832–1843 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  29. MATLAB. version 9.9.0 (R2020b). Natick, Massachusetts: The Math-Works Inc., (2020)

  30. McConnell, B.D.S.: Spectral realizations of graphs. (2020). https://daylateanddollarshort.com/mathdocs/Spectral-Realizations-of-Graphs.pdf

  31. McMullen, P.: The maximum numbers of faces of a convex polytope. Mathematika 17(2), 179–184 (1970)

    Article  MathSciNet  MATH  Google Scholar 

  32. Ortega, A., et al.: Graph signal processing: overview, challenges, and applications. Proc. of the IEEE. 106(5), 808–828 (2018)

    Article  Google Scholar 

  33. Ortega, A.: Introduction to Graph Signal Processing. Cambridge University Press, Cambridge, UK (2022)

  34. Pesenson, I.Z.: Sampling in Paley-Wiener spaces on combinatorial graphs. Trans. of the Am. Math. Soc. 360(10), 5603–5627 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  35. Powers, D.L., Licata, C.: A surprising property of some regular polytopes. Tech. rep. Clarkson University, Potsdam NY, Dept Of Mathematics and Computer Science (1986)

  36. Powers, D.L.: The Petersen polytopes. Tech. rep. Clarkson University, Potsdam NY, Dept Of Mathematics and Computer Science (1986)

  37. Powers, D.L.: Eigenvectors of distance-regular graphs. SIAM J. Matrix Anal. Appl. 9(3), 399–407 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  38. Sureda, A.P., Pfeifle, J.: Graph operations and Laplacian eigenpolytopes. In: VII Jornadas de Matemática Discreta y Algorítmica, pp. 505–516 (2010)

  39. Rooney, B.: Spectral Aspects of Cocliques in Graphs. University of Waterloo (2014)

  40. Sagan, B.E.: The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions, vol. 203, 2nd edn. Springer, New York (2001)

    Book  MATH  Google Scholar 

  41. Serre, J.-P.: Linear Representations of Finite Groups. Graduate Texts in Mathematics, Vol. 42. Translated from the second French edition by Leonard L. Scott. Springer-Verlag, New York-Heidelberg (1977)

  42. Singer, A.: From graph to manifold Laplacian: the convergence rate. Appl. and Comput. Harmonic Anal. 21, 128–134 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  43. Sandryhaila, A., Moura, J.M.F.: Discrete signal processing on graphs. IEEE Trans. on Signal Process. 61(7), 1644–1656 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  44. Steinerberger, S., Thomas, R.R.: Random Walks, Equidistribution and Graphical Designs. (2022). arXiv: 2206.05346

  45. Steinerberger, S.: Generalized designs on graphs: sampling, spectra, symmetries. J. of Graph Theory 93(2), 253–267 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  46. Tanaka, Y., et al.: Sampling signals on graphs: From theory to applications. IEEE Signal Process. Magazine 37(6), 14–30 (2020)

    Article  Google Scholar 

  47. Tanner, R.M.: Explicit concentrators from generalized n-gons. SIAM J. on Algebr. and Discrete Methods. 5(3), 287–293 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  48. Tsitsvero, M., Barbarossa, S., Di Lorenzo, P.: Signals on graphs: Uncertainty principle and sampling. IEEE Trans. on Signal Process.; a Publication of the IEEE Signal Process. Soc. 64(18), 4845–4860 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  49. Ward, H.N.: An introduction to divisible codes. Des. Codes Cryptogr. 17(1–3), 73–79 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  50. Winter, M.: Eigenpolytopes, spectral polytopes and edge-transitivity. (2020). arXiv: 2009.02179 [math.MG]

  51. Winter, M.: Spectral Realizations of Symmetric Graphs, Spectral Polytopes and Edge-Transitivity. Technische Universität Chemnitz (2021)

  52. Ziegler, G.M.: Lectures on Polytopes. Vol. 152. Graduate Texts in Mathematics. Springer-Verlag, New York (1995)

    Google Scholar 

Download references

Acknowledgements

We thank Sameer Agarwal and Stefan Steinerberger for many useful discussions and suggestions. We also thank Chris Lee and David Shiroma, undergraduates at the University of Washington, who worked with us in Autumn 2021 on graphical designs. They independently discovered the construction in Bonisoli’s theorem on linear codes which provides strong bounds on extremal designs in the graphs of hypercubes. We explain this result in Sect. 5.

Author information

Authors and Affiliations

  1. Department of Mathematics, University of Washington, Box 354350, Seattle, WA, 98195, USA

    Catherine Babecki & Rekha R. Thomas

Authors
  1. Catherine Babecki
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Rekha R. Thomas
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Rekha R. Thomas.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Research partially supported by the Walker Family Endowed Professorship in Mathematics at the University of Washington.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Babecki, C., Thomas, R.R. Graphical designs and gale duality. Math. Program. 200, 703–737 (2023). https://doi.org/10.1007/s10107-022-01861-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-022-01861-0

Keywords

Mathematics Subject Classification

Search

Navigation