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

learn more… | top users | synonyms

6
votes
1answer
132 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 ...
2
votes
1answer
32 views

eigenfunctions on covering spaces of graphs

I am reading about lifts of graphs in relation to covering spaces. Before I pose my question I will explain some of the terminology. Let $G$ and $H$ be two graphs. We say that a function $f: V(H) ...
2
votes
1answer
77 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 ...
0
votes
1answer
69 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
1answer
38 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 ...
0
votes
1answer
43 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
1answer
37 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 ...
0
votes
1answer
41 views

For which spectrum is the following result for?

I don't know if I am the only one that feels this, but damn Spectral Graph Theory needs some notation change... Maybe it is because I am not so experienced in the field yet, but man every time I read ...
5
votes
0answers
188 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 ...
4
votes
0answers
172 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 ...
4
votes
0answers
76 views

Extension of Cheeger's inequality with distinguished vertices

The standard Cheeger's inequality for graph $G$ states that $\frac{1}{2}$ $\lambda$ < $\phi(G)$ < $\sqrt{2\lambda}$ where $\lambda$ is the second smallest eigenvalue of the normalized ...
3
votes
0answers
106 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
45 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
142 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, ...
2
votes
0answers
116 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 & ...
2
votes
0answers
73 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 ...
2
votes
0answers
55 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 ...
2
votes
0answers
53 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 ...
2
votes
0answers
67 views

when does a graph with normalized laplacian have a uniform degree distribution?

Consider the graph $G(A)$ with A as its adjacency matrix. Let $L$ be its Laplacian and $L_{sym} = D^{\frac{1}{2}}LD^{\frac{1}{2}}$ be the normalized Laplacian. Now let $A(L_{sym}) = I - L_{sym}$ ...
2
votes
0answers
195 views

Bounds on the maximum eigenvalue of the adjacency matrix of a graph.

I managed to proof the following result for the maximum eigenvalue: $ d_{avg}\leq \lambda_{max} \leq \Delta(G) $ where $d_{avg}$ is the average degree of the graph while $\Delta(G)$ is the maximum ...
2
votes
0answers
49 views

Properties of a generalized graph

I'll start with formulating my problem and then ask my question: To generalize a graph $Ga = (Va,Ea)$, we partition its nodes into disjoint sets. The elements of a partitioning $V$ are subsets of ...
2
votes
0answers
493 views

Is there any relation between the principal eigenvalue of sub matrix and the original matrix?

I am wondering whether there is any relation between principal eigenvalue of sub matrix and the original matrix. In fact I am facing a problem which is to select $n$ rows and $n$ columns from the ...
1
vote
0answers
33 views

What is the multiplicity of the largest eigenvalue of a graph?

The Laplacian of a graph is a symmetric positive semi-definite matrix and hence has all real eigenvalues. Is there any characterization for the multiplicity of the largest Laplacian (and/or Adjacency ...
1
vote
0answers
11 views

Weighted undirected graphs, complex Laplacian, complex eigenvalues & spectral clusering

I am rather puzzled and confused, I have been trying to get a clear understanding of how would spectral clustering work for an undirected weighted graph, I have used the normalized Laplacian, but I ...
1
vote
0answers
32 views

Fast Cholesky Factrorization for Tree Laplacians

Suppose $T_1$ and $T_2$ represent two Laplacian matrices of two spanning trees of $n$ vertices. Since the Cholesky factorization needs $O(n)$ time for each $T_i\ (i=1,2)$ due to the tree structure, ...
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 ...
1
vote
0answers
96 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
0answers
80 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 ...
1
vote
0answers
45 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 ...
1
vote
0answers
45 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
30 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
51 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 ...
1
vote
0answers
98 views

Algebraic characterization of being $P_n$-free.

Is there an algebraic way to determine from the adjacency matrix $A$ of a simple graph $G$, whether $G$ contains an induced path of fixed length $n$? I am particularly interested in the case $n=6$. ...
1
vote
0answers
47 views

spectral graph theory with “potentials”

Let G be an undirected graph with bounded degree and n vertices. Let L[G] be the corresponding graph Laplacian, which is a symmetric $n \times n$ matrix. Let V be an $n \times n$ diagonal matrix. I am ...
1
vote
0answers
164 views

Is there a simple interpretation of the eigenvectors of a graph (visualizable?)?

I want to understand eigenvectors obtain from graphs (adjacency matrices) in an analogous way as they are interpreted from principal component analysis of a set of images, which is easy:Eigenfaces ...
1
vote
0answers
130 views

Spielman. Spectral Graph Theory Proposition

Spielman says in Lecture 3: Laplacians and Adjacency Matrices Fiedler’s Theorem will follow from an analysis of the eigenvalues of tri-diagonal matrices with zero row-sums. These may be viewed as ...
0
votes
0answers
5 views

Faber-Krahn inequality for domain in Z^d with nearest-neighbor connections

In $\mathbb{R}^d$ there is a theorem that if you are looking for the first Dirichlet eigenvalue $\lambda_1$ of a domain $D \subset \mathbb{R}^d$ with a given volume $V$, then $\lambda_1$ will be ...
0
votes
0answers
7 views

correlations between network parameters

I am calculating spectral densities for networks. Is there a reason why skewness and kurtosis would, in general, be correlated across many networks? That is, as a feature of networks rather than ...
0
votes
0answers
18 views

Spectral methods with linear programming

Is it possible to model and solve some fundamental spectral methods (say Singular-Value Decomposition) with (Integer?) Linear Programming? Update: say you want to do SVD. Can you model it as a ...
0
votes
0answers
17 views

Understanding minimum cuts and normalized minimum cuts in a graph.

I came across minimum and normalized minimum cuts while reading about image segmentation using graphs. I can't seem to understand these two notions. It will be great if someone can explain these two ...
0
votes
0answers
11 views

Modifications to the definition of graph Laplacian?

Many people have defined various definitions for graph Laplacian. For example see here [1]. What is common between various definitions of Laplacian that makes all of them ``Laplacian"? For example ...
0
votes
0answers
24 views

Multigrid eigensolver: properties of the Laplacian at different levels of the hierarchy

I'm not entirely sure this is the right place, but I could really use some help. I'm attempting to implement a hierarchical eigensolver specific to graph Laplacians $L_0$, but after one iteration, the ...
0
votes
0answers
14 views

K-way Undirected Weighted Graph Partition with K Vertices Pre-Assigned

I have an undirected weighted graph to be partitioned into k subgraphs with minimal edge weight between the partitions and k of the vertices are constrained to lie in separate partitions. I am ...
0
votes
0answers
50 views

Kac's question 'Can one hear the shape of a drum' and Sunada method, a clarification

I'm reading the article http://www.math.upenn.edu/~kazdan/425S11/Drum-Gordon-Webb.pdf, , where Gordon and Webb describe in a simple a way the contruction of a pair of isospectral but non isometric ...
0
votes
0answers
29 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?
0
votes
0answers
29 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$. ...
0
votes
0answers
37 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 ...
0
votes
0answers
15 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
33 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 ...
0
votes
0answers
136 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 ...