Skip to main content

Questions tagged [spectral-graph-theory]

For questions related to the study of properties of a graph in relationship to the spectral properties of some associated matrix.

Filter by
Sorted by
Tagged with
0 votes
1 answer
30 views

What are the properties of the incidence matrcies of undirected graphs

Here is the definition of incidence matrix I find on Wikipedia https://www.wikiwand.com/en/Incidence_matrix Suppose we have a graph $G$ with $N$ nodes and $e$ edges (we only consider undirected graphs ...
LeoB's user avatar
  • 1
0 votes
0 answers
35 views

Proof of: Connected graph with three distinct adjacency matrix eigenvalues with the largest eigenvalue nonintegral is complete bipartite.

In the paper "Graphs with Three Eigenvalues" by E. R. van Dam, proposition 2 says that if a connected graph has three distinct eigenvalues and the largest is nonintegral, then it's a ...
supremum's user avatar
2 votes
0 answers
20 views

Constructing a graph with a given Fiedler vector

Given $\boldsymbol u \in \mathbb{S}^{n-1}$, how could one construct a (weighted, connected) graph whose Fiedler vector $\lambda_{2}(D-A)$ — that is, a unit-norm eigenvector corresponding to the second-...
JakeH's user avatar
  • 21
0 votes
0 answers
27 views

Number of Shortest Paths Through Any Edge on a Discrete Torus

