Questions tagged [expanders]

An expander is a sparse (low degree) graph with high "expansion," measured in one of several ways; typically akin to the minimum ratio of the size of a subgraph boundary to the subgraph's volume.

51 questions
Filter by
Sorted by
Tagged with
47 views

d-regular graphs and edge expanders

Show that there is no (n, d, ρ)-edge expander for ρ > 0.5 Is this statement even true? My attempt: Let n = 2, then we can have 2 vertices, A and B. Let d = 1, therefore there is an edge between A ...
105 views

High-dimensional expanders through the lens of algebraic topology

High-dimensional expanders are used in a few areas of TCS (coding theory, sampling, probably some others). While I'm not too familiar with their usage, I know that in sampling they can be useful to ...
• 43
1 vote
56 views

Constructing lossless conductors using zigzag product - a doubt

Reference - this survey: https://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf I am reading the section on constructing lossless conductors using a bipartite variant of zigzag product (section 10,...
• 91
45 views

105 views

• 775
498 views

Bi-partite expander graphs

My question relates to bi-partite expander graphs, defined as bi-partite graphs on $n$ left vertices, $m$ right vertices, constant left-degree $k$, such that For any linear-sized subset $S$ of the ...
• 1,224
371 views

Error reduction with expanders and derandomization

In "standard" error reduction with an expander, if a randomize algorithm uses $n^d$ random bits, we need $n^d+O(n)$ random bits to achieve $2^{-O(n)}$ error probability. Now, if the algorithm has a ...
622 views

Simple Constructions of Special Graph Families

Consider the following definition, taken from Chung's 1978 paper: An $(n, m)$-concentrator is a graph with $n$ input vertices and $m$ output vertices, $n \ge m$, having the property that, for ...
• 16.5k
553 views

Terminology for sparse cuts in graphs

I have found some ambiguity in how the graph parameters edge-expansion, uniform sparsest cut and conductance are defined and denoted. My questions are: what are the definitions that best match the ...
• 4,902