Given a simple graph $G=(V,E)$ s.t. $2\mid \omega(G)$,
Show that $\exists S\subseteq V\text{ s.t. } f_G(S)=f_G(V\setminus S)$
where $f_G(A)$ is the clique number of the sub-graph of $G$ induced by vertex set $A$.

I'm have trouble proving this property of clique number.
Several approaches have been tried but none leads to a correct proof.

  • IDEA: Firstly, divide a largest clique $C$ of $G$ evenly into to subset $A,B$.
    I want to continuously add vertices into $A$ and $B$ keeping the clique number of the sub-graphs induced by $A,B$ unchanged.
    1. For every other vertex $v$, we have $f(A\cup \{v\})=f(A)\lor f(B\cup \{v\})=f(B)$, otherwise $A\cup B\cup\{v\}$ is a clique bigger than $C$.
    2. After adding the first vertex, I can show that every other vertex $v'$ satisfy $f(A\cup \{v'\})=f(A)\lor f(B\cup \{v'\})=f(B)$ using the pigeonhole principle.
    3. However, after adding $|A|$ vertices into $A$ or $|B|$ vertices into $B$, I can no longer have the property: $f(A+v)=f(A)\lor f(B+v)=f(B)$
  • IDEA: Continuously find the largest clique $C=\{v_1,\ldots v_k\}$
    if $2\mid k$ split it evenly, otherwise split it into $\lfloor k/2\rfloor,\lceil k/2\rceil$
    This doesn't work, adding the vertices arbitrarily can cause unpredictable increase in clique number.
  • other naive approaches.

I really need some hint to solve it.
btw, I don't know why the graph should be simple, I can't see a difference.

  • $\begingroup$ BTW, I am also wondering if it is proper to post the same problem on math-stackexchange. I am familiar with the math site but not the CS site. $\endgroup$
    – hehelego
    May 24 at 9:02
  • 1
    $\begingroup$ This post is appropriate on CS.SE. It is not recommanded to cross-post on multiple SE sites. $\endgroup$
    – Nathaniel
    May 24 at 10:01
  • $\begingroup$ The pentagon is a counterexample to any approach that attempts to strictly reduce $\omega$: It has $\omega=2$, and so does either $G[S]$ or $G[V\setminus S]$ for all $S \subseteq V$. $\endgroup$ May 24 at 11:19
  • 2
    $\begingroup$ After tons of searching and discussion. I find that this is exactly the problem 3 in IMO 2007. $\endgroup$
    – hehelego
    May 24 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.