Questions tagged [expanders]
The expanders tag has no usage guidance.
13
questions
1
vote
1answer
19 views
How to prove the existence of the spectral expander with the given parameteres?
I need to prove the existence of the $(1944, 144, 0.5)$ spectral expander. I tried to construct it using tensor product of the following graphs:
$$
(1944, 144, 0.5) = (9^2, 9, 1/3) \otimes (24, 16, 0....
1
vote
1answer
58 views
Unique-neighbor expander
I want to solve Problem 4.10 from Randomness by Salil Vadhan. https://people.seas.harvard.edu/~salil/cs225/spring15/PS3.pdf
Consider a bipartite expander $G$ with left degree $D$ so that every subset ...
1
vote
0answers
32 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
9 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
30 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}$...
2
votes
1answer
102 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,...
5
votes
1answer
298 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
343 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
591 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
48 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
117 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
2k 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
197 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 ...
