## New answers tagged expander-graphs

4
votes

Accepted

### Existence of connected set with large edge boundary

If I am not mistaken, then the following recursive construction disproves statement A:
Let $G_1$ consist of a $K_8$ and an additional vertex $r_1$ connected to half of the vertices of this $K_8$
For $...

4
votes

### Existence of connected set with large edge boundary

I think I have a counter-example to Statement B:
Start with a $K_r$ and connect every vertex to one vertex of a new $K_4$. This is the graph $\Gamma=(V,E)$, which has $5r$ vertices. Any set $S\subset ...

0
votes

### Existence of connected set with large edge boundary

Proof 1 of Statement B for regular graphs. Let $\Gamma$ be a regular graph of degree $d$. As in F. Petrov's answer to Existence of connected component with large boundary? : by Kleitman and West (...

0
votes

### Existence of connected set with large edge boundary

I assume by degree in V-S you mean the degree in the full graph (not restricted to V-S).
I begin partitioning $V=A \cup B$ of basically the same size (off by at most 1).
Now by your condition the sum ...

1
vote

### Existence of connected set with large edge boundary

Reduction of Statement A to Statement B. Let $S$ be as in statement B. Let, at first, $S'=S$. Do the following repeatedly until you cannot: include in $S'$ an element of $V\setminus S'$ having at ...

1
vote

### Arbitrary-dimensional expanders?

For the second question, there is the iterated Cauchy-Schwarz method, where you Cauchy-Schwarz to eliminate one or more of the $f_i$ variables and then repeat this process until all the $f_i$ are gone,...

Top 50 recent answers are included

#### Related Tags

expander-graphs × 54graph-theory × 33

spectral-graph-theory × 19

co.combinatorics × 18

gr.group-theory × 8

reference-request × 6

nt.number-theory × 5

pr.probability × 4

finite-groups × 4

mg.metric-geometry × 3

finite-fields × 3

extremal-graph-theory × 3

fa.functional-analysis × 2

rt.representation-theory × 2

algebraic-number-theory × 2

computational-complexity × 2

sp.spectral-theory × 2

geometric-group-theory × 2

eigenvalues × 2

graph-colorings × 2

random-walks × 2

random-graphs × 2

spanning-tree × 2

ag.algebraic-geometry × 1

oa.operator-algebras × 1