Say that $S\subset \mathbb Z\_n$ is *stabbed* by $X\subset \mathbb Z\_n$ if for every $t$ we have $(S+t)\cap X\ne \emptyset$.



> 
> Is there for every $|S|=4$ an $|X|<n/2$ that stabs it?
> 
> 
> 


My motivation comes from [here](https://dustingmixon.wordpress.com/2019/07/08/polymath16-thirteenth-thread-bumping-the-deadline/#comment-23883), where we would could improve the number of added edges.
In fact, instead of $\mathbb Z\_n$ we could also use the dihedral group $D\_n$ (where we pick some $t$ from $D\_n$).
*Update*: This became a [separate question](https://mathoverflow.net/questions/337227/is-it-possible-to-stab-every-permutation-of-any-four-element-subset-of-d-n-wit?).


I checked by hand, and it seems that there are no counterexamples for $n \le 8$, but I think that there should be for large enough $n$. (*Update*: After Seva's solution for $m\ge 5$, I'm not so confident about this anymore.)
More generally, instead of *four*, one can ask the following.



> 
> Is there an arbitrarily large $S\subset \mathbb Z\_n$ that cannot be stabbed by any $|X|<n/2$?
> 
> 
> 



Is it possible to stab (every rotation of) any four element subset of $\mathbb Z_n$ with less than $n/2$ elements?
I think this is true for any group $G$, and if $|G|$ is odd then $|S| \geq 3$ suffices. I will use multiplicative notation instead of additive notation since I do not assume that $G$ is commutative.


**Theorem.** If $G$ is a finite group and $S \subseteq G$ with $|S| \geq 4$ then there is a set $X \subseteq G$ such that $|X|<|G|/2$ and $gS \cap X \neq \varnothing$ for every $g \in G$. If $|G|$ is odd then $|S| \geq 3$ suffices.


Translating $S$ if necessary, we may assume that $1 \in S$. Let $H$ be the subgroup generated by $S$. We will first find a stabbing set for $S$ in $H$: a set $X \subseteq H$ with $|X| < |H|/2$ such that $hS \cap X \neq \varnothing$ for every $h \in H$. Then $g\_1X \cup \cdots \cup g\_kX$ will be as required where $g\_1,\ldots,g\_k$ are representatives for the left cosets of $H$ in $G$. (If $g \in G$ then $g = g\_ih$ for some $i \in \{1,\ldots,k\}$ and some $h \in H$. If $x \in hS \cap X$ then $g\_ix \in g\_ihS \cap g\_iX = gS \cap g\_iX$.)


Let $S\_0 = S-\{1\}$ and define the directed graph $D$ with vertex set $H$ and directed edges $(hs,h)$ for $s \in S\_0$. This is the Cayley digraph for the generating set $S\_0^{-1}$. Note that this is a strongly connected directed graph. In fact, $D$ is always strongly $\lceil |S|/2 \rceil$-connected by a result of Hamidoune:


*Hamidoune, Yahya Ould*, [**Quelques problèmes de connexité dans les graphes orientés**](http://dx.doi.org/10.1016/0095-8956(81)90085-X), J. Comb. Theory, Ser. B 30, 1-10 (1981). [ZBL0475.05039](https://zbmath.org/?q=an:0475.05039).


In the case of interest where $|S|\geq4$, this only ensures that $D$ is strongly $2$-connected. However, it turns out that $D$ is $3$-connected except in one scenario, which can be dealt with separately.
Let's first deal with the case where $D$ is strongly $3$-connected.


**Lemma.** There is a directed spanning tree $T$ for $D$ where in the root $1$ is connected to two leaves of $T$.


Proof: Pick distinct $s,t \in S\_0$. Remove $s^{-1},t^{-1}$ from $D$ and form a directed spanning tree $T\_0$ rooted at $1$ for the rest. (You can find one of these greedily since $D-\{s^{-1},t^{-1}\}$ is strongly connected.) Then add the edges $(1,s^{-1})$ and $(1,t^{-1})$ to $T\_0$ to obtain the desired tree $T$. $\square$


Paint elements of $H$ red and blue starting from the leaves of $T$ as follows. Once all the immediate successors of $h$ in $T$ have been painted red or blue, paint $h$ blue if at least one successor of $h$ has been painted red, otherwise paint $h$ red. So the leaves of $T$ are all red, their immediate predecessors are all blue, then the nodes whose immediate successors are either leaves or immediate predecessors of leaves are determined, and so on all the way down to the root $1$ of $T$.


Let $X$ be the set of blue nodes and let $Y$ be the set of red nodes. Note that $1 \in X$.


*Claim 1.* $X$ is stabbing for $S$.


Proof: Given $h \in H$. If $h \in X$ then $h \in hS \cap X$. If $h \in Y$ then $h$ has an immediate predecessor in $T$, which is of the form $hs$ for some $s \in S\_0$ and must be painted blue. Therefore $hs \in hS \cap X$.


*Claim 2.* $|X| < |H|/2$.


Proof: The map which sends every red element to its immediate predecessor is a surjection from $Y$ onto $X$. This is not a bijection because $1$ is a blue node attached to two leaves, which are both red. Therefore $|X|<|Y|$ and since $H = X \cup Y$, $X \cap Y = \varnothing$ it follows that $|X| < |H|/2$.


If $D$ is merely known to be strongly $2$-connected, which follows from $|S| \geq 3$, then we can find a spanning tree $T$ for $D$ where the root $1$ is connected to at least one leaf. This ensures that $1$ is colored blue to make Claim 1 work. The surjection from Claim 2 could be a bijection but we still have that $|X|\leq|Y|$. If $G$ and therefore $H$ have odd order, we can't have $|X|=|Y|$ and Claim 2 still holds. So $|S|\geq3$ suffices assuming that $|G|$ is odd.


Assuming $|S|=4$, the one scenario where $D$ is not strongly $3$-connected is when $S = \{1,a,b,ba\}$ and $a^2 = 1$ (up to translation). This follows from Hamidoune's atom theory, which says that the connectivity of the Cayley graph $D$ of $S\_0^{-1}$ in $H$ can be measured by an atom $A$ which is a subgroup of $H$ generated by $A \cap S\_0^{-1}$ such that $AS\_0^{-1} \setminus A$ is a minimal cut set of $D$. 


*Hamidoune, Yahya Ould*, [**On the connectivity of Cayley digraphs**](http://dx.doi.org/10.1016/S0195-6698(84)80034-7), Eur. J. Comb. 5, 309-312 (1984). [ZBL0561.05028](https://zbmath.org/?q=an:0561.05028).


Specializing to the case at hand where $|S|=4$ and $D$ is strongly $2$-connected but not strongly $3$-connected, we see that the only possibilitiy is that $S\_0 = \{a,b,ab\}$ where $a^2 = 1$ and $A = \{1,a\}$.


Let $X \subseteq H$ select one element from each left coset of the subgroup $\{1,a\}$ in $H$, except for the coset $\{b^{-1},b^{-1}a\}$. Without loss of generality $1 \in X$. Thus $|X| = |H|/2 - 1$. To see that this works, given $h$ in $H$ there are two cases:


* If $h \in \{b^{-1},b^{-1}a\}$ then $1 = b^{-1}b = b^{-1}aab \in hS \cap X$.
* Otherwise, $X$ contains one of $hA = \{h,ha\}$. Since $hA \subseteq hS$ we see that $hS \cap X \neq \varnothing$.


