Graphical designs and extremal combinatorics

DOI10.1016/J.LAA.2020.07.012zbMATH Open1446.05018arXiv1910.05966OpenAlexW3040906459MaRDI QIDQ2197221FDOQ2197221

Authors: Konstantin Golubev 

Publication date: 28 August 2020

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1910.05966

Recommendations

• Optimal and extremal graphical designs on regular graphs associated with classical parameters
• Graphical designs and gale duality
• Codes, cubes, and graphical designs
• Generalized designs on graphs: Sampling, spectra, symmetries
• scientific article; zbMATH DE number 812056

zbMATH Keywords

samplingdesignLaplaciangraph Laplacian

Mathematics Subject Classification ID

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)

Cites Work

• Eigenvalues and expanders
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• On the Shannon capacity of a graph
• Title not available (Why is that?)
• The density of sets avoiding distance 1 in Euclidean space
• Ramanujan complexes and high dimensional expanders
• Sharp \(L^1\)-Poincaré inequalities correspond to optimal hypersurface cuts
• A new proof of the Erdős-Ko-Rado theorem for intersecting families of permutations
• On the maximum number of permutations with given maximal or minimal distance
• The Kronecker Product of Graphs
• Erdős-Ko-Rado theorems. Algebraic approaches
• A survey of the theory of hypercube graphs
• Isoperimetric inequalities in simplicial complexes
• Explicit Concentrators from Generalized N-Gons
• A note on the isoperimetric constant
• Title not available (Why is that?)
• Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Title not available (Why is that?)
• On the measure of intersecting families, uniqueness and stability
• Sampling in Paley-Wiener spaces on combinatorial graphs
• Spherical sets avoiding a prescribed set of angles
• Optimal asymptotic bounds for spherical designs
• Intersecting families of permutations
• Graph products, Fourier analysis and spectral techniques
• Spectral bounds for the independence ratio and the chromatic number of an operator
• Optimal Numerical Integration on a Sphere
• Higher dimensional discrete Cheeger inequalities
• On the spectrum of the derangement graph
• Title not available (Why is that?)
• Local spectral expansion approach to high dimensional expanders. I: Descent of spectral gaps
• Generalized designs on graphs: Sampling, spectra, symmetries
• Lower bounds for the measurable chromatic number of the hyperbolic plane

Cited In (8)

• Codes, cubes, and graphical designs
• Title not available (Why is that?)
• Graphical designs and gale duality
• Optimal and extremal graphical designs on regular graphs associated with classical parameters
• Perfect colorings of the infinite square grid: coverings and twin colors
• Eigenpolytope Universality and Graphical Designs
• Title not available (Why is that?)
• Title not available (Why is that?)

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)