New answers tagged

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 $...
user avatar
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 ...
user avatar
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 (...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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,...
user avatar
  • 117k

Top 50 recent answers are included