Graphical designs and extremal combinatorics
| Autor: | Konstantin Golubev |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
Extremal combinatorics
Design Graph Mathematics - Spectral Theory Graphical design FOS: Mathematics Discrete Mathematics and Combinatorics Mathematics - Combinatorics Graph Laplacian Sampling Spectral Theory (math.SP) Mathematics Discrete mathematics Numerical Analysis Algebra and Number Theory Mean value Eigenfunction Hypercube graph 05B99 05C50 05C70 35P05 05C35 05C69 Laplacian Geometry and Topology Combinatorics (math.CO) Isoperimetric inequality Laplace operator Graph product MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Linear Algebra and its Applications, 604 |
| ISSN: | 0024-3795 1873-1856 |
| DOI: | 10.3929/ethz-b-000428111 |
| Popis: | A graphical design is a proper subset of vertices of a graph on which many eigenfunctions of the Laplacian operator have mean value zero. In this paper, we show that extremal independent sets make extremal graphical designs, that is, a design on which the maximum possible number of eigenfunctions have mean value zero. We then provide examples of such graphs and sets, which arise naturally in extremal combinatorics. We also show that sets which realize the isoperimetric constant of a graph make extremal graphical designs, and provide examples for them as well. We investigate the behavior of graphical designs under the operation of weak graph product. In addition, we present a family of extremal graphical designs for the hypercube graph. Linear Algebra and its Applications, 604 ISSN:0024-3795 ISSN:1873-1856 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect