# Difficult variation of the committee problem

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?

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$$.
• Update; the current bounds in the bounty question are at $82\leq m\leq84$. – Servaes Dec 11 '18 at 11:43
• *Update; the minimum $m$ such that $c(m,10)\geq40$ is $m=82$. – Servaes Dec 14 '18 at 2:54
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.}$$