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 $...
- 2,416
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 ...
- 96
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 (...
- 16.8k
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 ...
- 19
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 ...
- 16.8k
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,...
- 117k
Top 50 recent answers are included