A collection $\mathcal{A}\subseteq \mathcal{P}(X)$ is $k$-large in $X$ if for every $k$-partition of $X$ namely $X_1,\cdots,X_k$, there exists an $i\leq k$ such that $X_i\in \mathcal{A}$; $\mathcal{A}$ is upward closed if for every $X\subseteq Y$, $X\in \mathcal{A}$ implies $Y\in \mathcal{A}$.
Fix a $0<\delta<1/2$, $k\in\mathbb{N}$. Let $N$ be very large, $\mathcal{A}\subseteq\mathcal{P}(\{1,\cdots,N\})$ is $k$-large in $\{1,\cdots,N\}$ and upward closed. Let $Z$ be a uniformly random $N/k$-element subset of $\{1,\cdots,N\}$.
Question: Is it true that there exists a $\delta N$-element subset $Z'$ of $\{1,\cdots,N\}$ such that with high probability (as $N\rightarrow\infty$): $Z\cup Z'\in\mathcal{A}$.
Theorem 3 of [KG1975] gives the following: for every $\mathcal{A}'\subseteq 2^N$ with $|\mathcal{A}'|/2^N=c>0$, let $\rho\in 2^N$ be uniformly random, then $d_H(\rho,\mathcal{A}) = O_p(\sqrt{N})$. Where $d_H$ denote the Hamming distance. This implies a weaker "answer" of above question: with high probability, there exists a $Z'$ (depending on $Z$) such that $Z\cup Z'\in \mathcal{A}\wedge |Z'|<\delta N$.
I wonder if the following (which implies a positive answer to above question) holds:
For every $\mathcal{A}'\subseteq 2^N$ with $|\mathcal{A}'|/2^N\geq c>0$, every $\delta>0$, there exists a set $Z'\subseteq N$ with $|Z'|<\delta N$ such that let $\rho\in 2^N$ be uniformly random, then with hight probability: there exists a $\sigma\in \mathcal{A}'$ such that $\rho$ agree with $\sigma$ on $N\setminus Z'$.