I am currently stuck with the following problem: Consider the setting of a random walk on a discrete torus with $d$ dimensions and grid Size $L$. That means considering a simple (no loops or multiple ...
Gabelstabler's user avatar
0 votes
0 answers
26 views

Show that if $A(m, n)$ is nonsingular, then ${m + n \choose n}$ is even

The problem statement from Exercise 1(a) of chapter 6 of Algebraic Combinatorics by Richard Stanley: Let $A(m, n)$ be the adjacency matrix (over $\mathbb{R}$) of the Hasse diagram of $L(m, n)$, the ...
Jonathan McDonald's user avatar
0 votes
0 answers
28 views

Eigenvectors of Johnson Graph $J(N,2)$

I am having trouble finding an orthogonal basis of eigenvectors of the Johnson Graph $J(N,k)$ with k=2 in an explicit form. In the paper "On the reconstruction of eigenfunctions of Johnson graphs&...
Alessio Catanzaro's user avatar
1 vote
0 answers
54 views

Positive semidefiniteness of Laplacian of undirected graph

Let $D$ be a directed graph. Given a directed edge $e:x\to y$ of $D$, the head of $e$ is defined to be the vertex $y$ and its tail is defined to be the vertex $x$. The gradient matrix of $D$, denoted $...
D. S.'s user avatar
  • 40
0 votes
0 answers
12 views

Cospectrality of square grid minors

I'm working on an interesting computational game theory problem. One way to dramatically improve the runtime is to develop a computationally efficient invariant that can characterise the graphs I'm ...
Yi Chen Chong's user avatar
0 votes
0 answers
17 views

Prove that a necessary and sufficient condition $RQ(X):=\lambda_{max}$, where $\vert\vert x \vert \vert =1 $, is that $Ax=\lambda_{max}x$

I am trying to prove this question my current attempt is as follows. NB $RQ(X):=\langle Ax,x \rangle$, with $A$ an adjacency matrix of a graph $G$ on $n$ and $m$ vertices. ($\Leftarrow$) $Ax=\lambda_{...
andimon's user avatar
  • 35
1 vote
1 answer
79 views

Why eigenspace of -1 orthogonal complement of 1?

Suppose eigenvector of $A(K_n)$ that is orthogonal to $1$ satisfies $A(K_n)v=-1v.$ Hence, $-1$ is an eigenvalue of $K_n$. The argument used to flush out $-1$ revealed also that the eigenspace of $-1$ ...
user avatar
0 votes
0 answers
82 views

Compute all the eigenvalues of complete graph [duplicate]

We know that the eigenvalues of $K_n$ are $-1$, $n-1$ with multiplicity $n-1$, $1$ respectively. I am trying to find the spectrum of the complete graph from below image, where $x$ is the eigenvector, $...
user avatar
1 vote
1 answer
84 views

Inner products in graph partition

Let $G=(V, E)$ be a any graph and any set $S \subset V. $ And any vector $v_S$, defined as follows, $\begin{equation} v_{S_i}= \begin{cases} 1-\frac{|S|}{|V|},& \text{if}\ i \in S\\ ...
user avatar
-1 votes
1 answer
65 views

What does mean bisection of graph?

I am struggling to understand bisection of graph. I searched in internet (less article available in the internet) I found this below paragraph: A bisection of a graph is a bipartition of its vertex ...
user avatar
5 votes
2 answers
485 views

What is canonical spectral theorem?

My teacher has given me the following definition of the canonical spectrum theorem: Let a matrix the $A \in M_{n\times n}(\mathbb{R})$, and set of eigenvalues, $\sigma(A)$={$\lambda_1$,$\lambda_2$........
user avatar
0 votes
0 answers
30 views

Spectral Clustering: Finding the normalized minimum cut using the laplacian

I am trying to prove that finding the min $Ncut(A,B)$ for a edge weight graph $W$ with the diagonal matrix of edge degrees $D$ is equivalent to solving for $f \in \{a,b\}^n$ with the constraint that $...
bluesquare's user avatar
0 votes
0 answers
22 views

Do graph laplacian eigenvectors/values beyond the second smallest eigenvalue mean anything?

It is my understanding that the multiplicity of the smallest eigenvalue (the zero eigenvalue) of the graph laplacian $L=D-A$ equals the number of connected components of a graph, while the second ...
LYB's user avatar
  • 13
0 votes
0 answers
76 views

What's the conditions for equality of Cheeger inequality?

I have learnt the Cheeger inequality for a graph $G$: $$\lambda_2/2\le h(G)\le\sqrt{2\lambda_2}.$$ But does the equality hold? For a non-connected graph, it is obvious. But for a connected graph, I ...
Fresh's user avatar
  • 81
0 votes
0 answers
25 views

Reconstructing a graph from a subgraph and spectral properties

There's a graph $G$ which is conjectured to exist. We know it's $k$-regular, and we know its spectrum. (I don't think the exact problem is important for this question). $G$ is much too large to ...
Kristaps John Balodis's user avatar
1 vote
0 answers
60 views

Bounding $v_1^\top D v_1$ where $v_1$ is the top eigenvector of a symmetric random matrix (Wigner matrix)

Suppose $A\in \mathbb{R}^{n\times n}$ is a symmetric random matrix, with iid centered Bernoulli non-diagnonal entries $A_{ij} \sim \mathrm{Bernoulli}(p) - p$, for some $p \in (0,1)$, and zeros on its ...
JasonShaw's user avatar
0 votes
0 answers
62 views

How to show that for any graph $G$ $\lambda_{n}(G) \ge d_{\max}(G)$

To my understanding, the maximum degree of a node in a $n$ vertices graph is $n-1$. I am assuming that we have to somehow prove that maximum eigenvalues are greater than $n - 1$. The hint given was ...
Audrey's user avatar
  • 1
1 vote
1 answer
39 views

From adjacency Matrix can we find the maximum number of disjoint matching pairs of a simple undirected graph?

I came across this problem which boiled down to finding the maximum number of pairs of disjoint edges given a simple undirected graph. After doing some research I came across Edmond's Blossom ...
Chandana Deeksha's user avatar
0 votes
1 answer
107 views

Heat kernel on graphs

Let $V$ denote a finite set $(v_1, \ldots, v_n)$ and $G=$ $(V, E)$ denote a non-oriented connected graph, i.e., $E \subset V \times V$ and $(v, v^{\prime}) \in E \implies (v^{\prime}, v) \in E$ and ...
Pipnap's user avatar
  • 431
1 vote
1 answer
52 views

Spectrum of circulant block matrix of circulant blocks (Adjacency matrix of discrete torus)

I am currently investigating the spectrum of a matrix $M \in \mathbb{R}^{12 \times 12}$. The matrix has the following form, $$ M = \begin{bmatrix} 0 & 1 & 0 & 1 & 1 & 0 &...
SebastianP's user avatar
1 vote
0 answers
27 views

Connection between graph realization (embedding) and spectral theory

Definition 1 (realization): Let $k$ be a positive integer and $G = (V, E, d)$ be a simple graph with $n$ vertices, undirected, connected, and with edge weights. Find a function $x: V \rightarrow \...
GFP's user avatar
  • 11
1 vote
1 answer
67 views

computing eigenvalues for an infinite family of graphs [closed]

I'm trying to compute the sequence (and then trying to figure out the limit) of the maximum eigenvalues of the adjacency matrices of the infinite family of graphs build by starting with a triangle and ...
Gianfranco's user avatar
0 votes
0 answers
69 views

Final steps of Lovász derivation of the hitting time between two nodes in a random walk

I'm trying to understand thoroughly the proof of the Lovász's formula to calculate the hitting time $H(s, t)$ between two nodes $s$ and $t$ in a random walk on a graph. At page 13 it gets to the ...
Felipe's user avatar
  • 75
0 votes
1 answer
36 views

Type of Matrix with only real eigenvalues

Consider a parameter $0 \leq d \leq 1$ and a vector $\mathbf{q}$ of size $n$ made of real positive values. From this, construct the (real, non-negative) $n \times n $ matrix $\mathbf{M}$ such that $...
Christophe's user avatar
1 vote
1 answer
69 views

Proof of the spectral formula for the expected number of steps in a random walk

In a paper by Lovász (see reference at the end), there is the derivation of a spectral formula for the hitting time, which is the expected number of steps to get to a node t, starting at s, in a ...
Felipe's user avatar
  • 75
0 votes
0 answers
14 views

Eigenvectors corresponding to eigenvalue 1 in the Normalized Laplacian - Why does it represent clusters?

Consider the Normalized Laplacian associated to a similarty graph $$ L = D^{-1/2}SD^{-1/2} $$ I have two sources stating that, in the "ideal case of zero noise", the eigenvectors ...
ygh's user avatar
  • 121
0 votes
0 answers
27 views

Intuition eigenvectors graph Laplacian for weighted graph

Is there some interpretation for the eigenvectors of the Laplacian of a (directed) weighted graph? Normally, the spectrum of a Laplacian informs us about connectives, is this also the case for a ...
Jeff Martin's user avatar
2 votes
1 answer
58 views

Are there real normal matrices with non-negative entries that are asymmetric and non-circulant?

Is there an example of a normal matrix with real non-negative entries that is neither symmetric nor circulant/block-circulant? If not, is there a proof of this property/reference to proof? ...
citizenfour's user avatar
0 votes
0 answers
58 views

Generating a list of tuples $\{G, \eta(G)\}$, where $G$ is connected graph on $n$ vertices and $\eta(G)$ represents its nullity.

Let $G$ be a graph with an adjacency matrix $A(G)$. The nullity of a graph $G$ is defined as the dimension of the null space of $A(G)$. I want to generate a list of connected simple graphs on $n$ ...
Bableen Kaur's user avatar
1 vote
1 answer
99 views

Are all Laplacian eigenvalues always non-increasing when an edge is deleted?

Consider the Laplacian $L$ of some simple graph $G$ with at least one edge. As usual, $L=D-A$ where $D$ is the diagonal matrix with elements $D_{ii}=d_i$ where $d_i$ is the degree of node $i$ and ...
Kiro's user avatar
  • 305
0 votes
1 answer
250 views

Lower bounds on the maximum eigenvalue of the adjacency matrix of an edge weighted graph

If $G$ is a simple graph with adjacency matrix $A$ then the following inequalities are known to hold (See eg. Prop 2.1. of this note of Lovász - there's no proof given though): $$\sqrt{\Delta(G)}, d_{\...
gen's user avatar
  • 1,518
0 votes
1 answer
54 views

If k and n-k-1 are coprime then strongly regular graph G is imprimitive

I am trying to solve the exercise 10.1 from Algebraic graph theory by Godsil and Royle. I’m stuck with it, can anyone give me some hint. Below is the question. Suppose G is a strongly regular graph on ...
spectralmath's user avatar
1 vote
1 answer
285 views

Why do the "important" eigenvectors of a graph Laplacian have small-magnitude eigenvalues?

In spectral clustering, one computes sample-sample similarities, then from this computes a graph Laplacian matrix. (Typically, one uses the symmetrically normalized Laplacian matrix, but the pattern I'...
calmcc's user avatar
  • 261
1 vote
0 answers
79 views

Minimization problem of the Fiedler vector

I am currently stuyding spectral graph theory and in my slides I stumbled on the following solution to obtain the Fiedler vector: \begin{align} \min_x x^T L_G x \\ \text{s.t. } x^T x = 1 \\ x^T \vec{...
MathAccount12's user avatar
0 votes
0 answers
63 views

Bounds on the spectral radius of a directed graph

Suppose $(G_n)$ is a sequence of simple directed graphs with $G_n$ having $n$ edges such that the adjacency matrix $A_n$ of $G_n$ is primitive, and let $(G_n’)$ be a sequence of subgraphs obtained by ...
a person's user avatar
0 votes
0 answers
44 views

Connections between Ising model and Cheeger inequalities

(Disclaimer: I'm not all that familiar with any of the two topics) Consider the Ising model on some graph with, lets say, two heavily inter-connected components that are sparsely connected between ...
augustoperez's user avatar
  • 3,226
0 votes
0 answers
139 views

What can we say if the spectral radius of a matrix is less than one?

I am currently studying directed acyclic graphs (DAGs). Recall the spectral radius $r(B)$ of a matrix $B$ is the largest absolute eigenvalue of $B$. The paper I am reading said the condition that $r(B)...
Jackie's user avatar
  • 553
2 votes
1 answer
47 views

Inequality for local spectral moments of adjacency matrix

According to this paper, the local spectral moments $\mu_k(i)$ are defined as the $i$-th diagonal entry of the $k$-th power of the adjacency matrix $A$ of a simple graph $G = (V, E)$, i.e., $$ \mu_k(i)...
Bob Aiden Scott's user avatar
4 votes
0 answers
194 views

Can a simple (possibly weighted) graph be constructed for any given spectrum of the Laplacian?

Given a sequence $S$ of real numbers $0=e_0\le e_1 \le \dots \le e_n$, does there exist a simple graph G (possibly with real non-negative weights $\omega_{ij}$ assigned to its edges) whose Laplacian ...
user10001's user avatar
  • 463
0 votes
1 answer
111 views

Eigenvalues after setting rows of matrix to zero

I am studying the effect on the eigenvalues of a known Laplacian matrix $L$ when the first $p$ rows (wlog the top rows) are set to $0$. For those not familiar with a Laplacian matrix, all you need to ...
Landuros's user avatar
  • 2,781
1 vote
0 answers
19 views

Spectral graph theory for population projection matrices

Consider a population structured into $s$ categories, and a matrix $\mathbf{M}$ of size $s\times s$, that projects deterministically the population vector $\mathbf{n}$ of length $s$. All elements of $\...
Christophe's user avatar
2 votes
1 answer
236 views

Using the matrix of adjacency to find number of paths (not walks)

I am well aware that if $A$ is the adjacency matrix of a graph, then $A^n=a^{(n)}_{ij}$ counts the number of walks of length $n$ from vertex $i$ to vertex $j$. Is there a way to modify this so that ...
Pablo de la Fuente's user avatar
2 votes
1 answer
52 views

Smallest eigenvalue of a variant of the line graph Laplacian

I would like to calculate a lower bound on the minimum eigenvalue of the matrix $$M = e_1 e_1^\top + L$$ where $L$ is the Laplacian of the line graph on $T$ vertices: $$1 -2 -3 -4-\ldots -T $$ and $...
Chinmay Nirkhe's user avatar
1 vote
0 answers
35 views

If $G$ is a strongly connected graph and $1\le n< \rho(G)$ is an integer, then must there always exist $H\subset G$ with $\rho(H)=n$?

$G$ may have loops and multiple, directed edges, and we take $H\subset G$ to mean that the edges and vertices of $H$ are subsets of those in $G$ (not necessarily a vertex-induced subgraph). We take $\...
Terence C's user avatar
  • 332
1 vote
0 answers
54 views

On the smallest eigenvalue of the complement of a regular graph

While reading on graph theory and its applications, I came across a problem which stated if $\bar{G}$ is the complement of a regular graph then its eigenvalues are $-\lambda_i-1$ and $n-1-k$ where $G$ ...
Amir Mg's user avatar
  • 124
1 vote
1 answer
346 views

Left and right eigenvectors of transition matrix relationship and normalization

I'm currently reading this article (1) and I want to verify equation (4) and (5). I will reproduce the claim here. Let $P$ be a transition matrix and $\phi_0$ be the stationary distribution of $P$. ...
Mevve's user avatar
  • 658
0 votes
0 answers
31 views

Non-isomorphic co-spectral graphs with distinct eigenvalues

There is a polynomial time algorithm by Leighton and Miller for deciding whether cospectral graphs with eigenvalues of multiplicity $1$ are isomorphic. However, are there any known cospectral graphs ...
Emil Sinclair's user avatar

1
2 3 4 5
13