We study a combinatorial property of the Parity language (the set of binary words with an even number of 1s). Let $n$ be a word size, $\textit{Parity}_n$ be the subset of Parity of words of length $n$, $\overline{\textit{Parity}}_n$ be the subset of the complement of Parity of words of length $n$.
For two subset $A$ and $B$, we say that $B$ has a limit in $A$ if there is a word $u\in A$ such that for every position $i$ there exists a word $v$ in $B$ that matches $u$ on that position (ie. $u_i = v_i$).
Let $p$ be any polynomial. Show: $$\exists A \subseteq \textit{Parity}_n, \ \forall A'\subseteq A, \ |A'|\geq \frac{|A|}{p(n)}, \exists B \subseteq \overline{\textit{Parity}}_n,$$ $$\forall B' \subseteq B, \ |B'|\geq \frac{|B|}{p(n)},\ B' \textit{ has a limit in } A'$$
Note that the set $B$ can be chosen accordingly to the choice of $A'$.
This property is useful while studying the expressive power of depth-3 boolean circuits in $\textit{AC}^0$. A similar property has been proved for depth-3 circuits with bounded top fan-in in a recent LICS paper, and can be traced back to Hastad, Jukna and Pudlak. Here, the goal is to extend this combinatorial statement for a bigger class of languages, and for a more general notion of limit to describe precisely the regular languages definable thanks to depth-4 circuits with bounded top fan-in.