9
$\begingroup$

I asked a question few days ago which was from a local math contest in my city. The question and the solution seems interesting to me and I am interested in solving the generalization of the problem. So, the generalized problem is as follows:

Professor Liyung wants to make a math club consisting of his $n$ students. But there is a problem. Each student is enemies with exactly $k$ ($1\leq k \leq n-1$) students. And no one wills to be a member of the club if any of his enemies is already a member of the club. Let $M$ be the maximum number of members the club can have. Find all possible values of $M$. (If student $A$ is an enemy with student $B$, then student $B$ is an enemy with student $A$. Student $A$ is not enemy with himself.)

Here, $n,k$ are given numbers such that they satisfy the conditions of the problem (i.e. it is possible to draw a graph with $n$ vertices each of the vertices having degree $k$). Here are my workings regarding the problem:

My workings

I first tried for a fixed value of $k$. And I got the following:

  • For $k=1$, the problem statement is true for only even $n$. Then, $M$ has only one possible value that is $\frac n 2$.
  • For $k=2$, all values of $M$ are possible in the range $[\lceil\frac n 3\rceil,\lfloor\frac n 2\rfloor]$. (Explanation is in the link.)
  • For $k=3$, the upper bound of $M$ is $\lfloor \frac n 3\rfloor$ and the lower bound of $M$ is $\lceil\frac n 4\rceil$. However, I don't have a nice argument to prove the upper bound. The proof of the lower bound is as follows:
    Proof: If we choose $\lceil\frac n 4\rceil -1$ students as members, then there are at most $3\lceil\frac n 4\rceil -3$ students who can't be members of the club. Then, we can choose at least $1$ students from the remaining students as a member of the club. This proves that $M$ is at least $\lceil\frac n 4\rceil$ for $k=3$.

So, I think all values of $M$ are in $[\lceil\frac{n}{k+1}\rceil,\lfloor\frac{n}{k}\rfloor]$. The lower bound can be proved by following the similar steps as in for $k=3$. However, I am unable to show that all values in $[\lceil\frac{n}{k+1}\rceil,\lfloor\frac{n}{k}\rfloor]$ can be a value of $M$.

I hope my thoughts are correct. I need to complete the solution i.e. proving the upper bound and showing that all values in the stated interval are possible. The original problem involves graph theory in its solution. So, can the generalized problem be solved with graph theory?

$\endgroup$
4
  • $\begingroup$ For $k=3, n=6$ we have $M=3$. Also, for $k=3, n=8$ I find $M=4$. $\endgroup$ Commented Jul 18, 2021 at 15:37
  • $\begingroup$ The upper bound can be n/2 for larger n and fixed k. Take a bipartite k-regular graph. If you don't know what that means, split the students into 2 sets and always draw the enemies between the two sets (not within) $\endgroup$ Commented Jul 18, 2021 at 16:59
  • $\begingroup$ Why do you use word maximal for $M$. You can just ask what values can $M$ have? $\endgroup$ Commented Jul 18, 2021 at 17:01
  • $\begingroup$ @Aqua I didn't get your point. $M$ is defined such that it's the maximum number of members the club can have. And I said Find all possible values of $M$. As there are more than one values of $M$ for each $k$ and $n$, there exists a maximal $M$ for each case. $\endgroup$ Commented Jul 18, 2021 at 17:26

2 Answers 2

Reset to default
5
$\begingroup$

You are right about the lower bound, but not the upper. The correct upper bound is $\lfloor n/2\rfloor$ for any fixed value of $k\leq n/2$.

To see that this is an upper bound, fix a club with $M$ members and count edges of the graph, i.e. pairs who are enemies. There must be $Mk$ pairs with exactly one person in the club (each person in the club has $k$ enemies, none of whom are in the club). There are some number $r\geq 0$ of pairs who are both outside the club. Now everyone not in the club has $k$ enemies, and that gives $(n-M)k$ ordered pairs where the first person is not in the club. This counts each of the $Mk$ pairs with exactly one person in the club once, and each of the $r$ pairs of two non-members twice. So $(n-M)k=2r+Mk$, and since $r\geq 0$ we have $n-M\geq M$.

This bound can be achieved for any even $n$. (If $k$ is odd, then any graph with every vertex having degree $k$ must have $n$ being even.) To see this, start with the complete bipartite graph with both parts having size $n/2$ - every vertex has degree $n/2$. Now remove a perfect matching, which exists by Hall's theorem (a corollary of Hall's theorem is that any regular bipartite graph - unless it is $0$-regular - has a perfect matching). This decreases all degrees by $1$. Keep doing this until every degree is $k$. Clearly either part of the original graph contains no edges, so is a valid club, and has size $n/2$.

Now to obtain anything in between the two bounds, you just need to mix the two constructions. E.g. if $k=3$ and $n=100$ you can get $M=25$ by taking $25$ copies of $K_4$, or $M=50$ by the construction above. To get, say, $M=41$, take $9$ copies of $K_4$ and do the construction above on the remaining $64$ vertices. Your optimal club will then have one person from each $K_4$ and $32$ people from the remainder.

$\endgroup$
2
$\begingroup$

Imitating proof from the link, we have $k\cdot M \geq n-M$ so $M\geq {n\over k+1}$

For the upper bound:

Let $G$ be a graph of students being connected iff they are enemy. Clearly this graph has $\varepsilon ={nk\over 2}$. Suppose set of vertices of this graph can be represented as union of maximal cliques $Q_1,Q_2,...Q_m$. Since we can choose from each clique at most $1$ student we have $M\leq m$. So we need to find the minimum value of $m$. But this now is Clique Covering Number problem.

So, if:

  • $n=2l+1$ then we can make $l+1$ cliques so we have $M\leq l+1 = \lfloor {n+1\over 2} \rfloor $.
  • $n=2l$ then we can make $l$ cliques so we have $M\leq l = \lfloor {n\over 2} \rfloor $.
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.