Questions tagged [spectral-graph-theory]
The spectral-graph-theory tag has no usage guidance.
57 questions
0
votes
1
answer
82
views
Entries of the Inverse Laplacian
Let $L$ be a graph Laplacian. What is the meaning of the entries of its (pseudo)inverse $L^{-1}$? In other words, are there any interpretations which might help with understanding the entries of $L^{-...
- 141
0
votes
1
answer
95
views
Spectral sparsification of graphs with negative edge weights
I am reading the following well-known paper on spectral sparsification of weighted graphs: https://arxiv.org/pdf/0808.4134.pdf. Page 2 contains most of the definitions relevant to this question.
It is ...
- 1
2
votes
0
answers
76
views
Can we always find a graph with a given algebraic connectivity?
This is crossposted from math stackexchange. This is my first time posting here, so let me know if I'm doing something wrong.
I would like to experiment with various spectral properties of graphs, ...
- 121
1
vote
1
answer
80
views
When can partial spectral sparsifiers be combined?
A few important papers about spectral sparsifiers and friends contain a technical idea that involves building many different sparsifiers that each "partially" solve the problem, and then combining ...
- 2,591
1
vote
1
answer
887
views
Fast Computation of First k Eigenvectors of Graph Laplacian
I'm looking for references for the following; Given the unnormalized Laplacian matrix of a graph $L = D - A, ~ L \in \mathbb{R}^{n\times n}$
Algorithm(s) to efficiently estimate the first $k$ (...
3
votes
1
answer
248
views
How is SDP an extension of spectral algorithms?
In one of his lectures, Uri Feige described semidefinite programming (SDP) as
... an algorithmic technique that extends both linear programming and spectral algorithms.
I know the basic ...
- 630
1
vote
0
answers
94
views
Purely spectral algorithms for the minimum spanning tree problem
There are many algorithms that address the MST problem, from classical (Boruvka, Prim, Kruskal), optimal (Pettie et al.) to their distributed variants (Bader et al.).
However, I fail to find any ...
- 111
3
votes
0
answers
1k
views
Eigenvalues of adjacency matrix of a connected bipartite graph
Let $G=(V,E)$ is a connected d-regular bipartite graph with the same number of vertices on both sides of the bipartition. It's known that that the largest eigenvalue of its adjacency matrix would be d,...
- 419
2
votes
0
answers
93
views
The algebraic connectivity of graphs with large isoperimetric number
I asked this question on MO, but no answer. Let $G = (V,E)$ be an undirected graph with maximum degree $\Delta$. the isoperimetric number of $G$, denoted $i(G)$, is defined by
$$i(G) = \min_{|S| \leq |...
- 705
1
vote
0
answers
167
views
Spectra of Cayley Graphs for non-Abelian Groups
There appears to be much interest in the subject of the spectra of Cayley graphs. Indeed it appears that the spectra are highly related or may be computed through the irreducible representations of ...
- 225
1
vote
0
answers
73
views
Sparse-cut approximation for well connected graphs
Theorem: For any graph $G=(V,E)$, there is a polynomial time algorithm that finds a cut $S \subseteq V$ with conductance at most $\sqrt{2\big(1 − \lambda(G)\big)}$.
If I understand UGC correctly, ...
- 791
1
vote
1
answer
1k
views
Is the value of $\max_{f:V\rightarrow [\frac{-1}{2},\frac{1}{2}], \\ \sum_{v}{f(v)}=0} \frac{f^T L_G f}{n-f^Tf}$ polynomially computable?
For a graph $G$ on $n$ vertices, what is the value of following ratio:
$$\max_{f:V\rightarrow [\frac{-1}{2},\frac{1}{2}], \\ \sum_{v}{f(v)}=0} \frac{f^T L_G f}{n-f^Tf} ,$$
where $L_G=D_G-A_G$ is ...
- 705
8
votes
2
answers
1k
views
Dichotomy of the spectra of directed graphs
Compared to spectra of undirected graphs, which correspond to symmetric matrices, the spectra of directed graphs is not very well known:
It is known that a directed graph $G = (V,E)$ has an adjacency ...
- 1,224
5
votes
1
answer
207
views
About some possible optimality properties of Ramanujan graphs
The Ramanujan graphs are optimal from the Alon-Bopanna point of view but..
Is there any sense in which one can call Ramanujan graphs to be the "optimal" spectral sparsifiers? (Reference : http://...
- 654
2
votes
0
answers
157
views
Construction of a graph which has regular subgraphs at each iteration of a recursive process
I am studying Graph Isomorphism and also trying to figure out the complexity of a certain class of graph. The graph I am studying at the moment is described below
Description :
$G$ is a $r$ regular ...
- 553
8
votes
0
answers
314
views
Are there sparsifiers that approximate vertices rather than edges?
Originally introduced by Benczur and Karger, cut sparsifiers let one take a dense graph $G=(V,E)$ and produce a weighted sparse graph on the same vertex set, where - only knowing the sparse graph ...
- 11k
3
votes
0
answers
166
views
About the sparsest-cut question
Can someone kindly help clarify as to exactly what is the generally accepted definition of the "sparsest cut" problem for a graph?
(Isn't the set which achieves the Cheeger constant for a ...
- 281
24
votes
2
answers
2k
views
Is the Cheeger constant $\mathsf{NP}$-hard?
I have read in uncountably many articles that determining the Cheeger constant of a graph is $\mathsf{NP}$-hard. It seems to be a folk theorem, but I have never found either a quote or a proof for ...
- 343
9
votes
1
answer
1k
views
About the small set expansion conjecture
Given a graph $G=(V,E)$ and a $\delta > 0$ one wants to calculate $h(G,\delta)=min_{\vert S\vert \leq \delta \vert V \vert } \phi(S)$. ($\phi(S) = \frac{ E(S,\bar{S}) }{d min \{\vert S \vert , n - \...
- 281
5
votes
1
answer
203
views
Upper bounds on higher order eigenvalues of regular graphs
Suppose $G$ is an undirected $d$-regular $n$-vertex graph for some constant $d$. Let $\lambda_k$ be the $k$-th largest eigenvalue of the normalized laplacian $L$ of $G$ (defined as $I - \frac{1}{d} A$ ...
- 2,492
0
votes
0
answers
125
views
Is there a diagonal matrix D such that DMD is SDD, where M is SPD matrix
Let $M$ be symmetric and positive definite matrix (SPD). It is known [1] that
if $M$ is SPD and
in addition satisfies $M_{ij}\leq 0$, for $i\neq j$ (called M-matrix)
then there is a positive ...
- 1
1
vote
0
answers
102
views
Eigenvalues of Random Regular Bipartite Graphs
I am looking for a way of getting a good estimate of the eigenvalues of random bipartite d-regular graphs. The literature has very precise values the proofs of which are very involved and since I am ...
- 666
2
votes
0
answers
214
views
Graph sparsification
I would like to ask if any one is aware of any results related to graph sparsification with bounded degrees? What I mean is anyone aware of graph sparsification results such that the resultant graph ...
- 141
0
votes
1
answer
120
views
References to learn more about graph laplacian.
I have vaguely heard of this connection between random matrix theory and graphs (the spectral gap of their laplacians) on compact Riemann surfaces.
Can someone give a pedagogic reference which helps ...
- 281
0
votes
0
answers
286
views
introduction to spectral geometry
In the paper Belkin, Mikhail, and Partha Niyogi. "Laplacian eigenmaps and spectral techniques for embedding and clustering." In NIPS, vol. 14, pp. 585-591. 2001 The ...
- 141
1
vote
0
answers
148
views
Constructing a digraph from its spectrum
This is related to the following question which has already been explored:
Reverse Graph Spectra Problem?
So it seems as if given a sequence of real numbers, it is not always possible to generate a 0-...
- 393
10
votes
0
answers
171
views
Number of graphs with prescribed spectrum
I have a question relevant to the number of graphs with prescribed spectral ratio.
Let $A$ be the adjacency matrix of a graph on $n$ vertices. Let $\lambda_i$ be its $i$-th largest (signed) eigenvalue....
- 1,356
5
votes
2
answers
2k
views
Size of MAXCUT from eigenvalues
Is there an interpretation of MAXCUT using eigenvalues of the graph that yields constant factor approximation to MAXCUT?
Can the estimates provide sharp lower bound to MAXCUT?
- 13.3k
7
votes
0
answers
392
views
Spectral Graph Theory and Matroid Theory
I have just started grad school this year and I have been into Spectral Graph Theory for some time now. Recently I got introduced to Matroid Theory and although I know the field has been around for ...
0
votes
0
answers
212
views
Multi-way spectral partitioning and higher-order Cheeger inequalities
I am reading the paper above by Lee, Gharan and Trevisan, and I am having trouble with lemma 4.8 on page 23. How do we form the set $T_1, \ldots, T_{r'}$ such that $r'>(1-\delta/2)k$ and each set $...
2
votes
0
answers
164
views
Graph has several MST what does it mean combinatorically?
This question is not theoretical, it's about combinatorial meaning.
In graph theory there is a notion of complexity of a graph, which is equal to the number of spanning trees in a graph, which ...
- 605
1
vote
1
answer
461
views
Second eigenvalue and the last eigenvalue
Note : All eigenvalues that I would referring to below would of the adjacency matrix of the graph
My question arises from having read about Expander Graphs from a few different sources. The most ...
- 666
19
votes
1
answer
1k
views
Count the number of spanning trees fast
Let $t(G)$ denote the number of spanning trees in a graph $G$ with $n$ vertices. There is an algorithm that computes $t(G)$ in $O(n^3)$ arithmetic operations. This algorithm is to compute $\frac{1}{n^...
- 605
13
votes
0
answers
198
views
Complexity to compute the eigenvalue signs of the adjacency matrix
Let $A$ be the $n\times n$ adjacency matrix of a (non-bipartite) graph. Assume that we are given the amplitudes of its eigenvalues, i.e., $|\lambda_1|=a_1,\ldots, |\lambda_n|=a_n$, and we would like ...
- 1,356
13
votes
0
answers
188
views
Generating a random graph with constraints on spectrum
Consider two sequences $u_1 \geq u_2 \geq ... \geq u_n$ and $l_1 \geq l_2 \geq ... \geq l_n$ with $u_i \geq l_i$ for every $i$. Let $\mathcal{G}(l_{1:n},u_{1:n})$ be all undirected unweighted simple ...
- 10.3k
4
votes
2
answers
616
views
Optimal upper bound on the number of non-isomorphic graphs with certain parameter
What are the optimal (or best known) bounds (preferably exact or else asymptotic but not expectation on random graphs) on the number of non-isomorphic (unlabelled) simple (no self-loop), undirected ...
- 1,311
7
votes
0
answers
563
views
Which problems in graph theory can be stated as quadratic programs?
There seem to be many very interesting problems in graph theory that can be written in the form of maximizing/minimizing a quadratic form on either the Adjacency ${\bf A}$ or the Laplacian matrix ${\...
- 1,356
8
votes
1
answer
378
views
Bounds on the smaller eigenvalues of the adjacency matrix of a graph
Are there any known (non-trivial) bounds (combinatorial in nature, based on poly-time computable properties of a graph) on the third, down to the smallest, eigenvalue of an (un-weighted) adjacency ...
- 1,356
8
votes
0
answers
139
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 ...
- 81
11
votes
0
answers
147
views
expansion with respect to p-norms for p other than 2
Suppose I have an $d$-regular expander graph with $n$ vertices, where the stochastic version of its adjacency matrix $A$ (with entries $1/d$ and zero) has second eigenvalue $\lambda$.
Let $x \in {\...
- 119
13
votes
1
answer
1k
views
Sampling from Multivariate Gaussian with Graph Laplacian (inverse) Covariance
We know from e.g. Koutis-Miller-Peng (based on work of Spielman & Teng), that we can very quickly solve linear systems $A x = b$ for matrices $A$ that are the graph Laplacian matrix for some ...
- 681
7
votes
2
answers
2k
views
In a resistor network, is there any relation between the shortest path and the maximum electric current path?
Consider a shortest path problem between the source $s$ and sink $t$ in an undirected weighted graph. There's a well known algorithm such as Dijkstra's algorithm that solves this problem.
Naturally, ...
8
votes
0
answers
344
views
Combinatorial method for computing the largest eigenvector of the adjacency matrix of a graph
Given a connected and non-bipartite graph $G=(V,E)$ with vertex set $V=\{1,\cdots, n\}$, let $A$ denote its adjacency matrix and let $deg(i)$ denote the degree of vertex $i$. Let $D$ be a diagonal ...
0
votes
1
answer
195
views
Estimating graphs using random cuts
How easy is it to estimate a graph by observing only a few random cuts? Is there prior work related to this? I did google but could not find anything concrete.
Any help would be appreciated. Thanks.
- 17
17
votes
1
answer
425
views
Geometric picture behind quantum expanders
(also asked here, no replies)
A $(d,\lambda)$-quantum expander is a distribution $\nu$ over the unitary group $\mathcal{U}(d)$ with the property that: a) $|\mathrm{supp} \ \nu| =d$, b) $\Vert \mathbb{...
- 2,806
9
votes
1
answer
584
views
Applications of Spectral Graph Theory in Information and Coding Theory
I wanted to find out what are some application of SGT in the area of information and coding theory and maybe communications. The most related that comes to mind is the work on Expander Codes
Michael ...
- 1,356
5
votes
1
answer
557
views
Bipartite maximum matching size from eigenvalues
Supposing we know the adjacency matrix $\mathcal{A}_{G}$ of a given regular (or irregular) bipartite graph $G$. Are there good lower and upper bounds to the size of maximum matching from the graph's ...
- 2,228
9
votes
0
answers
292
views
Spectral gap for random bipartite regular graphs
For a graph $G$, let its Laplacian be $\Delta =I − D^{−1/2}AD^{−1/2}$, where
$A$ is the adjacency matrix, $I$ is the identity matrix and $D$ is the diagonal matrix with vertex degrees. I'm ...
- 2,806
5
votes
2
answers
3k
views
Making an adjacency matrix positive semidefinite
I would like to ask how can we transform an adjacency matrix of a graph into a positive semidefinite matrix. Of course, we could set self loops, but I do not know of any result indicating how we can ...
- 573
11
votes
2
answers
412
views
Maximum imbalance in a graph?
Let $G$ be a connected graph $G = (V,E)$ with nodes $V = 1 \dots n$ and edges $E$. Let $w_i$ denote the (integer) weight of graph $G$, with $\sum_i w_i = m$ the total weight in the graph. The average ...
- 349