All Questions
8 questions
4
votes
1
answer
303
views
Minimum eigenvalue of a symmetric matrix
I was solving a problem and got stuck on the following:
Let $[p] = \{1, \ldots, p\}$ where $p \in \mathbb{N}$. Let $P(n, r)$ denote the set of all injective functions from $[r]$ to $[n]$ and write a ...
- 41
0
votes
1
answer
207
views
Series analyzed in Lubotzky–Phillips–Sarnak "Ramanujan Graphs"
In the LPS paper "Ramanujan graphs" the adjacency matrix of $X^{p,q}$, for simplicity say that $p,q\equiv1\mod{4}$ and $\left(\frac{p}{q}\right)=1$ (so, nonbipartite) and $n=\lvert X^{p,q}\...
- 465
0
votes
0
answers
298
views
How is the second smallest eigenvalue of normalized laplacian bounded for random graphs?
It is well known that for any graph G following holds
$\frac{\lambda_2}{2} ≤ \phi(G) ≤ \sqrt{2\lambda_2}$, where $\phi(G)$ is the conductance of the graph and $\lambda_2$ is the second smallest ...
- 1
3
votes
1
answer
134
views
Spectral properties of half-transitive graphs
The half-transitive graphs form a curious class of graphs with some kind of intermediate symmetry that is non-trivial to achieve. More precisely, a graph is half-transitive if its symmetry group is
...
- 13.6k
6
votes
1
answer
263
views
An eigenvalue upper bound for 1-walk-regular graphs
Let $G$ be a graph and suppose that $G$ is 1-walk-regular (or, if you prefer, vertex- and edge-transitive, or distance-regular).
Let $\theta_1>\theta_2>\cdots>\theta_m$ be the distinct ...
- 13.6k
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
387
views
Relation between the sum of principal minors of different orders
Let $A$ be a symmetric (0,1)-square matrix of order $n$ having the diagonal entries zero. Let $m$ be the nullity of $A$ (number of zero eigenvalues), denoted by $\eta(A)$. Let $A_1$ be the square ...
- 640
6
votes
1
answer
583
views
Eigenvalue inequality for regular graphs
I recently proved an inequality relating some of the eigenvalues of a regular graph with each other, and I was wondering if it is already known. I was unable to find it online, and a quick skim ...
- 2,339