Questions tagged [spectral-graph-theory]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3
votes
1answer
146 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 ...
1
vote
0answers
88 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 ...
3
votes
0answers
482 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,...
2
votes
0answers
64 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 |...
1
vote
0answers
101 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 ...
1
vote
0answers
59 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, ...
1
vote
1answer
667 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 ...
8
votes
2answers
708 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 ...
5
votes
1answer
183 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://...
2
votes
0answers
153 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 ...
8
votes
0answers
304 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 ...
1
vote
0answers
126 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 graph, ...
23
votes
2answers
1k 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 ...
8
votes
1answer
778 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 - \...
5
votes
1answer
165 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$ ...
0
votes
0answers
98 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
vote
0answers
92 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 ...
2
votes
0answers
194 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 ...
0
votes
1answer
93 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 ...
0
votes
0answers
240 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 ...
1
vote
0answers
128 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-...
10
votes
0answers
161 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....
4
votes
2answers
1k 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?
6
votes
0answers
272 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
0answers
182 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
0answers
153 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 ...
1
vote
1answer
357 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 ...
19
votes
1answer
769 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^...
13
votes
0answers
185 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 ...
11
votes
0answers
157 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 ...
4
votes
2answers
423 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 ...
7
votes
0answers
462 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 ${\...
8
votes
1answer
292 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 ...
8
votes
0answers
134 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 ...
11
votes
0answers
144 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 {\...
12
votes
1answer
966 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 ...
5
votes
2answers
1k 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
0answers
339 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
1answer
192 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
votes
1answer
327 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{...
9
votes
2answers
478 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 ...
5
votes
1answer
515 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 ...
9
votes
0answers
268 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 ...
5
votes
2answers
2k 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 ...
10
votes
2answers
362 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 ...
8
votes
1answer
794 views

Effect of different graph operations at algebraic connectivity of graph laplacian?

The algebraic connectivity of a graph G is the second-smallest eigenvalue of the Laplacian matrix of G. This eigenvalue is greater than 0 if and only if G is a connected graph. The magnitude of this ...
28
votes
4answers
831 views

Proofs obtained only through spectral graph theory

I have an increasing interest in spectral graph theory, which I find fascinating, and I've started collecting a few documents that I have yet to read more thoroughly than what I so far have. However, ...
6
votes
2answers
389 views

Terminology for sparse cuts in graphs

I have found some ambiguity in how the graph parameters edge-expansion, uniform sparsest cut and conductance are defined and denoted. My questions are: what are the definitions that best match the ...
25
votes
3answers
961 views

Reverse Graph Spectra Problem?

Usually one constructs a graph and then asks questions about the adjacency matrix's (or some close relative like the Laplacian) eigenvalue decomposition (also called the spectra of a graph). But what ...
27
votes
2answers
735 views

Papers to credit for spectral partitioning of graphs

If $G=(V,E)$ is an undirected $d$-regular graph and $S$ is a subset of the vertices of cardinality $\leq |V|/2$, call the edge expansion of $S$ the quantity $\phi(S) := \frac {Edges(S,V-S)}{d\cdot |S|...