3
$\begingroup$

Let $G=(E,V)$ be a simple graph. The graph Laplacian is given by $$ L= D-A,$$ where $D$ is the degree matrix (diagonal matrix with entries corresponding to the degree of the vertex) and $A$ the adjacency matrix. Denote with $G_{nm}$ the $n\times m$ grid graph Example grid graph $G_{66}$. We like to label the vertices row by row with $1,2,...,m,m+1,...,m \cdot n$ . The Laplacian spectra of a grid graph is well understood. The eigenvalues are $$ \lambda_{ij} = 4\sin^2\left(\frac{(i-1)\pi}{2 n }\right)+4\sin^2\left(\frac{(j-1)\pi}{2 m }\right) $$ for $i\in\{1,...,n\}$ and $j\in\{1,...,m\}$. The corresponding eigenvectors $u_{ij}$ (with normalization $\langle u_{ij}, u_{ij}\rangle = 1$) are $$ u_{ij}:(x,y)\mapsto \frac{A_iB_j}{\sqrt{nm}}\cos\left[\left(x-\frac{1}{2}\right)\frac{i\pi}{n} \right] \cos\left[\left(y-\frac{1}{2}\right)\frac{j\pi}{m} \right] $$ for $x\in \{1,...,n\}$ and $y\in\{1,...,m\}$ where $A_i=1,B_j=1$, except $A_1=B_1 =\frac{1}{\sqrt{2}}$.

See: Pozrikidis, C., An introduction to grids, graphs, and networks, Oxford: Oxford University Press (ISBN 978-0-19-999672-8/hbk). xii, 284 p. (2014). ZBL1330.00004. - Chapter 3, spectra of lattices.

This can be easy understood since the problem factorizes - The grid graph $G_{nm}$ can be written as the Cartesian product of the path graphs $P_n$ and $P_m$: $G_{nm}=P_n\square P_m$ . In terms of spectra it holds $$ \mathrm{spec}(L(G_{nm}))=\mathrm{spec}(L(P_{n}))\oplus \mathrm{spec}(L(P_{m})). $$

Problem:

Now consider the graph $S_{n}$ as the graph resulting from $G_{nn}$ by deleting the "diagonal" vertices labeled by $1,n+2,2n+3,...,n\cdot n$. The graph $S_n$ has two connected components (see picture connected components of $S_n$). As both connected components are the same, I will call the connected component again $S_n$.

I am now interested in the spectrum of $S_n$. Is there any analytic solution to the Laplacian eigenvalue problem for $S_n$?. In particular I want to know the behavior of the first nonzero eigenvalue in function of $n$ (exponential vs. polynomial decrease?).

As I could figure out so far, it holds $$ \mathrm{spec}(L(P_n))\subseteq \mathrm{spec}(L(S_n)). $$ This comes from the fact that the superposition $\frac{1}{\sqrt{2}}\left(u_{i1}+u_{1i}\right)$ (projected to the corresponding subspace of vertices from $S_n$) is again a eigenvector of $L(S_n)$ with same eigenvalue $\lambda_{i1}$ for all $i\in \{1,...,n\}$. My guess for the smallest nonzero Laplacian eigenvalue of $S_n$ would be $ 4\sin^2\left( \frac{\pi}{2n}\right)$.

Generalization to higher dimensions

Also of interest is the same problem generalized to higher dimensions. The connected components of $S_n$ can be produced by starting with a path graph $P_{n-1}$ and "adding" a shorter row $P_{n-2}$ next to it, and repeat this procedure until reach the trivial graph $P_1$. As a generalization to the 3D case consider $S_{n-1}$ and "add" another layer of $S_{n-2}$ next to it and so on ( See: 3D generalization). Also this graph can be constructed by starting from the 3D grid graph $G_{nnn}$ and deleting vertices along 3 hyperplanes. (Example $G_{666}$, The 6 connected components after cutting out vertices of $G_{666}$ ) Also in this case, calculations in mathematica suggest that the lowest nonzero eigenvalue of the connected components is again $ 4\sin^2\left( \frac{\pi}{2n}\right)$ (checked it for small $n$ up to 10.)

Many thanks in advance. Martin :)

$\endgroup$
  • $\begingroup$ The Laplacian spectrum of the dual of the triangular grid graph is worked out in Example 4.4, page 84, of chanoir.math.siu.edu/MATH/MatrixTree/rubey.pdf. I am embarassed having to admit that I do not know where I took this from. I also do not know whether this helps. $\endgroup$ – Martin Rubey May 2 at 18:59
  • 1
    $\begingroup$ Interestingly the dual is up to the exterior vertex again a triangular grid graph. The removal of that vertex gives an upper bound to each eigenvalue (due to the Laplacian version of the interlacing theorem). But with the high degree of that vertex the lower bound is useless. Scrolling though your thesis got me the idea to google for aztec graphs. In arxiv.org/pdf/0710.4500.pdf they where able to calculate the adjacency spectrum of the so called "quartered Aztec diamond" (our triangular grid graph). But I don't know if this gives any information of the corresponding Laplacian spectra. $\endgroup$ – ortofoxy May 3 at 11:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.