# 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.

43 questions
Filter by
Sorted by
Tagged with
768 views

1k views

### NP-hard problems on expander graphs?

In a 2006 presentation titled EXPANDER GRAPHS - ARE THERE ANY MYSTERIES LEFT? , Nati Linial posed the following open problem: Which $NP$-hard computational problem on graph remain hard when ...
1k views

Given an undirected, regular graph $G=(V,E)$, what is the relationship between its diameter - defined as the largest distance between two nodes - and its conductance, defined as $$\min_{S \subset V} ~\... 0answers 487 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 ... 1answer 449 views ### What are the obstructions to extending L=SL to L=NL? Omer Reingold's proof that L=SL gives an algorithm for USTCON (In an Undirected graph with special vertices s and t, are they Connected?) using only logspace. The basic idea is to build an ... 2answers 687 views ### Are social networks typically good expanders? I am interested in the combinatorial properties of social networks as graphs. People have looked at things such as the distribution of the degrees, the clustering coefficient and the compressibility ... 1answer 439 views ### Existence of long induced paths in expander graphs Let's say that a graph family \mathcal{F} has long induced paths if there is a constant \epsilon > 0 such that every graph G in \mathcal{F} contains an induced path on |V(G)|^{\epsilon} ... 1answer 459 views ### Deterministic error reduction, state-of-the-art? Assume one has a randomized (BPP) algorithm A using r bits of randomness. Natural ways to amplify its probability of success to 1-\delta, for any chosen \delta>0, are Independent runs + ... 0answers 146 views ### expansion with respect to p-norms for p other than 2 Suppose I have an d-regular expander graph with n vertices, where the stochastic version of its adjacency matrix A (with entries 1/d and zero) has second eigenvalue \lambda. Let x \in {\... 1answer 966 views ### About the small set expansion conjecture Given a graph G=(V,E) and a \delta > 0 one wants to calculate h(G,\delta)=min_{\vert S\vert \leq \delta \vert V \vert } \phi(S). (\phi(S) = \frac{ E(S,\bar{S}) }{d min \{\vert S \vert , n - \... 0answers 192 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}... 0answers 49 views ### *Simple* explicit constructions of bounded-degree expanders of “largish” spectral gap I want to use for some work of mine bounded-degree (balanced bipartite) expanders with "decent" spectral gap. They need not be Ramanujan graphs. I'm ok with a degree that's a constant factor (ideally ... 0answers 176 views ### Pseudorandom object yielding shrinkage in \ell_p norm? Extractors have the following property: For a random variable X of min-entropy k and a seed Y, denote the output of an (k,\epsilon)-extractor by \mathrm{Ext}(X,Y). Then \|\mathrm{Ext}(X,Y)-... 0answers 176 views ### Lossless, constant-degree expanders that expand large sets It is known how to construct "lossless" unbalanced bipartite expanders with the following properties: the bipartite graph has n left vertices, m right vertices, left-degree D, and for all left-... 1answer 1k views ### d-regular bipartite expander graph I have seen that there exists d-left regular bipartite graphs. My question is do there exists d-regular bipartite expander graphs in which both the degree of the left and the right vertices is ... 0answers 184 views ### Expansion of the union of two expander graphs Suppose that G and H are both expander graphs on the same node set V with a second largest eigenvalue of \lambda_G resp. \lambda_H. Let G\cup H be the graph on V with the smallest set of ... 0answers 217 views ### Minimum weight expander Expander constructions given an expander which is a sub-graph of a complete graph. Sometimes we don't want to construct an arbitrary expander, want to find an expander inside another given graph. In a ... 2answers 496 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 ... 1answer 344 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 ... 1answer 252 views ### Self-intersecting walk in expander graphs Consider a random walk in an expander graph. How much time it typically takes to visit the same vertex twice. It seems to me that it should be something between \sqrt{n} to \sqrt{n}\log n. Is ... 1answer 576 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 ... 1answer 190 views ### About some possible optimality properties of Ramanujan graphs The Ramanujan graphs are optimal from the Alon-Bopanna point of view but.. Is there any sense in which one can call Ramanujan graphs to be the "optimal" spectral sparsifiers? (Reference : http://... 1answer 174 views ### Expander Graph from Hypergraph I came up with this problem while thinking about an optimizing compiler. Let H be a hypergraph. From this we construct a graph G_H as follows the vertices are the hyperedges of the hypergraph. ... 2answers 178 views ### reference request for construction of expanders I'm looking for a good exposition of the explicit constructive proof of the existence of expander graph families due to Reingold Vadhan and Wigderson. Arora/Barak has a chapter on it, but i find it ... 2answers 543 views ### Resources on Cryptographic Applications of Expander Graphs I want to read papers on cryptography like How to Recycle Random Bits or Security Preserving Ampliﬁcation of Hardness. They use random walks on expander graphs. I need a short introduction to the ... 1answer 207 views ### Can L=SL be shown with the replacement product instead of the zig-zag product? (This is a bit of follow-up to https://cstheory.stackexchange.com/posts/comments/93266 but is a distinct enough question I though it should be on its own.) In Omer Reingold's logspace USTCON ... 1answer 276 views ### Special properties of bipartite expanders It is well known that expanders, and often the special case of bipartite expanders, have found many uses in derandomization, coding, etc. However, I am curious if there are any special properties of ... 0answers 76 views ### Explicit Ramanujan graph families (Reference Request) I am looking for a reference for explicit families of d-regular Ramanujan graphs for fixed d. In particular, I am looking for a family of d-regular graphs such that the associated reversible ... 0answers 94 views ### Explicit combinatorial construction minimizing intersection of sets I'd like to know if anything is known about the following problem: Suppose we choose positive integer t to be constant. Let S = \{1,2,\dots,n\}, where n is sufficiently large. Consider a ... 0answers 190 views ### Expansion of constant-size sets My question refers to the expansion of constant size sets of an expander graph. Suppose we are given an expander graph with Cheeger constant \alpha. What can be said about the edge expansion of sets ... 1answer 288 views ### Existence of d-regular expander graph that can be represented as a bipartite graph It is easy to derive from the definition of expander graphs that a n-vertex expander graph G does not have a o(n)-vertex/edge separator. I was wondering if we can build a d-regular expander ... 0answers 179 views ### Building a “balanced” universal set A set of length n binary vectors \mathcal{U}=\{u_1,..,u_r\} is called (n,k)-universal if for all S\subset [n], |S|=k, |\mathcal{U}_{|S}|=2^k, i.e. for every subset of indices of size k, ... 0answers 105 views ### Delocalization of eigenvectors in Expanding Graphs Given an adjacency matrix A, can we say something about whether the eigenvectors corresponding to its highest (or second-highest) eigenvalues are de-localized ? By de-localization I mean that ... 1answer 242 views ### Combinatorial Expansion implies Algebraic Expansion Arora/Barak, in Chapter 21, Theorem 21.9, Page 428, proves: Algebraic Expansion implies Combinatorial Expansion If G is a (n, d, x) expander graph, then it is an (n, d, (1-x)/2) edge ... 0answers 62 views ### A random ensemble of sparse boundary operators The following question arises from the study of quantum error correction, and high-dimensional expanders: Is there an algorithm that for given numbers n>0,d≤n,r≤n samples uniformly a linear ... 1answer 388 views ### Second eigenvalue and the last eigenvalue Note : All eigenvalues that I would referring to below would of the adjacency matrix of the graph My question arises from having read about Expander Graphs from a few different sources. The most ... 1answer 214 views ### Expansion vs Sparsest cut let G=(V,E) and S\subsetneq V then expansion of set S is$$\alpha(S)=\frac{|E(S,\overline{S})|}{\min\{|S|,|\overline{S}|)\}} where $\bar{S}=V\setminus{S}$ and $E(S,\bar{S})$ are edges ...
Does Spectral Gap remains same after removal of some edges from a Expander Graph ? Suppose we take a d-regular graph and remove m edges from it. For a $d$-regular graph We have $\lambda_1 = d$ and \$\...