3
$\begingroup$

Let $\Gamma, \Xi$ be two graphs with the same set of vertices $V$ with $n$ elements. Assume $\Gamma$ is connected. Write $\Gamma\cup \Xi$ (or $\Gamma\cap \Xi$) for the graph whose set of edges is the union (or, correspondingly, the intersection) of the sets of edges of $\Gamma$ and $\Xi$. Given $S\subset V$, write $\partial_\Gamma S$ for the set of all $v\in V\setminus S$ such that there is a $w\in S$ for which $\{v,w\}$ is an edge in $\Gamma$.

Under what conditions is it the case that there must be a subset $S\subset V$ such that (a) $S$ is connected in $\Gamma \cup \Xi$ and (b) $\partial_\Gamma S\setminus (\partial_{\Gamma\cap \Xi} S)$ is large? ("Large" here may mean "having at least $\epsilon n$ elements".)


The "conditions" I'm looking for here would be local. For instance, for $\Xi$ an empty graph, it is enough to require the degree of every vertex in $\Gamma$ to be $\geq 3$. (See Existence of connected component with large boundary?)

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.