2
$\begingroup$

Let $\mathscr{C}$ be a graph consisting of an $n$-cycle, i.e., $n$ vertices arranged in a circle, with undirected (or two-way) blue edges between neighbors. Let us now draw two additional, green arrows from each vertex $n$ to two vertices $m$, $m+1$ that are not its neighbors. Denote by $\mathscr{C}'$ the new graph, including all edges, blue and green.

Must there exist a subset $S$ of the set of vertices $\{1,2,\dotsc,n\}$ such that $S$ is connected in $\mathscr{C}'$ and have large boundary in $\mathscr{C}$? By "large", I mean "having more than $\delta n$ elements for some fixed $\delta>0$".

(If not, can you give a counterexample? Can counterexamples be easily classified?)

EDIT: Aha. What if the green arrows are not arrows but undirected edges (or two-way arrows, if you wish)?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Let the arrows from $n,1,2,3$ go to $8,9$, all other arrows go to $1,2$. Then any $\mathscr{C}$-connected component $A$ of $S$ which does not intersect $\{n,1,\ldots,9\}$ is not reachable from $S\setminus A$ in $\mathscr{C}'$ either. So $S$ may have only $O(1)$ many connected components in $\mathscr{C}$, and the $\mathscr{C}$-boundary of $S$ has only $O(1)$ elements.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Right. See above - what happens if the green edges are undirected? $\endgroup$
    – H A Helfgott
    Commented Jan 16, 2021 at 15:07
  • $\begingroup$ Then there exists a spanning tree with many leafs. Take all non-leafs and each leaf with probability 1/2. $\endgroup$
    – Fedor Petrov
    Commented Jan 16, 2021 at 15:19
  • $\begingroup$ That gives us a set $S$ that is connected in $\mathscr{C}'$, but how do we know that its boundary in $\mathscr{C}$ is large? For all that we know, the edges connecting non-leafs to leafs may all be in $\mathscr{C}'$ but not in $\mathscr{C}$. $\endgroup$
    – H A Helfgott
    Commented Jan 16, 2021 at 15:49
  • 1
    $\begingroup$ Oh, I see. Each leaf $x$ has two neighbors in $\mathscr{C}$; if either is a non-leaf, you are done, and if they are both leaves, then the probability that $x$ be outside $S$ but one of its neighbors be in $S$ is $\geq 3/8$. Right? $\endgroup$
    – H A Helfgott
    Commented Jan 16, 2021 at 16:04
  • 1
    $\begingroup$ You mean every third leaf actually gets put in $S$. Yes, then the boundary is of size $\geq 2 \lfloor m/3\rfloor$ (or, more precisely, $\geq \lfloor m/3\rfloor + \lfloor (m+1)/3\rfloor$). $\endgroup$
    – H A Helfgott
    Commented Jan 17, 2021 at 10:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .