<p>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 of size, say 100?</p>

<p>Is it true, that the relative expansion of a set, w.r.t. the set size always has a
decaying profile - so that constant size sets expand much more rapidly than the overall graph expansion?</p>

<p>While there is nothing to stop constant-size sets from having just poor overall expansion value (equal to the minimal expansion over all sets) by definition, is it possible to show such a property?</p>

CC BY-SA 3.0
2011-08-17T06:46:41.487Z
Hi Lior. I merged your new account with the previous one. I would suggest that you register your account to avoid creating new ones and to have ability to edit your posts later.
Kaveh
CC BY-SA 3.0
2011-08-17T15:18:56.567Z
Can you clarify the question? If you just follow the definitions, there is nothing to prevent an expander graph with expansion $\alpha$ to have a constant-sized set with expansion $\alpha$. Maybe your question is about random graphs, or existing explicit families?
Mahdi Cheraghchi
CC BY-SA 3.0
2011-08-18T07:08:48.950Z
Thank you MCH.  Modified question following your comment.
Lior Eldar
<graph-theory><co.combinatorics><expanders>
Expansion of constant-size sets
Lior Eldar
# Expansion of constant-size sets

(Asked by: username_0 on 2011-08-17)

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 of size, say 100?

Is it true, that the relative expansion of a set, w.r.t. the set size always has a
decaying profile - so that constant size sets expand much more rapidly than the overall graph expansion?

While there is nothing to stop constant-size sets from having just poor overall expansion value (equal to the minimal expansion over all sets) by definition, is it possible to show such a property?

**Tags:** graph-theory, co.combinatorics, expanders

> **Comments:**
> **username_1**: Hi Lior. I merged your new account with the previous one. I would suggest that you register your account to avoid creating new ones and to have ability to edit your posts later.  
> **username_2**: Can you clarify the question? If you just follow the definitions, there is nothing to prevent an expander graph with expansion $\alpha$ to have a constant-sized set with expansion $\alpha$. Maybe your question is about random graphs, or existing explicit families?  
> **username_0**: Thank you MCH.  Modified question following your comment.  

---

## 0 answers

