Search Results

$G$ is $(n/2, d, c)$-expander if $h(G) \ge c$ and all degrees of the vertices of $G$ is at most $d$. I would like to somehow convert such graph into an algebraic expander. … And is there a better way to extract an algebraic properties from a combinatoric expander? Is there a way to get mixing lemma for non-disjoint sets? …

When I search about expander graphs in google I see a lot of articles about expander Cayley graphs. … Now my questions are as follows: Are all expander regular graphs are Cayley, or there is a special case of connected prime-order expander regular graphs which are not Cayley (specially graphs that constructed …

A set of $d\times d$ unitary matrices $\{U_1,\cdots,U_n\}$ is called a quantum expander if the identity matrice is the only eigenvector of the linear map $\mathcal{M}(X)=\frac{1}{n} U_i X U_I^{+}$ corresponding … Is there an explicit construction, matrix presentation, of a quantum expander with $n<< d$ and $\lambda<1/10$. …

One often reads that expander graphs look locally like trees. … Now, girth is not very robust but you might expect that expander graphs contain only few short cycles in general. …

I was told that this graph is known to be an expander, but the person who told me this couldn't recall where exactly this graph has been studied. Does anybody know the reference? Thanks! …

Consider a sequence of expander graphs ($G_n$); say $G_n$ has $n$ vertices. Remove $o(n)$ vertices (and the edges emanating from these vertices) and cut $o(n)$ edges. …

Deleting few edges from a complete graph leaves a good expander. What's the proportion of edges that one needs to remove to make the graph a bad expander? Or, is there any probabilistic result? …

Expander graphs ("sparse graphs that have strong connectivity properties") burst onto the mathematical scene around the millennium, but I have not been successful in tracing the origin of (a) the concept … , and (b) the name expander. …

Let $G=(L,R,E)$ be a bipartite d-regular $(\alpha, \varepsilon)$ 1-sided expander (from left to right), and let $\gamma \geq 1/d $ a constant. for every $v \in R$ let $r_v$ be an equivalence relation defined … Does $G$ (or its largest connected component, if it does not remain connected) remain an expander after this process? …

Note that this is stronger than what the expander mixing lemma guarantees for expander graphs with $d=n/2$. Has this particular property been studied already? …

Given an expander graph family (an injective sequence of graphs with uniformly bounded vertex degree and a Cheeger constant/Laplacian spectral gap uniformly bounded away from zero). … However, I am not very familiar with the standard expander constructions, so I am hoping that the community can help. Thank you very much! …

Consider a $d$-regular infinite transitive expander graph $G$, and let $B_r$ be a ball of radius $r$ in $G$. Can one place any upper bounds on the expansion of $B_r$? … The reason for this is that expander graphs are locally tree-like, and finite trees -- which is what I am imagining obtaining upon restricting to $B_r$ -- are the worst possible expanders. …

What are examples of expander family of 3-transitive Schreier graphs? Meaning for an action that is 3-transitive. It is better to have an option for randomization. … We know that choosing 2 elements at random in a simple Lie group leads to expander family of Cayley graphs. …

For example, random constant degree graphs have "few" short cycle, and after removing edges from the short cycle, the resulting graph is high-girth expander with bounded degrees. …

Now, call a $d$-regular graph $G = (U, V, E)$ a $(k, \varepsilon)$-expander if for any $S \subset U$ with $|S| \leq k$ it holds that $|\mathcal{N}(S)| > (1- \varepsilon)d |S|$. … It is true that if $n \geq 2k \geq 2$ and $\varepsilon > 0$ there exists a $(k, \varepsilon)$-expander with $d = \mathcal{O}(\log(\frac{n}{k})/\varepsilon)$ and $m = \mathcal{O}(k \log(\frac{n}{k})/\varepsilon …