Difficult variation of the committee problem
$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} biggrfloor$$
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?
combinatorics elementary-set-theory pigeonhole-principle
$endgroup$
add a comment |
$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} biggrfloor$$
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?
combinatorics elementary-set-theory pigeonhole-principle
$endgroup$
add a comment |
$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} biggrfloor$$
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?
combinatorics elementary-set-theory pigeonhole-principle
$endgroup$
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} biggrfloor$$
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?
combinatorics elementary-set-theory pigeonhole-principle
combinatorics elementary-set-theory pigeonhole-principle
asked Dec 7 '18 at 21:55
FrpzzdFrpzzd
22.8k840108
22.8k840108
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$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 ${mchoose 2}$ different pairs of organization members. On the other hand, each committee provides ${nchoose 2}$ such pairs, and no pair can be provided by two committees. This gives an upper bound $clefrac{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 qle 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 $74le mle 85$.
$endgroup$
2
$begingroup$
Update; the current bounds in the bounty question are at $82leq mleq84$.
$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
add a comment |
$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)cdotleftlfloor frac{m}{binom{n+1}2}rightrfloorapprox frac{2m}n;text{ committees.}
$$
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3030406%2fdifficult-variation-of-the-committee-problem%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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 ${mchoose 2}$ different pairs of organization members. On the other hand, each committee provides ${nchoose 2}$ such pairs, and no pair can be provided by two committees. This gives an upper bound $clefrac{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 qle 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 $74le mle 85$.
$endgroup$
2
$begingroup$
Update; the current bounds in the bounty question are at $82leq mleq84$.
$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
add a comment |
$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 ${mchoose 2}$ different pairs of organization members. On the other hand, each committee provides ${nchoose 2}$ such pairs, and no pair can be provided by two committees. This gives an upper bound $clefrac{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 qle 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 $74le mle 85$.
$endgroup$
2
$begingroup$
Update; the current bounds in the bounty question are at $82leq mleq84$.
$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
add a comment |
$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 ${mchoose 2}$ different pairs of organization members. On the other hand, each committee provides ${nchoose 2}$ such pairs, and no pair can be provided by two committees. This gives an upper bound $clefrac{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 qle 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 $74le mle 85$.
$endgroup$
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 ${mchoose 2}$ different pairs of organization members. On the other hand, each committee provides ${nchoose 2}$ such pairs, and no pair can be provided by two committees. This gives an upper bound $clefrac{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 qle 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 $74le mle 85$.
edited Dec 8 '18 at 19:52
answered Dec 8 '18 at 6:04
Alex RavskyAlex Ravsky
40.4k32282
40.4k32282
2
$begingroup$
Update; the current bounds in the bounty question are at $82leq mleq84$.
$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
add a comment |
2
$begingroup$
Update; the current bounds in the bounty question are at $82leq mleq84$.
$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
2
$begingroup$
Update; the current bounds in the bounty question are at $82leq mleq84$.
$endgroup$
– Servaes
Dec 11 '18 at 11:43
$begingroup$
Update; the current bounds in the bounty question are at $82leq mleq84$.
$endgroup$
– Servaes
Dec 11 '18 at 11:43
2
2
$begingroup$
*Update; the minimum $m$ such that $c(m,10)geq40$ is $m=82$.
$endgroup$
– Servaes
Dec 14 '18 at 2:54
$begingroup$
*Update; the minimum $m$ such that $c(m,10)geq40$ is $m=82$.
$endgroup$
– Servaes
Dec 14 '18 at 2:54
add a comment |
$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)cdotleftlfloor frac{m}{binom{n+1}2}rightrfloorapprox frac{2m}n;text{ committees.}
$$
$endgroup$
add a comment |
$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)cdotleftlfloor frac{m}{binom{n+1}2}rightrfloorapprox frac{2m}n;text{ committees.}
$$
$endgroup$
add a comment |
$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)cdotleftlfloor frac{m}{binom{n+1}2}rightrfloorapprox frac{2m}n;text{ committees.}
$$
$endgroup$
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)cdotleftlfloor frac{m}{binom{n+1}2}rightrfloorapprox frac{2m}n;text{ committees.}
$$
answered Dec 8 '18 at 5:11
Mike EarnestMike Earnest
21.9k12051
21.9k12051
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3030406%2fdifficult-variation-of-the-committee-problem%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown