A problem about symmetric relations on finite sets.

Solution 1:

The following algorithm is guaranteed to produce such a partition.

Let $G\subseteq X$ be a clique in $X$. We assume that $G$ is maximal (assumption $1$) and that $|G|$ is even (assumption $2$). Starting with $Y=X$ and $Z=\emptyset$, we will repeatedly select a vertex in $G \cap Y$ and move it from $Y$ to $Z$. For each vertex removed from $Y$, $s(Y)$ will either decrease by $1$ (if the vertex belongs to $Y$'s unique maximal clique) or remain the same. On the other hand, since $Z\subseteq G$ at each step, $Z$ is always a complete graph, and $s(Z)=|Z|$. The selection criterion is the following: select a vertex whose removal will leave $s(Y)$ unchanged, unless there are none. This process will terminate with $Y=X-G$ and $Z=G$. Therefore, the discrepancy $s(Y)-s(Z)$ will decrease monotonically from $s(X) - s(\emptyset)\ge 0$ to $s(X - G)-s(G)\le 0$, decreasing by either $1$ or $2$ per vertex moved. Moreover, it will only decrease by $2$ (i.e., skip a value) if there is no member of $G\cap Y$ that, when moved, will decrease it by only $1$. So $s(Y)-s(Z)$ will skip a value only if each member of $G\cap Y$ belongs to $Y$'s unique maximal clique. Carry out the procedure until $s(Y)=s(Z)$ (in which case we are done) or until $s(Y)=s(Z)+1$ and the next vertex to be moved will decrease $s(Y)-s(Z)$ by $2$.

At this point, $Y$ has a unique maximal clique (call it $H$) that contains $G \cap Y$. Removing any element of $H$ from $Y$ will decrease $s(Y)$ by $1$. We already know that each element of $G\cap Y$ is adjacent to all elements of $Z$, and so adding any of these to $Z$ would increase $s(Z)$ by $1$. What about the remaining elements of $H$, namely, $H-(G\cap Y)=H\cap G^{c}$? This set cannot be empty. If it were, then we would have $s(Y)=|H|=|H\cap G|=|G\cap Y|$ and $s(Z)=|Z|=|G\cap Y^{c}|$, hence $s(Y)+s(Z)=|G|$, which must be odd because $s(Y)=s(Z)+1$; but this contradicts assumption $2$ (that $|G|$ is even). Now, if all members of $H\cap G^{c}$ are also adjacent to all members of $Z$, then $H \cup Z$ is itself a clique in $X$ with size $|H\cup Z|=|H\cap G^{c}|+|G|>|G|$, contradicting assumption $1$ (that $G$ is maximal).

We conclude that there is at least one element $x \in H\cap G^{c}$ that is not adjacent to all members of $Z$. Therefore, $$s(Z \cup \{x\})=s(Z)=s(Y)-1=s(Y-\{x\}),$$ and $\{Y-\{x\},Z\cup\{x\}\}$ is the desired partition of $X$.

Solution 2:

I don't have a solution, but an example that the splitting of the graph might not be so easy:

Consider the graph $G$ resulting from the complete graph on the vertex set $V = \{1,2,3,4,5,6\}$ by removing the edges $\{4,5\}$, $\{4,6\}$ and $\{5,6\}$. The maximum clique size of $G$ is $4$ (The maximum cliques are $\{1,2,3,4\}$, $\{1,2,3,5\}$ and $\{1,2,3,6\}$). I have checked that the only partitions of $V$ resulting into two graphs of identical maximum clique size is $\{\{1,4,5,6\},\{2,3\}\}$, $\{\{2,4,5,6\},\{1,3\}\}$ and $\{\{3,4,5,6\},\{1,2\}\}$. In particular, there is no possible partition into two sets of size $3$.