Search Results

I want to ask the question in two parts, (1) Is there some fundamental distinguishing property between Abelian and non-Abelian Cayley graphs? (say some specific proof technique which distinguishes …

Is it purely coincidental that the same number $2\sqrt{d-1}$ appears in these two following apparently disparate concepts? A $d-$regular graph is said to be called Ramanujan if its adjacency eigenv …

If the edges of a bipartite graph are such that they can be seen as a disjoint union of perfect matchings then will this somehow reflect in the eigenvalues of the Laplacian? It would be helpful to g …

Is there any connection known between the two? One can naturally define lifts of graphs by groups like $\mathbb{Z}_k$ and hence I wonder if representation theoretic properties can be used to say som …

if a graph with adjacency matrix $A$ and Laplacian $L$ has $k$ distinct eigenvalues then does this fact naturally help define or prove existence of a polynomial $p$ of degree $k-1$ such that $[p(A)]_{ …

Say $B$ is a real symmetric matrix of dimension $n$ and $A$ is another real symmetric matrix of the same dimension. What needs to be the bounds on (which?) norm of $B$ to ensure that $\lambda_{max …

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 expand …

Given a real symmetric matrix $A$ and a vector $v$ of the same dimension we know that the eigenvalues of $A + vv^T$ are left interlaced by the eigenvalues of $A$. But do we have any quantitative es …

Say I am given the $0/1$ adjacency matrix of an undirected graph. Also I am given a representation $\rho$ of some group $G$ and an orientation has been arbitrarily chosen along each edge. Let $E^{orie …

Let $S \subseteq V$ of a $d-$regular graph $G$ such that $\mu = \frac{\vert S \vert }{\vert V \vert } $. Let $A$ be the adjacency matrix of the graph. Then define the quantity $\phi(S)= \frac{E(S,\bar …

Is there an exposition which explains how to do this step-by-step? (I see stray references and allusions to such a thing being possible but can't locate anything concretely) Something to do with `` …

Are there any special properties known about the set of perfect matchings of $K_{n,n}$? Like any global structure of this set? Some natural way to partition it? Like is there some algebraic structure …

[Assume all groups are finite] One knows the general statement that the sum of the values of the character function on the generating set is an eigenvalue of a Cayley graph. But the above doesn't …

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 - \ve …

I am thinking about the third bullet point on page 455 here, http://www.ams.org/journals/bull/2006-43-04/S0273-0979-06-01126-8/ Can someone explain what is the argument there which seems to conclude …