Here is the problem:
Let $\mathbb{Z_n}$ be the set of integers mod $n$, and for a subset $A \subset \mathbb{Z_n}$ and for $x \in \mathbb{Z_n}$, let $A+x$ denote the set {${a+x | a \in A}$}. Given two subsets $A,B \subset \mathbb{Z_n}$ prove there exists $x$ such that $|(A+x)\cap B| \geq |A||B|/n$.
Here is my attempt:
First note that if either $A$ or $B$ are empty, then the inequality is satisfied. Therefore, it is safe to assume that both $A$ and $B$ are non-empty. If $A$,$B$ are disjoint, then we can always find an $x$ such that $(A-x) \cap B \neq \emptyset$. (Take some $a \in A$ and some $b \in B$ and let $x = b -a$ mod $n$, this ensures the sets are not disjoint because $a+x$ is in both $(A+x)$ and $B$.)
We can now define the following bipartite graph: $G = (X,Y,E)$ where $X = (A+x) \cap B$ and $Y = (A+x)\times B$ ($\times$ denotes the cartesian product). We can write $y= (y_1,y_2)$ $\forall y \in Y$ where $y_1 \in A+x$ and $y_2 \in B$. Join $x$ and $y$ iff $x=y_2$. Each vertex in $Y$ has degree 1 since each $x$ only appears once in $X$, and each vertex in $X$ has degree $=|A+x| \leq n$. This implies $|E| = |Y| = |(A+x) \times B| =|A+x||B|=|A||B|$. On the other hand, $|E| \leq n|(A+x) \cap B|$ $\implies $ $|A||B|/n \leq |(A+x) \cap B|$
Reasons I don't think my answer is correct:
(a) Not enough emphasis on the exsistance of $x$, the question could be more simply phrased if $A$,$B$ are non-disjoint subsets....
(b) I'd be surprised if the solution was this simple.
I'm new to this type of double counting argument, i'd appreciate if someone could point me in the right direction.
The question comes from Topics in Combinatorics by W.T Gowers, problem sheet 1, question 1 linked here: https://drive.google.com/file/d/1OFgVrk1n2zxSF5tcfSe5Fxrva0YVhXEl/view
The full course can be found here: https://www.youtube.com/watch?v=WcLrT263p2w
I don't think the graph that you are using contains any information about what happens with different values of $x$. I propose the following solution using a bipartite graph (complete bipartite graph in this case):
Consider the graph where the vertices on one side are $A$ and the vertices on the other side are $B$, connect two vertices $a$ and $b$ with an edge of color $x$ if $a+x=b$. When you do this each vertex in $A$ is connected to each vertex in $B$, so there is $|A||B|$ edges. The cardinality of $|(A+x) \cap B|$ is equal to the number of edges of color $x$, since there are $n$ colors there must be a color $x$ with at least $|A||B|/n$ edges.