For questions on spectral graph theory is the study of properties of a graph in relationship to the characteristic polynomial,...

learn more… | top users | synonyms

0
votes
0answers
34 views

Finding the smallest max eigenvalues for related matrices?

While messing around with a spectral approach to a graph coloring question, I happened upon a type of problem I hadn't seen before. Suppose you have two symmetric $n$ x $n$ matrices in the form ...
0
votes
0answers
8 views

Normalized graph Laplacian with negative degrees

In spectral embedding algorithms, we can apply a kernel function to each pair of extracted feature vectors when constructing the adjacency matrix $W$. Suppose that the kernel function fulfills the ...
0
votes
1answer
21 views

If $G$ is connected then $\lambda_2 < \lambda_1$.

Let $G=(V,E)$ be an $n$-vertex , undirected graph with maximum degree $d$, then how to prove the following result. If $G$ is connected then $\lambda_2 < \lambda_1$. where $\lambda_1 \geq \lambda_2 ...
0
votes
1answer
22 views

Top and bottom power spectral density of a height profile

Imagine I have a simple 1D height profile which is NOT symmetric. Now, what is truly important for me is to know what are the frequency content of the top profile (i.e. a cut profile above the ...
2
votes
0answers
109 views

a closed formula to enumerate the self avoiding walks of a graph

Let $G$ be a directed graph with $N$ nodes and weighted adjacency matrix $W $ defined by $$ W_{ij} = \left\{ \begin{array}{cl} w_{ij} & \text{ if } \ i \ \text{ is connected to } j \\ 0 & ...
1
vote
1answer
65 views

Graph Isomorphism algorithm that doesn't always work

I just thought of the following incomplete algorithm for deciding whether two graphs are isomorphic: Let $A$ and $A'$ be adjacency matrices of two graphs. Then for some unitary $U,U’$ and diagonals ...
0
votes
1answer
26 views

Control principal eigenvector of a row stochastic matrix

I am just trying to consider the classical discrete-time Markov Chain problem. Consider the transition matrix P, which transforms state vector $x(k)$ to $x(k+1)$, satisfying: $x(k+1)$ = $P*x(k)$ It ...
0
votes
0answers
15 views

What is the importance of Laplacian Matrix in spectral clustering

In spectral clustering algorithms, we often use Laplacian matrix of adjacency matrix instead of Adjacency matrix itself. What is the advantage of using Laplacian matrix over simple adjacency matrix?
1
vote
0answers
32 views

Spectrum of an infinite graph independent of labelling

Does there exist an infinite graph whose spectrum does not depend upon the labelling of the graph? While evaluating the spectrum, I am considering adjacency matrix of the infinite graph as a bounded ...
2
votes
1answer
72 views

Eigenvalues of the distance-k graph of a graph

Let $G$ be a (finite, simple, connected) graph. Define the distance-$k$ graph $G_k$ to be the graph with the same vertex set and $x\sim y$ iff $d(x,y)=k$. A graph is integral if all of the eigenvalues ...
1
vote
1answer
17 views

Motivations for Shi-Malik Algorithm

So I've been trying to make sense of the clustering algorithm on page 6 of this paper. Are the "first" k eigenvalues they refer to the smallest eigenvalues? What are the $y_i$ exactly? I don't see ...
2
votes
1answer
36 views

Functions on adjacency matrices

From Norman Biggs, Algebraic Graph theory 2j, p13: The adjacency matrix has a spectral decomposition $A = \sum \lambda_aE_a$, where the matrices $E_a$ are idempotent and mutually orthogonal. (...) It ...
6
votes
0answers
110 views

Applications of Cayley Graphs in Physics

I have been recently reading about Cayley graphs and character theory. It is evident that Cayley graphs are very useful tool in theoretical computer science. In physics, Cayley graphs seem do appear ...
3
votes
1answer
50 views

Show the relationship between the trace and the number of 4-cycles

Let $G$ be a k-regular graph. Show the exact relationship between $tr(A^4)$ and the number of 4-cycles in $G$. I understand how $tr(A^4)$ tells us the total number of closed paths of length 4 in ...
1
vote
2answers
75 views

Graph Theory - Proof

I am need help to Prove the following statement: Let G be a $k$-regular graph with $n$ vertices and $k \geq 1$. Prove that $G$ does not have an independent set of size greater than $\dfrac{n}{2}$. ...
0
votes
0answers
26 views

The lower bound of Cheeger Inequality as the degree goes to infinity

Consider an undirected graph $G(V,E)$ with adjacency matrix $A$ and define the graph Laplacian as \begin{equation} L = D - A \end{equation} where $D$ is a diagonal matrix such that $D(i,i) = d_i$. ...
1
vote
2answers
71 views

Power series convergence of random walk transition matrix

I would like to find out if $$ \sum_{t=0}^\infty P^t = \left( I- P \right)^{-1} ~,$$ where $P = D^{-1}W ~ $ is a random walk transition matrix. $W$ is a matrix describing weights in a graph and ...
2
votes
1answer
65 views

Algebraic Combinatorics

Let $K_{r,s}$ denote the complete bipartite graph, defined on $r + s$ vertices $\{v_1,v_2,...,v_r,w_1,...,w_s\}$, with an edge between $v_i$ and $w_j$ for $1 ≤ i ≤ r$ and $1 ≤ j ≤ s$. By ...
1
vote
0answers
90 views

Does any vertex transitive graph have a bounded eigenvector?

Following up on the negative answer to this question, I would be interested in knowing the answer to the following question, which I cannot seem to find an obvious contradiction to when testing for ...
1
vote
1answer
62 views

rate of convergence of absorbing markov chain

Let $G$ be a biconnected and non-bipartite graph. I can simulate a random walk on this graph with a markov chain. The stochastic matrix is $M = AD^{-1}$, where $A$ is the adjacency matrix of $G$ and ...
3
votes
2answers
78 views

Is the eigenvectors of vertex transitive graphs bounded

For a connected and regular graph $G$ with degree $ d $ at each vertex and adjacency matrix $A$, the normalized Laplacian of $G$ is defined as $L = I-\frac{1}{d}M$. Let $\psi$ be an eigenvector of $L$ ...
2
votes
0answers
51 views

Interesting Questions in Spectral Graph Theory

In the past, I have worked on few problems in Spectral graph theory and their applications to Physics. I have read parts of Fan Chung's book and Daniel Spielman lecture notes. I really enjoyed the ...
1
vote
0answers
76 views

Number of Nodes within a Given Distance from a Node

Suppose we are given a $d$-regular graph $G=(V,E)$ of order $n$. Let $\lambda_2$ be the second-largest eigenvalue of $G$'s adjacency matrix. Does this information help obtaining a lowerbound or ...
2
votes
1answer
46 views

the solution of matrix polynomials

In order to get the eigenvalues of \begin{equation} P=\left[ \begin{array}{cc} 0_{n\times n} & I_{n\times n} \\ -A & -B% \end{array} \right], \end{equation} where $A$ and $B$ are both $n\times ...
0
votes
0answers
28 views

Eigen vectors of graph laplacians

I have been reading about spectral graph theory from Daniel A. Spielman's notes. Fiedler’s Nodal Domain Theorem from this note says that : Let $G = (V, E, w)$ be a weighted connected graph, and let ...
2
votes
0answers
47 views

interpretation of generalized eigenvalue/vectors in spectral graph theory

Let us say I have a symmetric graph adjacency matrix A, a degree matrix D, a laplacian L (D-A). I have a generalized eigenvalue equation $Av=\lambda Lv$. Does the eigenvalue/vectors produced in this ...
0
votes
1answer
40 views

Lower bound on the minimum eigenvalue of sum of two matrices

Assume that $A$ is a symmetric positive definite matrix and $B$ is a symmetric (can potentially negative entries). Is the following bound correct? $$\lambda_{min}(A+B)\geq ...
5
votes
0answers
78 views

Spectral gap of mixture of Markov chains

Context Let $P$ be the transition matrix of an irreducible, aperiodic, discrete-time Markov chain. The spectral gap is given by $$\xi = 1 - \lambda_\max$$ where $\lambda_\max = \max\{\lambda_2, ...
5
votes
0answers
139 views

Generating a stochastic matrix with a given second dominant eigenvalue

I need a procedure (iterative or otherwise) that, given a positive integer $N$ and a (possibly complex) number $\lambda$ such that $0 < \vert \lambda \vert < 1$, will be able to generate an $N ...
0
votes
0answers
13 views

Graph partitioning with constraints

Consider having $n$ data points ${{x}_{1}},..,{{x}_{N}}\in {{R}^{D}}$. Given an affinity matrix of the data, $W=[{{w}_{ij}}]$ where ${{w}_{ij}}$ is the affinity measure for data points ${{x}_{i}}$ and ...
0
votes
0answers
20 views

Graph Laplacian - Spectral Clustering with Regularization

Assume a graph $G=(V,E)$ where the vertices $V$ are points in ${{R}^{D}}$ with $\left| V \right|=n$. The edges $E$ are represented by a $n\times n$ affinity matrix $W$. Consider the graph Laplacian ...
1
vote
0answers
44 views

How can I prove that a particular family of graphs is integral?

I'm working with an infinite family of graphs that seem to always have all integral eigenvalues, and I'd like to find some way to prove that (if it's true). Call the graphs $G_{n,k}$ and define them ...
2
votes
0answers
48 views

Possible Eigenvalues of Graph

How would one prove (or disprove) that there is no such graph $G$ with $\lambda$ as an eigenvalue? I tried setting up a system of equations to see if it's possible for $-\frac{1}{2}$ to be an ...
0
votes
0answers
30 views

(Girko's) circular law beyond the standard normal distribution

I found this circular law , which states a uniform distribution of eigenvalues in the unit circle of the complex plane when the eigenvalues are of a asymmetric random matrix of which the elements are ...
1
vote
0answers
41 views

pierre simon laplace and his knowledge of the (Laplacian) matrices

so as we all know, there is a graph matrix called the Laplacian that is used in some eigenvalue/eigenvector/graph theory/spectral theory problems. i'm wondering if the name of this matrix is ...
1
vote
0answers
27 views

How to show that the spectral radius of a binary tree approaches exp(1) as the N tends to infinity?

How can I prove mathematically that the spectral radius of a binary tree approaches e as the number of nodes tends to infinity? I mean it is true that the increase in nodes number is exponential but ...
1
vote
0answers
48 views

Characterization of all matrices with unit spectral radius under constraint

Let $A \in \mathbb{R}^{n \times n}_{\geq 0}$ be a symmetric matrix with positive row sums $\mathbf{d} := A\mathbf{1} > 0$. I am interested in characterizing all those positive diagonal matrices $Z ...
4
votes
0answers
159 views

spectral radius (adjacency matrix) of a partitioned graph

Is the following bound on the largest eigenvalue of a partitioned graph known? It seems like it should be but I am not able to find a reference to it. Given a graph $G=(V,E)$ whose vertices are ...
0
votes
1answer
82 views

Compute eigenvalues of a regular graph.

I have a $(q^2+q)(q+1)$-regular graph. Is there some general method to compute the eigenvalues of the adjacency matrix of a $k$-regular graph explicitly? Or could we estimate its eigenvalues? Thank ...
0
votes
0answers
54 views

Controlling the spectral radius of a matrix product

Given a binary $n \times m$ matrix $B$, I want to find a real $m \times m$ diagonal matrix $D$ that minimizes the spectral radius of $BDB^T$, subject to the constraints: $Tr(D) = 0$. $\|D\|_{F1} = ...
0
votes
1answer
91 views

how do I compute the eigenvectors for spectral clustering from a singular value decomposition?

I am implementing spectral clustering following A tutorial on spectral clustering. After preparing the Laplacian matrix $L^{n \times n}$, I compute the Singular Value Decomposition $U \Sigma V^{*}$. ...
0
votes
2answers
400 views

Rank of adjacency matrix vs rank of graph Laplacian

What is the relation between rank of the adjacency matrix of a graph and rank of the corresponding graph Laplacian matrix?
0
votes
1answer
55 views

Are these equivalent representations (labelled graph and adjacency matrix)?

This is an example from Wikipedia's page on adjacency matrices, which from the site's format seems to be suggesting equivalence between the simple diagram below, left, and the abstractly represented ...
3
votes
0answers
84 views

Constructing a directed graph from its spectrum

This is related to the following question from cs theory stack exchange: http://cstheory.stackexchange.com/questions/3742/reverse-graph-spectra-problem So it seems as if given a sequence of real ...
3
votes
0answers
40 views

Is the upper Cheeger Inequality tight?

The (upper) Cheeger Inequality says: Let $G$ be an unweighted, undirected, regular graph of degree $d$. Let $\lambda_2$ be the second eigenvalue of the Laplacian matrix of $G$, and let $\phi(G)$ ...
3
votes
0answers
129 views

What can we say about two graphs if they have similar adjacency matrices?

Suppose we have two (finite, simple, undirected) graphs, what can we say about these graphs if they have similar adjacency matrices? Observations to begin with: If $G_1$ and $G_2$ are isomorphic, ...
1
vote
1answer
73 views

cluster validation and determining number of clusters

I want to find number of cluster in the real world data set. So, I validate the spectral clustering by using some indexes as shown in figures below? But as you seen in figures the results are very ...
0
votes
0answers
125 views

Variance of the first return time of a simple random walk on an hypercube graph

I am trying to solve this problem.... I have a simple random walk on a $d$-cube (finite graph). At each vertex of the graph, the particle chooses one of $d$ edges equally likely. I need to calculate ...
1
vote
1answer
93 views

What does small eigenvalue gap imply for a graph?

Knowing a graph has good expansion has well-known implications. What can we say about graphs with $1-\lambda = O(\log n/n)$, where $1-\lambda$ is the difference between the two largest eigenvalues of ...
2
votes
1answer
93 views

Connection between the Tutte and characteristic polynomials?

Both the Tutte polynomial $T_G(x,y)$ and the characteristic polynomial $\phi_G(x)$ encode a great amount of structure of the input graph $G$. I've read somewhere that the Tutte polynomial has a kind ...