Graphs that have many adjacent vertices for each subset of vertices I was thinking lately about graphs that have the following property :
Let $G = (V, E) $ be an undirected simple graph, and define for any subset $V'$, the neighborhood $N(V')$ as all vertices that are adjacent to some vértex in V', and are NOT themselves elements of $V'$.
If a subset $V'$ contains less vertices than $N(V') $, we say that V' has a large neighborhood. If every subset V' that contains less than half of all vertices has a large neighborhood, we say that $G$ is intertwined.
What properties would these type of intertwined graphs have?  Is it possible to construct large intertwined graphs while being sparse with the amount of edges?
More specifically, can we create an arbitrarily large intertwined graph that has maximal vertex degree 4?
I also would conjecture that if an intertwined graph has more than $n^2$ vertices, than it has $K_n$ as a minor.
 A: There's many definitions of expander graphs, so let me use the one from Alon and Spencer's Probabilistic Method:

A graph $G = (V, E)$ is called an $(n, d, c)$-expander if it has $n$ vertices, the maximum degree of a vertex is $d$, and, for every set of vertices $W \subset V$ of cardinality $|W| \le n/2$, the inequality $|N(W)| \ge c|W|$ holds, where $N(W)$ denotes the set of all vertices in $V \setminus W$ adjacent to some vertex in $W$.

By the definition in the question, $W$ "has a large neighborhood" if $|N(W)| \ge |W|$, so we are asking for $c=1$. So a graph is "intertwined" if it is an $(n,d,1)$-expander. (Note that $c=1$ is the very best expansion factor we can hope for; if $|W|$ is close to $n/2$, then $|N(W)|$ cannot be larger than $|V\setminus W|$, so it cannot be much larger than $|W|$.) There is one minor change, which is that Alon and Spencer's definition allows $|W| \le n/2$, and we do not want that, but it will not matter significantly.
There is a lot of interest in constructing $(n,d,c)$-expanders where $d$ is small, but in the case of $c=1$, we are doomed to have $d$ linear in $n$. For example, suppose $n$ is odd; then:

*

*Take two arbitrary vertices $x,y$ and let $U$ be the set of all vertices that are not $x$ or $y$ or adjacent to either one of them. Note that $|U| \ge n - 2 - 2d$.

*If $d \le (n-3)/4$, then $|U| \ge (n-1)/2$, so we can let $W$ be a subset of $U$ of size exactly $(n-1)/2$.

*Now, $|N(W)| \le n - |W| - 2$, because $N(W)$ cannot contain any vertex of $W$, and also by construction $N(W)$ cannot contain $x$ or $y$. So $|N(W)| \le (n-3)/2$, and in particular $|N(W)| < |W|$. Therefore the graph cannot be intertwined.

So we need $d$ to be at least around $n/4$ for the graph to be an $(n,d,1)$-expander. (That's for odd $n$. For even $n$, we can have $W$ equal to either $n/2$ or $n/2-1$, depending on definition, and so $d$ will need to be either around $n/2$ or $n/6$ by a similar argument. But still linear!)
If instead of $c=1$ we just wanted some $c$ that remains constant as $n \to \infty$, then it is possible to have a very small $d$ - even $d=3$. (In fact, randomly chosen $3$-regular graphs are $(n,3,c)$-expanders for some constant $c>0$ with high probability.)
