For any integer $m \in \mathbb{N}$, let $\mathbb{Z}_m$ denote the integers modulo $m$. For any two subset $A, B \subset \mathbb{Z}_m$, and $x \in \mathbb{Z}_m$, denote $s(A,B,x) := \vert \{(a,b) \mid a \in A, b \in B, a+b = x \} \vert$. For any 2-partition $A,B$ of $\mathbb{Z}_m$, denote $c(A, B) := \max_{x \in \mathbb{Z}_m} \vert s(A,A,x) + s(B,B,x) - 2 \times s(A,B,x) \vert$ Show that for every odd $m$, there exists a 2-partition of $\mathbb{Z}_m, (A,B)$ such that $c(A,B) = \mathcal{O} (\sqrt{m \log m})$
I tried doing the following:
Fix a $x \in \mathbb{Z}_m$ and consider the graph $G = (\mathbb{Z}_m, E)$, where $ab \in E$ if $a+b = x$. This graph would be a matching on $\mathbb{Z_m} \setminus \{u\}$ where $u$ is some element of $\mathbb{Z}_m$ and a loop on $u$. Hence, our question basically becomes to find vertex cut of $G$ such that $C(A,\mathbb{Z}_m\setminus A) = \mathcal{O}(\sqrt{m\log m})$
I tried setting up a randomly sampled set $S$ such that $\Pr(x \in S) = p$ ( we will fix $p$ later ) and tried finding value of $c(S, \mathbb{Z}_M \setminus S)$ but I was not getting an appropriate result.
Any hints or solution would be appreciated.
I think you make a very good start, and are nearly there. First some notation: for any $x$, let me define $\mathcal{E}_x$ as the edges (interpreted as elements of $\binom{[1:m]}{1} \cup \binom{[1:m]}{2}$) in the matching w.r.t. $x$. Define $U_e(A) = \begin{cases} 1 & e \subset A \textrm{ or } e \subset A^c \\ -1 & \textrm{ o.w.}\end{cases},$ and $\Delta_x(A) = \sum_{e \in \mathcal{E}_x : |e| > 1} \frac{3U_e - 1}{2}$. Note here that I've not summed up over the potential self-loop in $\mathcal{E}_x$: at the end of the day there is only one possible loop, so this will only change our estimates by $O(1)$, so we need not worry about this. With this in mind, $\Delta_x$ approximates $s(A,A,x) + s(A^c,A^c,x) - 2s(A,A^c,x)$ up to an error of $\pm 2$.
Now, still viewing everything from the pespective of a single $x$, if we choose $A$ as in the question, then notice that each of the $U_e$s in the sum for $\Delta_x$ are independent and bounded random variables. This is because $U_e$ only depends on the assignment of the vertices in $e$, but the sets $e \in \mathcal{E}_x$ are all disjoint (since they form a matching), so the assignment of vertices in $e$ doesn't affect the assignment of vertices in some $e' \neq e$. So we can apply Hoeffding's inequality to find that $$ P(|\Delta_x(A) - \mathbb{E}[\Delta_x(A)]| > t) \le \exp(- C t^2/m)$$ for some constant $C$. Further, note that we can choose some $p$ so that $\forall x, \mathbb{E}[\Delta_x(A)] = 0,$ since $$ \mathbb{E}[3U_e(A) - 1]/2 = p^2 + (1-p)^2 - 4p(1-p) = 0$$ has a solution in $(0,1)$ (show this). Let us assume that we have picked $p$ accordingly. Note that this makes $\mathbb{E}[\Delta_x(A)] = 0$ for every $x$ simultaneously (this is the key point).
Now, if we pick a partition randomly according to the above bias, we have $$ \forall x, P(|\Delta_x(A)| > t) \le \exp(-Ct^2/m). $$ But there are only $m$ possible $x$s, so by a union bound, $$ P(\exists x: |\Delta_x(A)| > t) \le m \exp(-C t^2/m).$$ This upper bound is smaller than $1$ so long as $\log m - Ct^2/m < 0 \iff t > \sqrt{(m \log m)/C},$ showing that there exists some partition $A_*$ such that simultaneously for all $x$, $|\Delta_x(A_*)| = O(\sqrt{m \log m})$. Of course, $c(A_*,A_*^c) \le \max_x |\Delta_x(A)| + O(1),$ so we are done.