This is question from a chapter on the Lovasz Local Lemma in the probabisitic method. I am asked to show that there is some constant $c>0$ such that for all $k$, there is a set $S$ of not less than $ck\ln k$ integers that satisfy: for every $k$ coloring of the integers, there is some $x$ such that the set $x+S$ does not contain integers of all $k$ colors.
So I know we have to use the Lovasz Local Lemma, probably the symmetric version is not strong enough so we will have to use the general one. There was a hint I saw somewhere that said to let $S$ be a set of size $ck \ln k$ randomly selected from $[2ck\ln k]$. By the pigeonhole principle, every coloring has a monochromatic set of size not more than $4c\ln k$ integers in the first $4ck\ln k$ integers. So let $U$ be a set of size $4 c \ln k$ randomly selected from the first $ 4ck \ln k$ integers. We want to bound the probability
\begin{equation}
\mathbb{P}\left( x+S \in U, \ \forall \ x \in [2ck\ln k] \right).
\end{equation}
The conclusion I am hoping to get would then be something like
\begin{equation}
\mathbb{P}\left( \bigwedge_{U, |U| = 4c\ln k} \overline{ \bigwedge\limits_{x\in [4ck\ln k] }x+S \in U } \right) > 0.
\end{equation}
To use the LLL, I want to find some $x_U$ for all $U$ such that
\begin{equation}
\mathbb{P} \left( \bigwedge_{x\in [4ck\ln k]} x+S \in U \right) < x_U \prod_{U'\sim U} (1-x_{U'})
\end{equation}
where $U\sim U'$ denotes dependency of the above events.
However, I am not sure how to get a nice bound no the above probability. Also, I think the dependency would be all over the place for this construction right? For some set $U$, there are very many other sets $U$ that intersect with it.
If anyone can shed some light I would be thankful!
Best Answer
Though this problem is in the Lovász Local Lemma chapter, this particular result doesn't use it; it's meant to be an asymptotically tight lower bound to the result proven in Theorem 5.2.2, which does crucially use it. The proof is a bit of a handful, so do let me know if something seems wrong/isn't clear!
To get the result, for now, let $c$ be undetermined, and randomly select a subset $S$ by independently including each element in $[2ck \ln k]$ with probability $1/2$ (this is slightly different than the hint, but avoids the slight negative dependencies between which elements are included in $S$). Now fix any subset $U$ of size at most $4c\ln k$. We will first show that with extremely high probability, $U$ does not intersect every translate of $S$. For any translate $x+S$, where $x$ is an arbitrary element of $[2ck\ln k]$, it is easy to see that $$ \Pr(U\cap x+S= \emptyset)\geq \bigg(\frac{1}{2}\bigg)^{4c\ln k}=\frac{1}{k^{4c\ln 2}}\geq \frac{1}{k^{2.8c}}. $$
So the probability $U$ intersects an arbitrary translate is fairly close to $1$, but bounded away from $1$. To drive the probability it intersects all translates of $U$ down to $0$, notice that $$ U\cap x+S\neq \emptyset \iff U-x\cap S\neq 0, $$ and because of how $S$ was generated, if $x,x'$ are such that $U-x\cap U-x'=\emptyset$, then the events that $S\cap U-x=\emptyset$ and $S\cap U-x'=\emptyset$ are independent. Obviously, this will not hold for many pairs of $x,x'$, but we can find a fairly large family where these translates are mutually disjoint. Indeed, we claim there is such a family of such $x$ of size $\geq \frac{k}{8c\ln k}$. In fact, any maximal family of such $x$ will have at least this cardinality.
To get this, take any maximal family $X\subseteq [2ck\ln k]$ of such $x$ i.e. for all $x, x'\in X$ distinct, $$ U-x\cap U-x'=\emptyset, $$ and for any other $x''\in [2ck\ln k]\setminus X$, there exists some $x\in X$ such that $$ U-x''\cap U-x\neq \emptyset. $$ Suppose it has smaller size than what we claimed. By pairwise disjointness, we must have $$ \vert \cup_{x\in X} U-x\vert=\vert U\vert\vert X\vert< k/2. $$ Notice that every element in this union can belong to at most $\vert U\vert$ translates of $U$. It follows that $\cup_{x\in X} U-x$ can only intersect strictly less than $(k/2)\vert U\vert=2ck\ln k$ translates of $U$, giving a contradiction. We conclude that any maximal family $X\subseteq [2ck\ln k]$ such that the $U-x$ for $x\in X$ are all disjoint has size $\geq \frac{k}{8c\ln k}$.
For the fixed $U$, take such a maximal family $X$. Now, we can finally continue to say that \begin{align} \Pr(U\cap x+S\neq \emptyset, \forall x\in [2ck\ln k])&\leq \Pr(U\cap x+S\neq \emptyset, \forall x\in X)\\ &\leq \bigg(1-\frac{1}{k^{2.8c}}\bigg)^{k/8c\ln k}\\ &\leq \exp\bigg(\frac{-k^{1-2.8c}}{8c\ln k}\bigg), \end{align} where we use independence, the estimate above, and the usual $1-x\leq e^{-x}$ estimate.
To use a union bound for all subsets of $[4ck\ln k]$ of size at most $4c\ln k$, we estimate $$ \sum_{i=0}^{4c\ln k} {4ck\ln k\choose i}\leq 2^{H(1/k)4ck\ln k}, $$ using a standard upper bound on partial sums of binomial coefficients, where $H(x)$ is the binary entropy function. Observe that \begin{align} 2^{H(1/k)4ck\ln k}&=2^{((1/k)\log_2(k)-(1-1/k)\log_2(1-1/k))4ck\ln k}\\ &\leq 2^{(\log_2(k)+1)4c\ln k}\\ &\leq \exp\bigg(c'\ln^2 k\bigg), \end{align} where $c'$ is some other constant that is at most some absolute scalar multiple of $c$ after changing bases of logs. We also use the fact $-(k-1)\log_2(1-1/k)\leq 1$ for all $k\geq 2$. The union bound then gives \begin{align} \Pr\bigg(\exists U\subseteq [4ck\ln k]: \vert U\vert\leq 4c\ln k,\leq U\cap S+x\quad\forall x\in [2ck\ln k]\bigg)&\leq \exp\bigg(c'\ln^2 k\bigg)\exp\bigg(-k^{1-2.8c}/8c\ln k\bigg)\\ &<<1, \end{align} where we can make $c$ sufficiently small so that this holds for all $k$ with very high probability. The last thing to note is that by usual Chernoff bounds, with very high probability, $\vert S\vert\geq f(c)k\ln k$ for all $k$, where $f<1$ is just some function of $c$, so with high probability $S$ will be large and satisfy the event above. This shows the existence of a large subset $S$ such that for any $k$-coloring of the integers, some translate of $S$ will avoid the least represented color among the first $[4ck\ln k]$ integers.