All Questions
Tagged with spectral-graph-theory co.combinatorics
12 questions
9
votes
3
answers
356
views
Spectrum of orthogonality graph (2)
The orthogonality graph, $\Omega(n)$, has vertex set the set of $\pm 1$ vectors of length $n$, with orthogonal vectors being adjacent.
I am only interested when $4|n$, since otherwise $\Omega(n)$ is ...
- 421
17
votes
1
answer
673
views
Graph embeddings in the projective plane: for the 35 forbidden minors, do we know their Colin de Verdière numbers?
The Graph Minor Theorem of Robertson and Seymour asserts
that any minor-closed graph property is determined by a finite set
of forbidden graph minors. It is a broad generalization e.g. of the ...
- 6,917
8
votes
3
answers
498
views
Where does $2\sqrt{d-1}$ come from in Ramanujan graphs?
Ramanujan graphs are the best spectral expanders: $\lambda_2 \le 2\sqrt{d-1}$. I'm looking for some intuition for this value $2\sqrt{d-1}$.
Friedman showed that every random $d$-regular graph ...
- 1,161
7
votes
1
answer
952
views
Roots of matching polynomial of graph
At the end of this preprint, I make the following conjecture concerning the roots of the matching polynomial:
If a graph $G$ is connected and contains a cycle, then the spectral radius of $G$ ...
- 674
7
votes
1
answer
358
views
Co-spectral fractional isomorphic graphs with different Laplacian spectrum
I am looking for two undirected graphs $G$ and $H$ of the same order (i.e., they have the same number of vertices) such that $G$ and $H$ are
cospectral (i.e., their adjacency matrices $A_G$ and $A_H$ ...
- 493
6
votes
3
answers
443
views
Number of trees with the same matching number
Let $\sigma(n,m)$ be the number of trees with $n$ vertices $\{ v_1, \dots, v_n \}$ such that the matching number (the size of a maximum matching) is $m$.
I have been trying to compute the value of $\...
- 201
5
votes
0
answers
267
views
(Connected) Cayley graphs of PSL(2,q) from (2,3,n)-triples
Let $G = PSL(2,q)$. I'm interested in the Cayley graphs of $G$ generated by triples $(A,BAB^{-1},B^{-1}AB)$, where $A, B \in G$ are elements of order $2, 3$ respectively: such a triple generates all ...
- 3,612
5
votes
1
answer
980
views
"Nice" eigenvectors for (square of) adjacency matrix of a bipartite graph?
Let $G$ be a bipartite graph, and let $A$ be its adjacency matrix.
I was wondering in this case whether $A^2$ will have nice eigenvectors that reflect combinatorial structure of the graph. I'd be ...
- 53
5
votes
0
answers
397
views
spectrum of orthogonality graphs
The orthogonality graph $\Omega(n)$ with $2^n$ vertices is the graph with vertex set $\{-1,+1\}^n$, with two vertices being adjacent if and only if they are orthogonal (as vectors in the standard ...
- 421
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
2
votes
0
answers
63
views
Antipodal vertices in spectral graph embeddings
Suppose your are given an antipodal graph $G=(V,E)$, that is, for every vertex $v\in V$ there is a unique maximally distant vertex $v'\in V$.
Under which condistions does the following hold:
If $\...
- 13.6k
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