Questions tagged [expanders]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
0answers
9 views

bipartite d regular expender explicit construction

I am looking for an explicit (and simple) construction of a d regular bi bipartite graph which is an expander. I searched the web and didn't find any sufficient answer. The only explicit graph I did ...
2
votes
0answers
6 views

Motivation behind the definition of order-$k$ (edge) expansion?

I'm trying to understand the motivation behind the idea of order-$k$ (edge) expansion for partitions of a graph, defined below: For simplicity, let's focus on $d$-regular graphs. The definitions I'm ...
2
votes
0answers
27 views

Random unbalanced bipartite graphs are good small set expanders

My question is about small set expansion properties of random unbalanced bipartite graphs. Fix a positive $\delta<1/2$, and a positive integers $n,m,d$. Let us call a bipartite graph $\mathcal{G}$...
1
vote
1answer
88 views

Expander Graph - Is the following graph family an expander graph?

Consider the family of graphs of degree $6$ with vertex set $V_n=(a, b, c)$ for all $0\leq a, b, c \leq n-1$ with $(a,b,c)$ being connected to $(a-1, b, c),(a+1, b,c), (a, b-1, c), (a, b+1, c), (a,b,...
4
votes
1answer
231 views

Amplifying the correctness of $\mathsf{RP}$ algorithms using expander graphs

A graph $G = (V, E)$ is called an $(n, d, \varepsilon)$-expander if the graph has $n$ vertices, maximum degree $d$, and satisfies the following expansion property: for every subset $W\subset V$ such ...
5
votes
1answer
267 views

Random Graph is a good expander

If a (n,d) random graph is a n-vertex graph defined as : Choose d random permutations $\pi_1 \ldots \pi_d $, from [n] to [n]. Take edge (u,v) if $v = \pi_i(u)$ for some i. I am trying to prove that, ...
7
votes
1answer
331 views

Relationship between graph expansion and conductance

I'm quite confused about the exact relationship between the expansion of a graph and its conductance. My first question is: Could someone point me to a reference that discusses both of these notions? ...
5
votes
0answers
44 views

Union of 2 expander graphs [closed]

Suppose that $G$ and $H$ are both expander graphs on the same node set with a second largest eigenvalue of $\lambda_G$ resp. $\lambda_H$. What can be said about the expansion of graph $G \cup H$? In ...
2
votes
1answer
108 views

Electrical resistance of expander graphs

Let $G$ be a $d$-regular expander graph. What is the electrical resistance of $G$? Is it a constant independent of the number of nodes $n$ once $d$ is large enough? If not, can we give matching upper ...
14
votes
2answers
1k views

How to practically construct regular expander graphs?

I need to construct d-regular expander graph for some small fixed d (like 3 or 4) of n vertices. What is the easiest method to do this in practice? Constructing a random d-regular graph, which is ...
5
votes
1answer
169 views

Application of Expander Codes

I need to give a talk about expander codes at university (I'm a student of computer science). Since they have been introduced to show a family of codes looking good when thinking of the Shannon ...