Subsets of a set with common elements between themselves
Let $S={1,2,ldots,n}$. Let $A_isubset S$ for $iin{1,2,ldots,m}$. Impose the following conditions
$|A_i|=r$ with $r<n$ for all $i$.
$|A_icap A_j|=t$ for all $ineq j$, with $t<r$.
Let $n,r,t$ be fixed. What is the maximum number $m$ of subsets $A_i$ that satisfy these conditions?
The question arises from my observation of a game called Rafly, where there are 55 cards, each with 8 images on them. No matter which 2 cards you pick, they have one and only one common image. I want to generalize this game by using the minimum number of $n$ images, having $m$ cards, each with $r$ images and $t$ common images. However, I am having trouble with finding $m$ given $n,r$ and $t$.
In the case of $t=1$ I start to build the cards like this:
$$A_1 = {1,2,ldots,r}.$$
A new card must have one common element with the first card:
$$A_2 = {c_{1,2}, r+1,ldots, 2r-1 },$$
where $c_{1,2}in A_1$. A new card must have one common element with the second and first cards:
$$A_3 = {c_{1,3},c_{2,3}, 2r,2r+1,ldots, 3r-3},$$
where $c_{1,3}in A_1$ and $c_{2,3}in A_2setminus A_1$. Following this reasoning I conclude that there are $n=r(r+1)/2$ different images. But how many cards are there? How are these quantities related to $t$? Thanks a lot.
combinatorics extremal-combinatorics combinatorial-designs
edited yesterday
bof
50.5k457119
asked yesterday
Vladimir Vargas
3,33811529
|
show 7 more comments
Let $S={1,2,ldots,n}$. Let $A_isubset S$ for $iin{1,2,ldots,m}$. Impose the following conditions
$|A_i|=r$ with $r<n$ for all $i$.
$|A_icap A_j|=t$ for all $ineq j$, with $t<r$.
Let $n,r,t$ be fixed. What is the maximum number $m$ of subsets $A_i$ that satisfy these conditions?
The question arises from my observation of a game called Rafly, where there are 55 cards, each with 8 images on them. No matter which 2 cards you pick, they have one and only one common image. I want to generalize this game by using the minimum number of $n$ images, having $m$ cards, each with $r$ images and $t$ common images. However, I am having trouble with finding $m$ given $n,r$ and $t$.
In the case of $t=1$ I start to build the cards like this:
$$A_1 = {1,2,ldots,r}.$$
A new card must have one common element with the first card:
$$A_2 = {c_{1,2}, r+1,ldots, 2r-1 },$$
where $c_{1,2}in A_1$. A new card must have one common element with the second and first cards:
$$A_3 = {c_{1,3},c_{2,3}, 2r,2r+1,ldots, 3r-3},$$
where $c_{1,3}in A_1$ and $c_{2,3}in A_2setminus A_1$. Following this reasoning I conclude that there are $n=r(r+1)/2$ different images. But how many cards are there? How are these quantities related to $t$? Thanks a lot.
combinatorics extremal-combinatorics combinatorial-designs
edited yesterday
bof
50.5k457119
asked yesterday
Vladimir Vargas
3,33811529
1
There is a problem in your reasoning: What if $c_{1,3}=c_{2,3}$? More generally, you can have a "star-shaped" collection of sets all with a single common element and a bunch of unique elements, and there is no bound on how many you can have, meaning that for $r,t$ fixed there is no maximum $m$, assuming $n$ is allowed to grow as well.
– Mario Carneiro
yesterday
@MarioCarneiro Right, I corrected the errors
– Vladimir Vargas
yesterday
Well no, the error is still there, because $c_{1,3}=c_{2,3}$ is a legal choice. You don't know that they are distinct, and so you don't know that the image count is up to $3r-3$ after the third card - it could also be $3r-2$. But I guess you mean to say that there are at least $3r-3$ images in use in the first three cards. You can continue this lower bound up until you get to $A_r$, at which point you have used $r(r+1)/2$ images and $m=r$, but then the lower bound stops and $m$ can possibly keep increasing, reusing all the old cards for a while. The true upper bound for $m$ is farther on.
– Mario Carneiro
yesterday
@MarioCarneiro if $c_{2,3}in A_2setminus A_1$ it can't be $c_{1,3}$
– Vladimir Vargas
yesterday
1
This game is known as "Spot It!" in the US and "Dobble" in Europe. Searching for these names turns up several questions about these games across StackExchange. For example, on this site: one, two, three. You might find (partial) answers there or by following further links.
– Alex Kruckman
yesterday
|
show 7 more comments
Let $S={1,2,ldots,n}$. Let $A_isubset S$ for $iin{1,2,ldots,m}$. Impose the following conditions
$|A_i|=r$ with $r<n$ for all $i$.
$|A_icap A_j|=t$ for all $ineq j$, with $t<r$.
Let $n,r,t$ be fixed. What is the maximum number $m$ of subsets $A_i$ that satisfy these conditions?
The question arises from my observation of a game called Rafly, where there are 55 cards, each with 8 images on them. No matter which 2 cards you pick, they have one and only one common image. I want to generalize this game by using the minimum number of $n$ images, having $m$ cards, each with $r$ images and $t$ common images. However, I am having trouble with finding $m$ given $n,r$ and $t$.
In the case of $t=1$ I start to build the cards like this:
$$A_1 = {1,2,ldots,r}.$$
A new card must have one common element with the first card:
$$A_2 = {c_{1,2}, r+1,ldots, 2r-1 },$$
where $c_{1,2}in A_1$. A new card must have one common element with the second and first cards:
$$A_3 = {c_{1,3},c_{2,3}, 2r,2r+1,ldots, 3r-3},$$
where $c_{1,3}in A_1$ and $c_{2,3}in A_2setminus A_1$. Following this reasoning I conclude that there are $n=r(r+1)/2$ different images. But how many cards are there? How are these quantities related to $t$? Thanks a lot.
combinatorics extremal-combinatorics combinatorial-designs
edited yesterday
bof
50.5k457119
asked yesterday
Vladimir Vargas
3,33811529
Let $S={1,2,ldots,n}$. Let $A_isubset S$ for $iin{1,2,ldots,m}$. Impose the following conditions
$|A_i|=r$ with $r<n$ for all $i$.
$|A_icap A_j|=t$ for all $ineq j$, with $t<r$.
Let $n,r,t$ be fixed. What is the maximum number $m$ of subsets $A_i$ that satisfy these conditions?
The question arises from my observation of a game called Rafly, where there are 55 cards, each with 8 images on them. No matter which 2 cards you pick, they have one and only one common image. I want to generalize this game by using the minimum number of $n$ images, having $m$ cards, each with $r$ images and $t$ common images. However, I am having trouble with finding $m$ given $n,r$ and $t$.
In the case of $t=1$ I start to build the cards like this:
$$A_1 = {1,2,ldots,r}.$$
A new card must have one common element with the first card:
$$A_2 = {c_{1,2}, r+1,ldots, 2r-1 },$$
where $c_{1,2}in A_1$. A new card must have one common element with the second and first cards:
$$A_3 = {c_{1,3},c_{2,3}, 2r,2r+1,ldots, 3r-3},$$
where $c_{1,3}in A_1$ and $c_{2,3}in A_2setminus A_1$. Following this reasoning I conclude that there are $n=r(r+1)/2$ different images. But how many cards are there? How are these quantities related to $t$? Thanks a lot.
combinatorics extremal-combinatorics combinatorial-designs
combinatorics extremal-combinatorics combinatorial-designs
edited yesterday
bof
50.5k457119
asked yesterday
Vladimir Vargas
3,33811529
edited yesterday
bof
50.5k457119
asked yesterday
Vladimir Vargas
3,33811529
edited yesterday
bof
50.5k457119
edited yesterday
bof
50.5k457119
edited yesterday
bof
50.5k457119
50.5k457119
asked yesterday
Vladimir Vargas
3,33811529
asked yesterday
Vladimir Vargas
3,33811529
asked yesterday
Vladimir Vargas
3,33811529
3,33811529
1
There is a problem in your reasoning: What if $c_{1,3}=c_{2,3}$? More generally, you can have a "star-shaped" collection of sets all with a single common element and a bunch of unique elements, and there is no bound on how many you can have, meaning that for $r,t$ fixed there is no maximum $m$, assuming $n$ is allowed to grow as well.
– Mario Carneiro
yesterday
@MarioCarneiro Right, I corrected the errors
– Vladimir Vargas
yesterday
Well no, the error is still there, because $c_{1,3}=c_{2,3}$ is a legal choice. You don't know that they are distinct, and so you don't know that the image count is up to $3r-3$ after the third card - it could also be $3r-2$. But I guess you mean to say that there are at least $3r-3$ images in use in the first three cards. You can continue this lower bound up until you get to $A_r$, at which point you have used $r(r+1)/2$ images and $m=r$, but then the lower bound stops and $m$ can possibly keep increasing, reusing all the old cards for a while. The true upper bound for $m$ is farther on.
– Mario Carneiro
yesterday
@MarioCarneiro if $c_{2,3}in A_2setminus A_1$ it can't be $c_{1,3}$
– Vladimir Vargas
yesterday
1
This game is known as "Spot It!" in the US and "Dobble" in Europe. Searching for these names turns up several questions about these games across StackExchange. For example, on this site: one, two, three. You might find (partial) answers there or by following further links.
– Alex Kruckman
yesterday
|
show 7 more comments
1
There is a problem in your reasoning: What if $c_{1,3}=c_{2,3}$? More generally, you can have a "star-shaped" collection of sets all with a single common element and a bunch of unique elements, and there is no bound on how many you can have, meaning that for $r,t$ fixed there is no maximum $m$, assuming $n$ is allowed to grow as well.
– Mario Carneiro
yesterday
@MarioCarneiro Right, I corrected the errors
– Vladimir Vargas
yesterday
Well no, the error is still there, because $c_{1,3}=c_{2,3}$ is a legal choice. You don't know that they are distinct, and so you don't know that the image count is up to $3r-3$ after the third card - it could also be $3r-2$. But I guess you mean to say that there are at least $3r-3$ images in use in the first three cards. You can continue this lower bound up until you get to $A_r$, at which point you have used $r(r+1)/2$ images and $m=r$, but then the lower bound stops and $m$ can possibly keep increasing, reusing all the old cards for a while. The true upper bound for $m$ is farther on.
– Mario Carneiro
yesterday
@MarioCarneiro if $c_{2,3}in A_2setminus A_1$ it can't be $c_{1,3}$
– Vladimir Vargas
yesterday
1
This game is known as "Spot It!" in the US and "Dobble" in Europe. Searching for these names turns up several questions about these games across StackExchange. For example, on this site: one, two, three. You might find (partial) answers there or by following further links.
– Alex Kruckman
yesterday
1
1
There is a problem in your reasoning: What if $c_{1,3}=c_{2,3}$? More generally, you can have a "star-shaped" collection of sets all with a single common element and a bunch of unique elements, and there is no bound on how many you can have, meaning that for $r,t$ fixed there is no maximum $m$, assuming $n$ is allowed to grow as well.
– Mario Carneiro
yesterday
There is a problem in your reasoning: What if $c_{1,3}=c_{2,3}$? More generally, you can have a "star-shaped" collection of sets all with a single common element and a bunch of unique elements, and there is no bound on how many you can have, meaning that for $r,t$ fixed there is no maximum $m$, assuming $n$ is allowed to grow as well.
– Mario Carneiro
yesterday
@MarioCarneiro Right, I corrected the errors
– Vladimir Vargas
yesterday
@MarioCarneiro Right, I corrected the errors
– Vladimir Vargas
yesterday
Well no, the error is still there, because $c_{1,3}=c_{2,3}$ is a legal choice. You don't know that they are distinct, and so you don't know that the image count is up to $3r-3$ after the third card - it could also be $3r-2$. But I guess you mean to say that there are at least $3r-3$ images in use in the first three cards. You can continue this lower bound up until you get to $A_r$, at which point you have used $r(r+1)/2$ images and $m=r$, but then the lower bound stops and $m$ can possibly keep increasing, reusing all the old cards for a while. The true upper bound for $m$ is farther on.
– Mario Carneiro
yesterday
Well no, the error is still there, because $c_{1,3}=c_{2,3}$ is a legal choice. You don't know that they are distinct, and so you don't know that the image count is up to $3r-3$ after the third card - it could also be $3r-2$. But I guess you mean to say that there are at least $3r-3$ images in use in the first three cards. You can continue this lower bound up until you get to $A_r$, at which point you have used $r(r+1)/2$ images and $m=r$, but then the lower bound stops and $m$ can possibly keep increasing, reusing all the old cards for a while. The true upper bound for $m$ is farther on.
– Mario Carneiro
yesterday
@MarioCarneiro if $c_{2,3}in A_2setminus A_1$ it can't be $c_{1,3}$
– Vladimir Vargas
yesterday
@MarioCarneiro if $c_{2,3}in A_2setminus A_1$ it can't be $c_{1,3}$
– Vladimir Vargas
yesterday
1
1
This game is known as "Spot It!" in the US and "Dobble" in Europe. Searching for these names turns up several questions about these games across StackExchange. For example, on this site: one, two, three. You might find (partial) answers there or by following further links.
– Alex Kruckman
yesterday
This game is known as "Spot It!" in the US and "Dobble" in Europe. Searching for these names turns up several questions about these games across StackExchange. For example, on this site: one, two, three. You might find (partial) answers there or by following further links.
– Alex Kruckman
yesterday
|
show 7 more comments
1 Answer
1
active
oldest
votes
Your problem in the $t=1$ case was asked here. I will provide a generalization of those ideas to your problem.
There are $binom{n}{t+1}$ subsets of $S$ with size $t+1$. Each set $A_i$ has $binom{r}{t+1}$ subsets of size $t+1$. Furthermore, the $binom{r}{t+1}$ subsets of size $t+1$ for $A_i$ must be different then those for $A_j$, because $A_i$ and $A_j$ only have $t$ elements in common. Therefore, counting up the total number of subsets of size $t+1$ found in some set $A_i$, we get
$$
mcdotbinom{r}{t+1}le binom{n}{t+1}
$$
This give you an upper bound on $m$.
If equality is attained, this would mean that every subset of size $t+1$ is contained in exactly one set $A_i$. . This means that you have a Steiner system $S(t+1,r,n)$. Not much is known about when Steiner systems exist; see the other answer for some more information.
answered yesterday
Mike Earnest
20.5k11950
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%2f3062304%2fsubsets-of-a-set-with-common-elements-between-themselves%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
Your problem in the $t=1$ case was asked here. I will provide a generalization of those ideas to your problem.
There are $binom{n}{t+1}$ subsets of $S$ with size $t+1$. Each set $A_i$ has $binom{r}{t+1}$ subsets of size $t+1$. Furthermore, the $binom{r}{t+1}$ subsets of size $t+1$ for $A_i$ must be different then those for $A_j$, because $A_i$ and $A_j$ only have $t$ elements in common. Therefore, counting up the total number of subsets of size $t+1$ found in some set $A_i$, we get
$$
mcdotbinom{r}{t+1}le binom{n}{t+1}
$$
This give you an upper bound on $m$.
If equality is attained, this would mean that every subset of size $t+1$ is contained in exactly one set $A_i$. . This means that you have a Steiner system $S(t+1,r,n)$. Not much is known about when Steiner systems exist; see the other answer for some more information.
answered yesterday
Mike Earnest
20.5k11950
add a comment |
Your problem in the $t=1$ case was asked here. I will provide a generalization of those ideas to your problem.
There are $binom{n}{t+1}$ subsets of $S$ with size $t+1$. Each set $A_i$ has $binom{r}{t+1}$ subsets of size $t+1$. Furthermore, the $binom{r}{t+1}$ subsets of size $t+1$ for $A_i$ must be different then those for $A_j$, because $A_i$ and $A_j$ only have $t$ elements in common. Therefore, counting up the total number of subsets of size $t+1$ found in some set $A_i$, we get
$$
mcdotbinom{r}{t+1}le binom{n}{t+1}
$$
This give you an upper bound on $m$.
If equality is attained, this would mean that every subset of size $t+1$ is contained in exactly one set $A_i$. . This means that you have a Steiner system $S(t+1,r,n)$. Not much is known about when Steiner systems exist; see the other answer for some more information.
answered yesterday
Mike Earnest
20.5k11950
add a comment |
Your problem in the $t=1$ case was asked here. I will provide a generalization of those ideas to your problem.
There are $binom{n}{t+1}$ subsets of $S$ with size $t+1$. Each set $A_i$ has $binom{r}{t+1}$ subsets of size $t+1$. Furthermore, the $binom{r}{t+1}$ subsets of size $t+1$ for $A_i$ must be different then those for $A_j$, because $A_i$ and $A_j$ only have $t$ elements in common. Therefore, counting up the total number of subsets of size $t+1$ found in some set $A_i$, we get
$$
mcdotbinom{r}{t+1}le binom{n}{t+1}
$$
This give you an upper bound on $m$.
If equality is attained, this would mean that every subset of size $t+1$ is contained in exactly one set $A_i$. . This means that you have a Steiner system $S(t+1,r,n)$. Not much is known about when Steiner systems exist; see the other answer for some more information.
answered yesterday
Mike Earnest
20.5k11950
Your problem in the $t=1$ case was asked here. I will provide a generalization of those ideas to your problem.
There are $binom{n}{t+1}$ subsets of $S$ with size $t+1$. Each set $A_i$ has $binom{r}{t+1}$ subsets of size $t+1$. Furthermore, the $binom{r}{t+1}$ subsets of size $t+1$ for $A_i$ must be different then those for $A_j$, because $A_i$ and $A_j$ only have $t$ elements in common. Therefore, counting up the total number of subsets of size $t+1$ found in some set $A_i$, we get
$$
mcdotbinom{r}{t+1}le binom{n}{t+1}
$$
This give you an upper bound on $m$.
If equality is attained, this would mean that every subset of size $t+1$ is contained in exactly one set $A_i$. . This means that you have a Steiner system $S(t+1,r,n)$. Not much is known about when Steiner systems exist; see the other answer for some more information.
answered yesterday
Mike Earnest
20.5k11950
answered yesterday
Mike Earnest
20.5k11950
answered yesterday
Mike Earnest
20.5k11950
answered yesterday
Mike Earnest
20.5k11950
20.5k11950
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3062304%2fsubsets-of-a-set-with-common-elements-between-themselves%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
1
There is a problem in your reasoning: What if $c_{1,3}=c_{2,3}$? More generally, you can have a "star-shaped" collection of sets all with a single common element and a bunch of unique elements, and there is no bound on how many you can have, meaning that for $r,t$ fixed there is no maximum $m$, assuming $n$ is allowed to grow as well.
– Mario Carneiro
yesterday
@MarioCarneiro Right, I corrected the errors
– Vladimir Vargas
yesterday
Well no, the error is still there, because $c_{1,3}=c_{2,3}$ is a legal choice. You don't know that they are distinct, and so you don't know that the image count is up to $3r-3$ after the third card - it could also be $3r-2$. But I guess you mean to say that there are at least $3r-3$ images in use in the first three cards. You can continue this lower bound up until you get to $A_r$, at which point you have used $r(r+1)/2$ images and $m=r$, but then the lower bound stops and $m$ can possibly keep increasing, reusing all the old cards for a while. The true upper bound for $m$ is farther on.
– Mario Carneiro
yesterday
@MarioCarneiro if $c_{2,3}in A_2setminus A_1$ it can't be $c_{1,3}$
– Vladimir Vargas
yesterday
1
This game is known as "Spot It!" in the US and "Dobble" in Europe. Searching for these names turns up several questions about these games across StackExchange. For example, on this site: one, two, three. You might find (partial) answers there or by following further links.
– Alex Kruckman
yesterday