Graphical designs and extremal combinatorics
Copyright policy )Graphical designs and extremal combinatorics
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.
Latest Update: error fix in the references
- ETH Zurich Switzerland
Extremal problems in graph theory, sampling, Design, Graphs and linear algebra (matrices, eigenvalues, etc.), Graph operations (line graphs, products, etc.), design, General topics in linear spectral theory for PDEs, Graph, Mathematics - Spectral Theory, 05B99, 05C50, 05C70, 35P05, 05C35, 05C69, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), Graph; Laplacian; Graph Laplacian; Sampling; Design, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), graph Laplacian, FOS: Mathematics, Mathematics - Combinatorics, Graph Laplacian, Combinatorics (math.CO), Laplacian, Sampling, Spectral Theory (math.SP), Designs and configurations
Extremal problems in graph theory, sampling, Design, Graphs and linear algebra (matrices, eigenvalues, etc.), Graph operations (line graphs, products, etc.), design, General topics in linear spectral theory for PDEs, Graph, Mathematics - Spectral Theory, 05B99, 05C50, 05C70, 35P05, 05C35, 05C69, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), Graph; Laplacian; Graph Laplacian; Sampling; Design, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), graph Laplacian, FOS: Mathematics, Mathematics - Combinatorics, Graph Laplacian, Combinatorics (math.CO), Laplacian, Sampling, Spectral Theory (math.SP), Designs and configurations
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).7 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!