A problem about symmetric relations on finite sets.

Question

We have these assumptions:

1. $X$ is a finite set.
2. $\sim$ is an irreflexive symmetric relation on $X$.
3. for any subset $Y\subseteq X$ we define $$\mathcal{Cl}(Y)=\{A\subseteq Y\mid(\forall a,b\in A:a\ne b)(a\sim b) \}$$ $$s(Y)=\max\{|A|: A \in \mathcal{Cl}(Y)\}$$
4. $s(X)$ is even.

Prove there exists a 2-element partition $\{Y,Z\}$ for $X$ such that $$s(Y)=s(Z)$$

---

In fact the relation is equivalent to a graph. A maximal clique with largest size has an even number of vertices. Now we want to divide the graph into two subgraphs which have largest maximal cliques with the same size.

This problem is really hard.

Answer 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$.

Answer 2

Assume $s(X)=2m>0$. Let $A$ be a maximal cluster of $X$. Clearly, $s(Y)+s(Z)\ge 2m$ holds for any partition. Start with $Y_0=\emptyset$, $Z_0=X$, i.e. $s(Y_0)=0$, $s(Z_0)=2m$. For $n=1,2, \ldots$, select a vertex $z_n$ from a $Z_n$ and transfer it to $Y$, i.e. let $$Y_n=Y_{n-1}\cup\{z_n\},\qquad Z_n=Z_{n-1}\setminus\{z_n\}.$$ Then $s(Y_{n-1})\le s(Y_n)\le s(Y_{n-1})+1$ and $s(Z_{n-1})\ge s(Z_n)\ge s(Z_{n-1})-1$. At least for $n=|X|$ we have $s(Y_n)=2m>s(Z_n)$, therefore there must exist some intermediate index $0\le i<2m$ such that $s(Y_{i})\le s(Z_i)$ and $s(Y_{i+1})\ge s(Z_{i+1})$. If $s(Y_{i})= s(Z_i)$ or $s(Y_{i+1})= s(Z_{i+1})$ can be obtained by a suitable choice of the sequence $(z_n)_n$, we are done. Therefore we may assume $s(Y_i)< s(Z_i)$ and $s(Y_{i+1})> s(Z_{i+1})$, esp. the index $i$ is uniquely determined by the sequence $(z_n)_n$. We may assume wlog. that the sequence $(z_n)_n$ was chosen in such a way that $i$ is maximized. As $s(Z_{i+1})<s(Z_i)$, $z_i$ lies in all maximal clusters of $Z_i$. Let $B$ be a maximal cluster of $Z_i$ and assume $B\ne Z_i$. Then chosing $z_i\in Z_i\setminus B$ would have guaranteed $s(Z_{i+1})=s(Z_i)$, contradicting the choise of $(z_n)_n$ as maximizing $i$. Therefore, $Z_i$ is just one big cluster, $s(Z_i)=|Z_i|$.

Assume $Y_i$ as only one maximal cluster $C$. If every element of $Z_i$ is adjacent to every element of $C$, then $C\cup Z_i$ is a cluster in $X$ of size $s(Y_i)+s(Z_i)=2s(Y_i)+1$. As this is an odd number and $s(Y_i)+s(Z_i)\ge 2m$ this would be bigger than the maximal cluster. Therefore there is some $z\in Z_i$ that is not adjacent to all elements of $C$. But then choosing $z$ instead of $z_n$ would have made $s(Y_{i+1})=s(Y_i)$, thus contradicting maximality of $i$. Therefore $Y_i$ has at least two maximal clusters $C$, and $C'$, say. I've been thinking that at this point one could obtain a contradiction (i.e. increase $i$) by revising an ealier choice in the sequence $(z_n)_n$, but got lost in this attempt somehow. I guess I'll need to think about it once more. Please give me a while.

Answer 3

Consider the set $\mathcal M:=\{ M | M$ is an unextendable complete subgraph in $X\}$. By 4., we know that if $M\in\mathcal M$ has maximal size, then it is even. We also have that any $x\in X$ is contained in at least one $M$ (let it be either the point $x$ itself if separated or just an edge..).

Now pick out (one of) the biggest complete subgraph, $M_1\in\mathcal M$ and cut it into equal parts $M_1=Y_1\cup Z_1$. Now continue this procedure in the remaining subgraph $X\setminus M_1$, with next maximal complete subgraph $M_2$. Now this might have odd elements, but just divide it then into $p+(p+1)$ elements ($Y_2\cup Z_2$). And so on..

The procedure guarantees that for $Y:=Y_1\cup Y_2\cup\dots $, its largest complete subgraph will be $Y_1$ of size $s(X)/2$, similarly for $Z$.

Answer 4

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$.