7
$\begingroup$

It is a trivial exercise in the pigeonhole principle to show that if an organization contains $m$ people and forms disjoint committees of $n$ members each, then at most $$\bigg \lfloor \frac{m}{n} \bigg\rfloor$$ committees can be formed.

However, I have recently attempted a seemingly simple variation on this problem: what if the committees need not be disjoint, but no two committees can share more than one member.

It seems like another easy exercise in the pigeonhole principle, but I have been unable to come up with a formula for the largest possible number of committees in terms of $m$ and $n$. Does anyone know of such a formula?

$\endgroup$
3
$\begingroup$

This is a well-known problem which I often meet in different forms. For given $m$ and $n$ let $c=c(m,n)$ be the largest possible number of committees. As far as I know, exact formulas for $c(m,n)$ are known only in particular cases, for small $m,n$ and two infinite series. There are ${m\choose 2}$ different pairs of organization members. On the other hand, each committee provides ${n\choose 2}$ such pairs, and no pair can be provided by two committees. This gives an upper bound $c\le\frac{m(m-1)}{n(n-1)}$. This upper bound is exact iff there exists a Steiner system $S(2,n,m)$. For particular values of $m,n$ their construction is based on finite projective planes. But such planes are over a finite field of a order $q$, which exists iff $q$ is a power of a prime, and there are no known other $q$ for which these exist a Steiner system $S(2, q, q^2)$ (or, equivalently, $S(2,q+1,q^2+n+1)$). Nevertheless, when $m$ is close to $n^2$ this approach provides a rather tight asymptotic lower bound for $c(m,n)$, because for sufficiently big $n$ there exists a prime number $n-n^{0.525}\le q\le n$ (see the paper “The difference between consecutive primes II” by
R. C. Baker, G. Harman, and J. Pintz). So estimating $c(m,n)$ for concrete $m$ and $n$ we usually pick a basic committee pattern provided by a finite projective plane and then try to improve the construction. The upper bound sometimes can be improved too by more subtle and complicated estimations. For instance, a current bounty question asks about minimum $m$ such that $c(m,10)\ge 40$. The current bounds are $74\le m\le 85$.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Update; the current bounds in the bounty question are at $82\leq m\leq84$. $\endgroup$ – Servaes Dec 11 '18 at 11:43
  • 2
    $\begingroup$ *Update; the minimum $m$ such that $c(m,10)\geq40$ is $m=82$. $\endgroup$ – Servaes Dec 14 '18 at 2:54
2
$\begingroup$

For a lower bound, you can form roughly double the number of committees than the disjoint case. Divide the people into groups of size $\binom{n+1}2$, ignoring the leftovers. Identify the people of each group with the edges of a complete graph on $n+1$ vertices. For each vertex of this graph, form a committee consisting of the $n+1$ edges meeting at that vertex. There will be $n+1$ committees for each group of $\binom{n+1}2$ people, for a total of $$ (n+1)\cdot\left\lfloor \frac{m}{\binom{n+1}2}\right\rfloor\approx \frac{2m}n\;\text{ committees.} $$

| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.