All Questions
Tagged with sp.spectral-theory co.combinatorics
19 questions
5
votes
1
answer
299
views
Combinatorial Skeleton of a Riemannian manifold
In Chung and Yau's paper: "A combinatorial trace formula" (MSN), they proved
a combinatorial version of Selberg's trace formula for lattice graphs.
I learned also in the setup that it makes sense to ...
- 5,230
2
votes
2
answers
539
views
Graph with complex eigenvalues
The question I am wondering about is:
Can the discrete Laplacian have complex eigenvalues on a graph?
Clearly, there are two cases where it is obvious that this is impossible.
1.) The graph is ...
user144765
1
vote
1
answer
117
views
Spectral bound for maximum clique $k(G)$ in a permutation graph
Let $\pi \in S_n$ be an arbitrary permutation. By permutation graph, we refer to a simple graph with nodes $[n]$ and edges that connect pairs of nodes that appear sorted in $\pi$. Formally, $G=(V=[n],...
- 187
1
vote
0
answers
114
views
Bounds on spectral radius using chromatic number
I am struggling with this question:
If I have a connected graph $G$ on $n$ vertices and $m$ edges with chromatic number $d$ then how can I give a bound(lower and upper) on its spectral radius in ...
- 135
0
votes
3
answers
308
views
Clustering on tree
I am looking for a method that would identify clusters in a tree-like structure. In the figure below you can see a very simple example where one can visually identify distinct branches with a lot of ...
- 237
8
votes
2
answers
323
views
Matrix rescaling increases lowest eigenvalue?
Consider the set $\mathbf{N}:=\left\{1,2,....,N \right\}$ and let $$\mathbf M:=\left\{ M_i; M_i \subset \mathbf N \text{ such that } \left\lvert M_i \right\rvert=2 \text{ or }\left\lvert M_i \right\...
- 225
4
votes
0
answers
240
views
Does the zeta regularized Laplacian determinant measure the volume of some parameter space? How many "spanning trees" on a manifold?
Let $(M,g)$ be a Riemannian manifold, with Laplacian $\Delta$. If $\lambda_i$ are the nonzero eigenvalues of $\Delta$, we can define the zeta function $\zeta(s) = \Sigma \lambda_i^{-s}$. By analytic ...
- 1,462
0
votes
1
answer
138
views
On sum of matrices
Suppose we have a matrix $M\in\Bbb Q^{n\times n}$ with no $0$ elements and we write as sum of two matrices $M_1$ and $M_2$ on following constraint.
$M_{1,ij}=M_{ij}$ and $M_{2,ij}=0$ or $M_{1,ij}=0$ ...
- 13.9k
1
vote
0
answers
51
views
Relation between nullity of components to its parent graph
Let $G$ be an undirected graph and the corresponding adjacency matrix be $A$. Let $v$ be a cut-vertex of $G$. Let $G_1, G_2,\dots, G_k$ are the connected components of the induced graph $G-v$ ( the ...
- 640
15
votes
2
answers
819
views
An orbit of symmetric polynomials
Consider the ring of polynomials $R:=\mathbb{Z}[x_1,x_2,x_3]$. Define the operators $E, I:R\rightarrow R$ by $Ef(x_1,x_2,x_3)=f(x_1-1,x_2,x_3)$ and the identity $If=f$.
Let $\mathcal{L}:R\rightarrow R$...
- 43.2k
0
votes
1
answer
414
views
Exact formula for computing n-step transition probability of random walks with self-transitions
Consider a semi-infinite random walks $X_n$, $n=0,1,2,\ldots$, whose state space is a set of consecutive integers and whose one-step transition probabilities are $P_{ij}=\mathrm{Pr}\{X_{n+1}=j|X_n=i\}$...
- 1
1
vote
0
answers
232
views
Lp norm estimates for the inverse of the Laplacian on a graph
I am looking at a finite connected graph and I would like to know what is the best [i.e. largest] constant $\lambda_p$ in
$$
\sum_x f(x) =0 \implies \| \Delta^{-1} f\|_{\ell^p} \leq \lambda_p^{-1} \|...
- 4,432
0
votes
1
answer
269
views
Decomposition of a regular graph and connected subgraphs
I have asked almost same question earlier. I have been told that my question was poorly written, so I am trying to write it more clearly in this post. Also, this time I would be a little different in ...
- 267
1
vote
0
answers
455
views
Possibility of Disconnected Subgraphs of a $k$ Connected $r$ regular Graph under a given condition
Context: Given a adjacency matrix A of a $r$-regular graph $G$ (not complete graph $K_{r+1}$) . $G$ is $k$ connected.
The matrix A can be divided into 4 sub-matrices based on adjacency of vertex $x ...
- 267
13
votes
3
answers
4k
views
What is a "Ramanujan Graph"?
I noticed an apparent conflict in the definition in literature about what is a "Ramanujan graph, which I was wondering if someone could kindly clarify.
(1)
The Hoory-Linial-Wigderson review on ...
- 1,893
4
votes
1
answer
418
views
What is the spectrum of the Rado graph?
Isn't this question self-explanatory? There is a lot of literature about the Rado graph $R$ in various places. This graph is also known as the "Random Graph" because a countable random graph is ...
- 1,277
12
votes
6
answers
693
views
Invertibility of a certain matrix indexed by the Hamming cube
For reasons which the margin of this page is too small to hold, I have been reading parts of a recent paper by O. Selim
On submeasures on Boolean algebras, arXiv 1212.6822v3
and in Section 7 the ...
- 25.8k
3
votes
0
answers
185
views
spectrum of a polygon and zeta function
Let $\Delta(x,y) = 1,0$ according to whether $(x,y)$ is in some polygon (symmetric with respect to the diagonal axis).
E.g. The convex hull of three points (taken from a paper on dominoes)
$$ \...
- 22.8k
13
votes
2
answers
1k
views
Combinatorial proof of (a special case of) the spectral theorem?
The spectral theorem for a real $n \times n$ symmetric matrix $A$ says that $A$ is diagonalizable with all eigenvalues real. If $A$ happens to have non-negative integer entries, it can be interpreted ...
- 118k