Questions tagged [expanders]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3 votes
1 answer

Increasing families of expander graphs

I would like to know if there is any research dealing with the problem of constructing an increasing family of expander graphs. The goal is to find a family of expander graphs $(G_i)_{i \in \mathbb{N}}...
sooolal's user avatar
  • 31
1 vote
1 answer

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....
envy grunt's user avatar
1 vote
1 answer

Unique-neighbor expander

I want to solve Problem 4.10 from Randomness by Salil Vadhan. Consider a bipartite expander $G$ with left degree $D$ so that every subset ...
Mark Regev's user avatar
1 vote
0 answers

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 ...
misha312's user avatar
  • 209
2 votes
0 answers

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 ...
theQman's user avatar
  • 557
2 votes
0 answers

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}$...
curiousperson's user avatar
2 votes
1 answer

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,...
midnight44's user avatar
5 votes
1 answer

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 ...
iHubble's user avatar
  • 207
5 votes
1 answer

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, ...
Gaganpreet's user avatar
7 votes
1 answer

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? ...
someguy3's user avatar
5 votes
0 answers

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 ...
user16400's user avatar
2 votes
1 answer

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 ...
maartje's user avatar
  • 23
15 votes
2 answers

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 ...
user2145167's user avatar
5 votes
1 answer

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 ...
smoes's user avatar
  • 163