Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Why is the set $\mathcal{O}$ dependent of $Y$? –  Sigur Feb 8 '13 at 0:26
    
Let $A$ be a maximal complete subgraph of $X$, from 4., $A$ has even number of elements, say $A=X_0\cup Y_0$ with $|X_0|=|Y_0|$. Then try to extend both sets. –  Berci Feb 8 '13 at 0:31
    
I guess so.. Probably it could be done such a way that if a bigger complete graph must enter the picture on either side, then it has to appear on the other side, too.. I can't see it clearly how to be done.. –  Berci Feb 8 '13 at 0:44
    
Aha.. you can divide all maximal complete subgraphs of $X$! I think I got it. –  Berci Feb 8 '13 at 0:47
    
@CutieKrait That is subjective. Just as your alleged cuteness. Some might find this problem hard, yet some very easy. –  Pedro Tamaroff Feb 10 '13 at 0:46

4 Answers 4

up vote 3 down vote accepted
+50

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

share|improve this answer
    
+1. Yes, I think that is about what I wanted to try as well, but somehow ended in a dead end. –  Hagen von Eitzen Feb 15 '13 at 21:19
    
very nice answer. I don't have a critic badge, but let me criticize: what is $Y$? I think there's not a firm background for variables in mathematical logic (yet). it makes me confused when I read your answer. thanks –  user59671 Feb 16 '13 at 4:25
    
@CutieKrait : Think of $Y$ as an initially full box of vertices and of $Z$ as an initially empty box of vertices. As this answer explains, one progressively moves vertices from $Y$ to $Z$. –  Ewan Delanoy Feb 16 '13 at 9:29
    
$\langle Y, Z \rangle$ is a partition of $X$ at each step of the procedure. Strictly speaking, I'm constructing a sequence of partitions, as in @HagenvonEitzen's solution. The main difference between my solution and his is that I fix a maximal clique $G$ at the outset, and only move vertices from this clique. This keeps the structure of $Z$ simple (it's always a subset of a maximal clique of $X$). –  mjqxxxx Feb 16 '13 at 16:42

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.

share|improve this answer
    
Now seems correct that $s(Y)+s(Z)≥2m$. But there's some programming problem. the sentence "that the sequence was chosen in such a way that i is maximized" ruins any tries to program the solution. However it seems a good approach. –  user59671 Feb 15 '13 at 19:35
    
@CutieKrait How is that a programming problem? We are asked an existential proof and can be happy that it is constructive at all .. (once I'm finished, I hope) –  Hagen von Eitzen Feb 15 '13 at 21:16
    
An existential solution is welcome. But your solution is kind of semi-algorithimic. most parts can be programmed easily. –  user59671 Feb 15 '13 at 21:23

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

share|improve this answer
    
Hmm.. It's not that easy.. something still smells somewhere.. $Y_1\cup Y_2$ could be for example complete together while $M_1$ could not be extended with any points of $Y_2$.. sorry –  Berci Feb 8 '13 at 0:58
1  
if the relation was transitive, a proof similar to your proof above applies. but transitivity is not assumed. –  user59671 Feb 8 '13 at 2:31
    
The halves of $M_1$ might extend to bigger cliques in the subgraphs ... –  Hagen von Eitzen Feb 15 '13 at 17:04

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

share|improve this answer
    
One has to show that there exists a partition resulting into 2 graphs with identical maximum clique size (and the partition does not need to consist of 2 sets with equal size). However he does not need to say how to split. My tries show graph theory approach does not simplify solving the problem. –  user59671 Feb 13 '13 at 0:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.