Consider the following problem:

For $k \le n$, what is the smallest number of edges in the graph with $n$ vertices so that the maximum independent set has size at most $k$?

I.e., given an empty graph on $n$ vertices, I want to add the smallest number of edges so that the maximum independent set has size $k$. Let's denote it as $A(n,k)$. For example, $A(8,3)=7$, with edges $1-2-3-1$, $4-5-6-4$ and $7-8$ (two triangles and an edge).

I know that $A(n,k) \le T(n-1, k)$ where $T$ is https://oeis.org/A134546. In particular, I know that $A(n,n) = 0$ and $A(n + 1,k) \le A(n, k) + \lfloor n / k \rfloor$.

The particular construction is to maintain $k$ cliques so that the independent set can pick only vertex per clique. For example, for $A(8,3)$, the solution $1-2-3-1$, $4-5-6-4$ and $7-8$ consists of three cliques $(1,2,3)$, $(4,5,6)$, and $(7,8)$. When we add another vertex, we have $A(9,3) \le A(8,3) + 2$, since we can add edges $8-9$ and $7-9$ to have cliques $(1,2,3)$, $(4,5,6)$, and $(7,8,9)$.

Q: How to prove that we have equality, i.e. $A(n + 1,k) = A(n, k) + \lfloor n / k \rfloor$? My experiments show that it indeed holds, and, intuitively, it should hold.

I suspect there is some relation to Clique Cover, but I couldn't find it.

  • 1
    $\begingroup$ You might find Turan's theorem helpful: en.m.wikipedia.org/wiki/Tur%C3%A1n%27s_theorem $\endgroup$
    – jschnei
    Dec 27, 2023 at 19:15
  • $\begingroup$ @jschnei, Thanks, this does provide a very good bound, but, unfortunately, it doesn't show equality. E.g., assuming that what I want to prove is in fact correct, starting from $n \ge 12$, the Turan's theorem starts underestimating the number of edges. $\endgroup$
    – Dmitry
    Dec 27, 2023 at 21:09
  • $\begingroup$ I am confused, if I understand your question correctly Turan's theorem should provide a tight bound. Note that an independent set is just a clique in the complement graph, so your question is equivalent to asking "what is the largest number of edges a graph with n vertices can have so that the maximum clique has size at most k"? This is exactly answered by Turan's theorem. $\endgroup$
    – jschnei
    Dec 28, 2023 at 0:27
  • $\begingroup$ For $n=12$ and $k=8$, the answer is $4$, while Turan predicts $\ge 3$. This is if I use the last expression from en.m.wikipedia.org/wiki/Tur%C3%A1n%27s_theorem#Statement (see also link.springer.com/content/pdf/10.1007/978-3-662-57265-8_41.pdf), which gives ${12 \choose 2} - (1-\frac{1}{8}) \cdot \frac{12^2}{2} = 3$. Do you have something else in mind? $\endgroup$
    – Dmitry
    Dec 28, 2023 at 4:05
  • $\begingroup$ If you read carefully, you'll see that the formula you are using is only an asymptotic bound. The actual "tight" value is given by some $(k-1)$-partite graph. You can phrase this as finding k-1 positive integers x_1, x_2, ..., x_{k-1} that sum to n and that maximize the sum_{i < j} x_ix_j. It is not too hard to show that to do this you want to set each x_i to either floor(n/(k-1)) or ceil(n/(k-1)). $\endgroup$
    – jschnei
    Dec 28, 2023 at 17:51


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.