Graphical designs and extremal combinatorics
From MaRDI portal
Publication:2197221
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76) General topics in linear spectral theory for PDEs (35P05) Designs and configurations (05B99)
Abstract: 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.
Recommendations
Cites work
- scientific article; zbMATH DE number 4004190 (Why is no real title available?)
- scientific article; zbMATH DE number 1943822 (Why is no real title available?)
- scientific article; zbMATH DE number 3337135 (Why is no real title available?)
- scientific article; zbMATH DE number 3349875 (Why is no real title available?)
- A new proof of the Erdős-Ko-Rado theorem for intersecting families of permutations
- A note on the isoperimetric constant
- A survey of the theory of hypercube graphs
- Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
- Eigenvalues and expanders
- Erdős-Ko-Rado theorems. Algebraic approaches
- Explicit Concentrators from Generalized N-Gons
- Generalized designs on graphs: Sampling, spectra, symmetries
- Graph products, Fourier analysis and spectral techniques
- Higher dimensional discrete Cheeger inequalities
- INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- Intersecting families of permutations
- Isoperimetric inequalities in simplicial complexes
- Local spectral expansion approach to high dimensional expanders. I: Descent of spectral gaps
- Lower bounds for the measurable chromatic number of the hyperbolic plane
- On the Shannon capacity of a graph
- On the maximum number of permutations with given maximal or minimal distance
- On the measure of intersecting families, uniqueness and stability
- On the spectrum of the derangement graph
- Optimal Numerical Integration on a Sphere
- Optimal asymptotic bounds for spherical designs
- Ramanujan complexes and high dimensional expanders
- Sampling in Paley-Wiener spaces on combinatorial graphs
- Sharp \(L^1\)-Poincaré inequalities correspond to optimal hypersurface cuts
- Spectral bounds for the independence ratio and the chromatic number of an operator
- Spherical sets avoiding a prescribed set of angles
- The Kronecker Product of Graphs
- The density of sets avoiding distance 1 in Euclidean space
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
Cited in
(8)- Perfect colorings of the infinite square grid: coverings and twin colors
- scientific article; zbMATH DE number 107837 (Why is no real title available?)
- Optimal and extremal graphical designs on regular graphs associated with classical parameters
- Codes, cubes, and graphical designs
- Graphical designs and gale duality
- scientific article; zbMATH DE number 812056 (Why is no real title available?)
- Eigenpolytope Universality and Graphical Designs
- scientific article; zbMATH DE number 5073492 (Why is no real title available?)
This page was built for publication: Graphical designs and extremal combinatorics
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2197221)
