This paper investigates spectral minimal partitions for weighted graphs, thus extending the extensive class of results that are currently available on domains and, to a lesser extent, manifolds and metric graphs. We provide a rigorous framework for analyzing graph Laplacians under Dirichlet, Neumann, and boundaryless energy formulations; a central focus of the study is establishing existence theorems for minimal partitions. While existence is straightforward for finite connected graphs due to the finiteness of the class of admissible partitions, infinite graphs require advanced topological and functional-analytic machinery. Specifically, we introduce the notion of canonical compactifiability, which relates to compact embeddings and uniform Poincar\'e-type constants for Neumann and boundaryless energies; and an appropriate notion of subgraph convergence. In this way, we can relax the spectral minimal problem on infinite graphs by reducing it to the study of finite graphs; and can, thus, guarantee that optimal spectral energies are actually attained by appropriate partitions even in non-compact settings.
This thesis investigates two central directions in algebraic graph theory, with an emphasis on spectral methods: spectral determination of graphs and transitivity properties of generalized-Hamming graphs and their complements. The first part focuses on graphs that are determined by the spectra of associated matrices. We study spectral determination with respect to the adjacency, Laplacian, signless Laplacian, and normalized Laplacian matrices, with particular emphasis on the adjacency spectrum. We survey existing results on graphs determined by their spectrum and develop new proof techniques for establishing spectral uniqueness. In particular, we present new proofs for the spectral characterization of complete bipartite graphs and Tur\'{a}n graphs, as well as some new results related to the spectral characterization of the important family of strongly regular graphs. In addition, we introduce a new family of graphs, called \emph{the graphs of pyramids}, and prove that they are determined by their adjacency spectrum using tools from matrix analysis, such as Cauchy's interlacing theorem and Schur complements. The second part of the thesis studies generalized-Hamming graphs, a family of Cayley graphs that generalize the sub-family of Hamming graphs, and their complements. We classify the parameters for which these graphs are edge-transitive or even distance-transitive. Our analysis combines spectral methods, group-theoretic arguments, and techniques from the theory of association schemes. As an application, we derive closed-form expressions for the Lov\'{a}sz $\vartheta$-function of generalized-Hamming graphs and their complements whenever either the graph or its complement is edge-transitive. Overall, the results demonstrate how spectral methods provide powerful tools for understanding the structure and symmetry of graphs, and they suggest several directions for further research.
We study the heat content for Laplacians on compact, finite metric graphs with Dirichlet conditions imposed at the “boundary” (i.e., a given set of vertices) and standard conditions imposed elsewhere. We prove a closed formula of combinatorial flavor, as it is expressed as a sum over all paths starting and ending at boundary vertices. By delivering a small-time asymptotic expansion, our approach yields information on crucial geometric quantities of the metric graph, much in the spirit of the celebrated corresponding result for manifolds due to Gilkey–van den Berg; but unlike other known formulae based on different methods, ours holds for all times
$$t>0$$
t
>
0
and it displays a stronger decay rate in the short time limit. Furthermore, we prove new surgery principles for the heat content and use them to derive comparison principles for the heat content between metric graphs of different topology.
Unknown authors· Annales de l'Institute Henri...· 0 citations
The main theorem gives the asymptotic sampling distribution and enumeration formulae for configurations, and accommodates forbidden edges, and enables the sampling of edge-colored graphs with prescribed degree sequences for each color class by constructing the colored subgraphs one at a time.
I. Kryven, Rik Versendaal, M. D. Vries· 0 citations
We develop a constructive method for solving semilinear elliptic equations $\Delta u(x)=f(x,u(x))$ on locally finite, connected infinite graphs with layered structure. Using Eidelheit's theorem, we establish coupling criteria ensuring that arbitrary initial-layer data extend to global solutions for every $f$. We apply combinatorial criteria to prove solvability on leafless infinite trees, integer lattices, the triangular and hexagonal lattices, and a Cayley graph of the discrete Heisenberg group. We further establish solvability for a broad class of Cayley graphs of semidirect products $G\cong\mathbb Z\ltimes_\theta H$. In particular, $\Delta u=e^u$ has infinitely many solutions on $\mathbb Z^2$, but none of finite energy. We also extend the method to the bi-Laplacian under two-step coupling conditions, to the $p$-Laplacian under a unique-neighbor condition, and to magnetic Laplacians.
In this thesis, we study the spectral properties of dynamically defined aperiodic metric and discrete graphs. Our goal is to determine to what extent spectral properties of discrete one-dimensional ergodic Schr\"odinger operators persist when the aperiodicity is manifested through the geometry rather than through a potential. The graphs considered here are inspired by one-dimensional aperiodic tilings, and are called tiling graphs and decorated $\mathbb{Z}$-graphs. For a large family of metric tiling graphs equipped with the standard Laplacian, we show that the spectrum is of zero Lebesgue measure, and is a generalized Cantor set up to a possible discrete set of energies. For decorated $\mathbb{Z}$-graphs, we further show that for a Baire-generic and Lebesgue almost-sure choice of the decoration edge lengths, the spectrum is a generalized Cantor set. We then study the integrated density of states (IDS) for metric and discrete decorated $\mathbb{Z}$-graphs. We prove a gap labelling theorem, which characterizes the set of possible values taken by the IDS inside spectral gaps. We show that the gap labels are contained in the Schwartzman group associated with the dynamical system generating the graph, up to a geometric scaling factor. Lastly, we consider the Dry Ten Martini Problem for discrete Sturmian decorated $\mathbb{Z}$-graphs, asking whether all possible values predicted by the gap labelling theorem are indeed attained by the IDS inside spectral gaps. We answer this question negatively, by identifying a large set of gap labels which are not attained due to jump discontinuities of the IDS. We then show that away from these jump discontinuities, the periodic approximants for Sturmian graphs display the same combinatorial structure as the standard Sturmian Hamiltonians, and use this to obtain an explicit characterization of the realized gap labels for Sturmian comb graphs.
Let $(M,g)$ be a connected, compact, $n$-dimensional Riemannian manifold with $\operatorname{Ric}(M,g)\geq-(n-1)\kappa g$. We introduce a weighted combinatorial Laplacian on $\varepsilon$-discretizations of $M$ and prove a spectral comparison theorem between the weighted graph Laplacian and the Laplace-Beltrami operator. More precisely, the eigenvalues of the two operators are uniformly comparable with constants depending only on $n,\kappa,\varepsilon$, independently of the injectivity radius. As an application, we prove spectral stability under measured Gromov-Hausdorff convergence. We also recover the Schoen-Wolpert-Yau inequality using the weighted discretization on families of pinching genus-$2$ hyperbolic surfaces.
Aditya Tiwari· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
