The spectral-graph-theory tag has no wiki summary.
0
votes
0answers
52 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
110 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 ...
16
votes
1answer
413 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 ...
10
votes
0answers
114 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 ...
9
votes
0answers
110 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
147 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 ...
5
votes
0answers
227 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 ...
7
votes
1answer
162 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 ...
7
votes
0answers
95 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
124 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 ...
9
votes
0answers
273 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
462 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
193 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
156 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.
16
votes
0answers
212 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 ...
7
votes
1answer
237 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
267 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
176 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 ...
1
vote
1answer
436 views
condition to make 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 ...
9
votes
2answers
269 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 ...
6
votes
1answer
376 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 ...
23
votes
4answers
600 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
256 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 ...
15
votes
2answers
521 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 ...
25
votes
2answers
491 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 ...
7
votes
2answers
331 views
Spectral techniques for genus of a graph
A generic question: are there any spectral techniques to estimate the genus of a graph? I am interested in bipartite graphs.
20
votes
6answers
870 views
Introduction to spectral graph theory
What are the basic references? Are there any good, high-level surveys of SGT and its applications to CS in general and machine learning more specifically?
