Questions tagged [spectral-graph-theory]

Questions related to the spectrum of graphs, defined using one of the possible variants of the discrete Laplace operator or Laplacian matrix. See https://en.wikipedia.org/wiki/Discrete_Laplace_operator

Filter by
Sorted by
Tagged with
2
votes
0answers
59 views

On norms of Boolean functions

Let $f: \mathbb{F}_2^n \rightarrow \{-1,1\}$ be a Boolean function, represented by a $N=2^n$ dimensional vector, $f \in \{-1,+1\}^N$. Define the Fourier transform of $f$ to be $\hat{f}$, where $$\hat{...
0
votes
0answers
43 views

Lower bounds on the length of circuits, depending on the number of times it crosses itself

I have this problem that I have been stuck on for months, and would like to know if somebody can tell me a way to attack the problem. Let me ask the problem in a simple example below. Let $G(V,E)$ be ...
1
vote
0answers
38 views

4-cycles vs eigenvalue information on quasi-random graphs

My (philosophical) question arises from reading the wonderful paper of Chung-Graham-Wilson where the authors introduces the notion of quasi-random graphs. The main purpose of the paper is to show ...
7
votes
0answers
109 views

Is this lower bound for the size of minimal vertex cover new/interesting?

I have found this lower bound for the size of minimal vertex cover (and proved it). If a simple connected graph G on n vertices has largest and smallest eigenvalues $\lambda_1,\lambda_n$, ...
3
votes
0answers
87 views

How related are Fourier transforms on finite groups and Fourier transforms on graphs?

Here are two generalizations of the notion of a Fourier transform. I am also aware of the Pontryagin Duality generalization for locally compact abelian groups, though I am personally more concerned ...
4
votes
1answer
108 views

Relation of row sums to largest eigenvalue

I know that the largest eigenvalue of a graph is bounded between the minimal and maximal row sum of the matrix. If I have a $0-1$ symetric matrix (an adjacency matrix) and I know $k$ of the rows have ...
0
votes
0answers
50 views

$\lambda_2$ of Laplacian of a regular graph

Given a $d$-regular graph $G=(V,E)$ with $|V| =n$. We know that the smallest eigenvalue of the normalized laplacian matrix of $G$ is $0$. I have seen the formulation of the second smallest eigenvalue $...
2
votes
0answers
104 views

Number of components of self-index complementary graphs

Let $G$ be a simple graph. We say this graph is self-index complementary ($SIC$) if $\lambda_1 (G)=\lambda_1 (\overline{G})$, where $\lambda_1(G)$ denotes the index of the adjacency matrix of the ...
0
votes
0answers
34 views

Orthogonality condition of symmetric matrix pencil

Let $P(\lambda)=\lambda M−L\in \mathbb{R}^{n \times n}$ be a matrix pencil with symmetric nonsingular matrix $M$ and $L$ is a weighted Laplacian matrix of a connected graph. Clearly $(0,1_n)$ is an ...
1
vote
1answer
67 views

Total behaviour of graph spectrum

Let $\mathcal{G}$ be the set of all finite connected simple graphs minus the complete graphs. For any $G\in \mathcal{G}$, let $\lambda_{\geq0}(G)$ denotes the smallest positive adjacency eigenvalue of ...
0
votes
0answers
29 views

Unions of subgraphs of quasi-random graphs

Fix a positive probability $p$, and take $G = (V, E)$ to be a graph with edge density $p$. Given a subset $S$ of $V$, take $K(S)$ to be the complete graph on the vertices in $S$. Following Chung in ...
2
votes
1answer
99 views

Cocktail party and tripartite graphs are DS?

Cocktail party graphs and $k_{n,n,n}$ (a tripartite graph) are determined by the spectra of their adjacency matrices? I think thay are DS ( determined by the adjacency spectrum) but I can't find a ...
9
votes
3answers
1k views

What happens to eigenvalues when edges are removed?

I am stuck at the following : Let $G$ be a graph and $A$ is its adjacency matrix. Let the eigenvalues of $A$ be $\lambda_1\le \lambda_2\leq \cdots \leq \lambda_n$. If we remove some edges from the ...
1
vote
1answer
65 views

Anderson localization for Bernoulli potentials on half-line

Anderson localisation for (discrete) Schrödinger operators with Bernoulli potentials on $l^2(\mathbb{Z})$ was proven in https://link.springer.com/article/10.1007/BF01210702 I am wondering if there ...
2
votes
2answers
72 views

Question about eigenvalues of connectivity matrices for graphs [closed]

I'm a computer science student working on a research project that deals with computational study of atomic clusters. I'm using a graph based representation of the clusters using a binary connectivity ...
1
vote
0answers
65 views

Normalized Laplacian matrix versus walk Laplacian matrix (or normalized adjacency matrix versus walk adjacency matrix)

In graphs, found that two different normalization matrices exist for Laplacian and adiacency matrix. I will ask about the adjacency matrix (for the Laplacian matrix the questions are the same). The ...
3
votes
1answer
56 views

Reference request: maximal Cheeger constant for 3-regular graphs

Given a connected graph $G$, the Cheeger constant $h(G)$ (a.k.a. Cheeger number or isoperimetric number) roughly measures the "bottleneckedness" of $G$. See Wikipedia for the precise definition. I ...
10
votes
2answers
270 views

Algebraic properties of graph of chess pieces

For the purpose of this question, a chess piece is the King, Queen, Rook, Bishop or Knight of the game of chess. To a chess piece is attached a graph which represents the legal moves it can make on an ...
0
votes
0answers
19 views

Explicit computation of spectrum of some infinite trees

This is probably more of a computational matter, but on Mathematica StackExchange they closed my question, so I try and ask here as well. I would like to compute the spectrum of some infinite trees ...
2
votes
0answers
56 views

Infinite trees whose spectrum has more than 3 connected components

I was wondering whether there exists any infinite tree $T$ such that the action of $\mathit{Aut}(T)$ on the set of vertices $V=V(T)$ has finitely many orbits, and whose spectrum $\sigma(T)$ has ...
0
votes
1answer
45 views

Spectral of a connected d-regular bipartite graph [closed]

Let $G$ be a connected $d$-regular bipartite graph. Would you please tell me about the spectrum of this graph?
0
votes
0answers
58 views

Singular values and the chromatic number

What relation, if any, is there between the singular values of the adjacency matrix ( or possibly incidence matrix) of a simple graph and its chromatic number. Typically, do we have Hoffmann type, or ...
2
votes
0answers
145 views

Graphs with the same Laplacian eigenvalues

Let $L$ be the Laplacian matrix for a simple graph $G$ of $n$ vertices, and $\lambda_0,\ldots,\lambda_{n-1}$ its $n$ eigenvalues. Q. What is the cardinality of the class of $n$-vertex graphs $\...
1
vote
0answers
54 views

Large bounded degree expanders in the hypercube

Does the $n$ dimensional hypercube graph contain large bounded degree expanders as subgraphs? For example, of exponential size in $n$? If not, one could relax the problem and allow the maximum ...
2
votes
1answer
94 views

Eigenfunctions adjacency operator on infinite graph in $l^2$

Let $\Gamma$ be an infinite (connected) graph without edges going from a vertex to itself (though it might have multi-edges). Let us suppose that $\Gamma$ has finite valence. Is there always a ...
1
vote
0answers
90 views

Digraphs with same number of semiwalks

This is a follow-up question to Characterisation of walk-equivalent digraphs. Question: Do there exists two directed graphs $G$ and $H$ consisting of the same number ($n$) of vertices, such that \...
1
vote
1answer
99 views

Characterisation of walk-equivalent digraphs

Setting Let $G=(V,E)$ be an undirected graph. A walk $\pi$ in $G$ of length $k$ is a sequence of $k+1$ vertices $v_1,\ldots,v_{k+1}$ such that for each $i\in[1,k]$, $\{v_i,v_{i+1}\}\in E$. Let $H=(W,F)...
2
votes
0answers
230 views

Why do we assume that $\mathcal{A}$ is an algebra in this 2003 paper of Bobkov and Tetali?

In the following paper (extended version here), at the beginning of section 3, the authors give two axioms about $\mathcal{A}$. Axiom 1 is about $\mathcal{A}$ being an algebra. I do not see where this ...
2
votes
1answer
91 views

Two cospectral (normal) digraphs which are not orthogonal similar

Preliminaries A complex matrix $A$ is normal when $A$ and $A^*$ commute. A real matrix $A$ is normal when $A$ and $A^t$ commute. Two complex matrices $A$ and $B$ are said to be unitary similar if ...
2
votes
1answer
70 views

On sum of elements in products of matrices for a simple graph

Let $G$ be a simple graph with vertex set $\{v_1,v_2,\ldots,v_n\}$. The adjacency matrix of $G$ is the 0-1 matrix $A$, where $A_{i,j}=1$ when $v_i$ is adjacent with $v_j$. The degree matrix is the ...
0
votes
0answers
71 views

Difference between second largest and smallest eigenvalue

The question is related to spectral graph theory. Wrt Fiedler number and algebraic connectivity of graphs, sometimes academic literature uses second largest eigenvalue, sometimes second smallest. For ...
1
vote
1answer
205 views

Eigenvectors of graph Laplacian for spectral clustering

I have the following questions regarding the graph Laplacian for spectral clustering: What is the intuition behind projecting the Laplacian (D-A, where D is the degree matrix and A is the affinity ...
1
vote
0answers
80 views

Algebraic connectivity of the path $P_n$

Let $G$ be a graph with $n$ vertices. Denote by $L(G)$ the Laplacian matrix of $G$ and $0=\lambda_1\leqslant\lambda_2\leqslant...\leqslant\lambda_n$ its spectrum. The number $\lambda_2$ is called the ...
1
vote
1answer
68 views

Spectral bound for maximum clique $k(G)$ in a permutation graph

Let $\pi \in S_n$ be an arbitrary permutation. By permutation graph, we refer to a simple graph with nodes $[n]$ and edges that connect pairs of nodes that appear sorted in $\pi$. Formally, $G=(V=[n],...
5
votes
0answers
157 views

Can the corollary of the Ihara–Bass formula be extended to $ u^2 = 1 $?

Suppose there is a finite undirected graph $G(V,E)$ having $n$ vertices and $m$ edges. The non-backtracking matrix $B$ is indexed by $2m$ directed edges and defined as $$ B(a \to b, c \to d) = \delta_{...
2
votes
2answers
251 views

What's the full assumption for Laplacian matrix $L=BB^T=\Delta-A$?

Graph with no-selfloop, no-multi-edges, unweighted. directed For directed graph Adjacency matrix is a non-symmetric matrix $A_{in}$ considering indegree or $A_{out}$ considering outdegree. Degree ...
7
votes
1answer
362 views

Understanding Gillman's proof of the Chernoff bound for expander graphs

My question is about the proof of Claim 1 in this paper: Gillman (1993). At the end of the proof, the author says: The matrix product $U^\top\sqrt{D^{-1}}(P+(\mathrm{e}^x-1)B(0)-\mu I)\sqrt{D}U$, ...
7
votes
1answer
175 views

Co-spectral fractional isomorphic graphs with different Laplacian spectrum

I am looking for two undirected graphs $G$ and $H$ of the same order (i.e., they have the same number of vertices) such that $G$ and $H$ are cospectral (i.e., their adjacency matrices $A_G$ and $A_H$ ...
1
vote
2answers
187 views

Upper bounds for the second largest eigenvalue in terms of degree?

I am looking for upper bounds on the second largest eigenvalue, $\lambda_2(G)$ of a given graph $G$, with respect to minimum/maximum degrees of the graph. I looked around for some existing bounds most ...
2
votes
1answer
219 views

Graph Fourier transform definition

I have a question about the definition of the graph Fourier transform. Let me start with definition. Let $A$ be the adjacency matrix of a graph $G$ with vertex set $V = \{1, 2, \dots, n\}$. The ...
3
votes
0answers
153 views

Laplace spectra of “half” grid graph

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 ...
5
votes
2answers
207 views

Eigenvalues of the Laplacian of the directed De Bruijn graph

We will denote by $DB(n,k)$ the directed De Bruijn graph, which is a digraph whose vertices are elements of $\{0,1,\dots,k-1\}^n$, and $\sigma_1\cdots \sigma_n$ is connected to $\tau_1\cdots \tau_{n}$ ...
1
vote
1answer
193 views

Graph Laplacian Operator

Consider the linear operator $\mathbb{L} : L^2([0,1])\to L^2([0,1])$ defined by $$ (\mathbb{L}f)(x) = \int_0^1 xy(f(x)-f(y)) \mathrm{d}y $$ for all $f\in L^2([0,1])$ and $x \in [0,1]$. Is $\mathbb{L}$...
4
votes
1answer
139 views

Are there graphs with irrational eigenvalues which are all $>1$?

The eigenvalues associated to a graph's adjacency matrix are necessarily algebraic integers, because the adjacency matrix itself is entirely integer. I'm curious as to whether it's possible to have ...
6
votes
0answers
223 views

Is there a version of Weyl's law for graph Laplacians?

Is there a version of Weyl's law or a local Weyl's law for eigenvectors of the graph Laplacian? For some context, a colleague in statistics has encountered eigenvectors of the Laplacian for certain ...
1
vote
0answers
134 views

Principal eigenvector of non-negative symmetric block matrix is approximated by a linear combination of the principal eigenvectors of the blocks

Let $ M \in \mathbb{R}^{n \times n} = \begin{bmatrix} A & B \\ B^T & C \end{bmatrix} $ for some nonnegative $A \in \mathbb{R}^{k \times k}, B \in \mathbb{R}^{k \times n-k}, C \in \mathbb{R}^{n-...
1
vote
0answers
121 views

Expander mixing lemma in combinatoric expanders

There is a well-known relation between combinatoric expansion and the gap between the first and the second largest eigenvalues (Dodziuk 1984) : $$ h(G) \le d \sqrt{2 (1 - \alpha)} $$ where $$h(G) = \...
1
vote
0answers
81 views

What is intuitive perception of $T_{\alpha_1} \circ T_{\alpha_2} \circ … \circ T_{\alpha_M} $ in graph domain?

if $G(V,E,W)$ be a weighted graph and $\vert V \vert =N $. for any vertex $i \in \lbrace 1,2,...,,N \rbrace $ define a generalized translation operator $T_i:\mathbb{R}^N \to \mathbb{R}^N $via ...
10
votes
1answer
287 views

An upper bound for the largest Laplacian eigenvalue of a graph in terms of its diameter

Let $G$ be a simple graph with $n$ vertices and $\lambda$ be the largest eigenvalue of its Laplacian operator $L=D-A$. I have some evidence for the following conjecture: Conjecture: If G has ...
1
vote
1answer
101 views

Is there a transient graph whose spectral dimension two?

Let $G = (V(G), E(G))$ be an infinite connected simple graph. Let $((S_n)_n, (P^x)_{x \in V(G)})$ be the simple random walk on $G$. Let $p_n (x,y) = P^x (S_n = y)$. A spectral dimension of $G$ is ...

1
2 3 4 5 6