Let $ T= {A subset {1,2,ldots,9 } ; |A|=5 }$. Find $n_{min}$ if for any $ X subset T $, $|X|=n$ exist $A,B...
$begingroup$
Let $ S={1,2,ldots,9 }$ and $ T= {A subset S ; |A|=5 }$.
Find the minimum value of $n$ such that for any $ X subset T $ with $|X|=n$ there exist two sets $A,B in X$ so that $ |A cap B|=4$.
Let $mathcal{F}={A_1,A_2,ldots,A_k} subset T$ be a family of $5$-element subsets of $S$ such that: $$|Acap B|leq 3;;;;;;forall A,B in mathcal{F}, Aneq B$$ Now we are interested in $k_{max}$.
Make a following bipartite graph. Connect $A_i$ with a $4$-element subset $Bsubset S$ if and only if $Bsubset A_i$.
Then the degree of any $B$ is at most $1$, while the degree of each $A_i$ is $ {5choose 4}=5$.
So we have $1cdot {9choose 4}geq 5 cdot k$, and so $kleq 25$. Thus the partial answer is $n_{min}leq 26$.
Now I don't know how to find a configuration for $n=26$. If I understand we are searching for Steiner system $S(4,5,9)$?
combinatorics graph-theory optimization extremal-combinatorics
asked Jan 16 at 15:10
Maria MazurMaria Mazur
49.6k1361124
$endgroup$
add a comment |
$begingroup$
Let $ S={1,2,ldots,9 }$ and $ T= {A subset S ; |A|=5 }$.
Find the minimum value of $n$ such that for any $ X subset T $ with $|X|=n$ there exist two sets $A,B in X$ so that $ |A cap B|=4$.
Let $mathcal{F}={A_1,A_2,ldots,A_k} subset T$ be a family of $5$-element subsets of $S$ such that: $$|Acap B|leq 3;;;;;;forall A,B in mathcal{F}, Aneq B$$ Now we are interested in $k_{max}$.
Make a following bipartite graph. Connect $A_i$ with a $4$-element subset $Bsubset S$ if and only if $Bsubset A_i$.
Then the degree of any $B$ is at most $1$, while the degree of each $A_i$ is $ {5choose 4}=5$.
So we have $1cdot {9choose 4}geq 5 cdot k$, and so $kleq 25$. Thus the partial answer is $n_{min}leq 26$.
Now I don't know how to find a configuration for $n=26$. If I understand we are searching for Steiner system $S(4,5,9)$?
combinatorics graph-theory optimization extremal-combinatorics
asked Jan 16 at 15:10
Maria MazurMaria Mazur
49.6k1361124
$endgroup$
1
$begingroup$
A family $mathcal F$ of size $25$ would not quite be a Steiner system, as the number of subsets of ${1,dots,9}$ of size four contained in some element of $mathcal F$ would be $5cdot 25$, which is one less than $binom94=126$.
$endgroup$
– Mike Earnest
Jan 16 at 20:51
$begingroup$
You want $25$ five-element sets whose four-element subsets comprise all but one of the four element subsets of $[9]$. Consider the $120times 125$ matrix of 0's and 1's whose columns are indexed by four-element subset of $[9]$, except for ${1,2,3,4}$, and whose rows are indexed by five-element subsets of $[9]$, except for those who contain ${1,2,3,4}$. Then you want a subset of rows whose sum is the vector of $125$ ones, with a one where the row contains the column. This is solvable by Knuth's Algorithm X.
$endgroup$
– Mike Earnest
Jan 16 at 21:05
add a comment |
$begingroup$
Let $ S={1,2,ldots,9 }$ and $ T= {A subset S ; |A|=5 }$.
Find the minimum value of $n$ such that for any $ X subset T $ with $|X|=n$ there exist two sets $A,B in X$ so that $ |A cap B|=4$.
Let $mathcal{F}={A_1,A_2,ldots,A_k} subset T$ be a family of $5$-element subsets of $S$ such that: $$|Acap B|leq 3;;;;;;forall A,B in mathcal{F}, Aneq B$$ Now we are interested in $k_{max}$.
Make a following bipartite graph. Connect $A_i$ with a $4$-element subset $Bsubset S$ if and only if $Bsubset A_i$.
Then the degree of any $B$ is at most $1$, while the degree of each $A_i$ is $ {5choose 4}=5$.
So we have $1cdot {9choose 4}geq 5 cdot k$, and so $kleq 25$. Thus the partial answer is $n_{min}leq 26$.
Now I don't know how to find a configuration for $n=26$. If I understand we are searching for Steiner system $S(4,5,9)$?
combinatorics graph-theory optimization extremal-combinatorics
asked Jan 16 at 15:10
Maria MazurMaria Mazur
49.6k1361124
$endgroup$
Let $ S={1,2,ldots,9 }$ and $ T= {A subset S ; |A|=5 }$.
Find the minimum value of $n$ such that for any $ X subset T $ with $|X|=n$ there exist two sets $A,B in X$ so that $ |A cap B|=4$.
Let $mathcal{F}={A_1,A_2,ldots,A_k} subset T$ be a family of $5$-element subsets of $S$ such that: $$|Acap B|leq 3;;;;;;forall A,B in mathcal{F}, Aneq B$$ Now we are interested in $k_{max}$.
Make a following bipartite graph. Connect $A_i$ with a $4$-element subset $Bsubset S$ if and only if $Bsubset A_i$.
Then the degree of any $B$ is at most $1$, while the degree of each $A_i$ is $ {5choose 4}=5$.
So we have $1cdot {9choose 4}geq 5 cdot k$, and so $kleq 25$. Thus the partial answer is $n_{min}leq 26$.
Now I don't know how to find a configuration for $n=26$. If I understand we are searching for Steiner system $S(4,5,9)$?
combinatorics graph-theory optimization extremal-combinatorics
combinatorics graph-theory optimization extremal-combinatorics
asked Jan 16 at 15:10
Maria MazurMaria Mazur
49.6k1361124
asked Jan 16 at 15:10
Maria MazurMaria Mazur
49.6k1361124
edited Jan 17 at 10:13
Maria Mazur
asked Jan 16 at 15:10
Maria MazurMaria Mazur
49.6k1361124
asked Jan 16 at 15:10
Maria MazurMaria Mazur
49.6k1361124
asked Jan 16 at 15:10
Maria MazurMaria Mazur
49.6k1361124
49.6k1361124
1
$begingroup$
A family $mathcal F$ of size $25$ would not quite be a Steiner system, as the number of subsets of ${1,dots,9}$ of size four contained in some element of $mathcal F$ would be $5cdot 25$, which is one less than $binom94=126$.
$endgroup$
– Mike Earnest
Jan 16 at 20:51
$begingroup$
You want $25$ five-element sets whose four-element subsets comprise all but one of the four element subsets of $[9]$. Consider the $120times 125$ matrix of 0's and 1's whose columns are indexed by four-element subset of $[9]$, except for ${1,2,3,4}$, and whose rows are indexed by five-element subsets of $[9]$, except for those who contain ${1,2,3,4}$. Then you want a subset of rows whose sum is the vector of $125$ ones, with a one where the row contains the column. This is solvable by Knuth's Algorithm X.
$endgroup$
– Mike Earnest
Jan 16 at 21:05
add a comment |
1
$begingroup$
A family $mathcal F$ of size $25$ would not quite be a Steiner system, as the number of subsets of ${1,dots,9}$ of size four contained in some element of $mathcal F$ would be $5cdot 25$, which is one less than $binom94=126$.
$endgroup$
– Mike Earnest
Jan 16 at 20:51
$begingroup$
You want $25$ five-element sets whose four-element subsets comprise all but one of the four element subsets of $[9]$. Consider the $120times 125$ matrix of 0's and 1's whose columns are indexed by four-element subset of $[9]$, except for ${1,2,3,4}$, and whose rows are indexed by five-element subsets of $[9]$, except for those who contain ${1,2,3,4}$. Then you want a subset of rows whose sum is the vector of $125$ ones, with a one where the row contains the column. This is solvable by Knuth's Algorithm X.
$endgroup$
– Mike Earnest
Jan 16 at 21:05
1
1
$begingroup$
A family $mathcal F$ of size $25$ would not quite be a Steiner system, as the number of subsets of ${1,dots,9}$ of size four contained in some element of $mathcal F$ would be $5cdot 25$, which is one less than $binom94=126$.
$endgroup$
– Mike Earnest
Jan 16 at 20:51
$begingroup$
A family $mathcal F$ of size $25$ would not quite be a Steiner system, as the number of subsets of ${1,dots,9}$ of size four contained in some element of $mathcal F$ would be $5cdot 25$, which is one less than $binom94=126$.
$endgroup$
– Mike Earnest
Jan 16 at 20:51
$begingroup$
You want $25$ five-element sets whose four-element subsets comprise all but one of the four element subsets of $[9]$. Consider the $120times 125$ matrix of 0's and 1's whose columns are indexed by four-element subset of $[9]$, except for ${1,2,3,4}$, and whose rows are indexed by five-element subsets of $[9]$, except for those who contain ${1,2,3,4}$. Then you want a subset of rows whose sum is the vector of $125$ ones, with a one where the row contains the column. This is solvable by Knuth's Algorithm X.
$endgroup$
– Mike Earnest
Jan 16 at 21:05
$begingroup$
You want $25$ five-element sets whose four-element subsets comprise all but one of the four element subsets of $[9]$. Consider the $120times 125$ matrix of 0's and 1's whose columns are indexed by four-element subset of $[9]$, except for ${1,2,3,4}$, and whose rows are indexed by five-element subsets of $[9]$, except for those who contain ${1,2,3,4}$. Then you want a subset of rows whose sum is the vector of $125$ ones, with a one where the row contains the column. This is solvable by Knuth's Algorithm X.
$endgroup$
– Mike Earnest
Jan 16 at 21:05
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Continuing the thread in my comment above, I did a computer search for a counterexample using this Python implementation of Algorithm X. I found no solutions. You can run the program yourself here. To help convince you I coded everything correctly, I used the same algorithm to find $S(5,6,12)$ by brute force. You can play with the code to see it find/not find $S(k-1,k,n)$ for other values of $k,n$, and verify this agrees with the (non)existence of Steiner $k$-tuple systems for your chosen $n$.
In short, I think $n_{text{min}}le 25$.
answered Jan 16 at 22:40
Mike EarnestMike Earnest
26.9k22152
$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%2f3075845%2flet-t-a-subset-1-2-ldots-9-a-5-find-n-min-if-for-a%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
$begingroup$
Continuing the thread in my comment above, I did a computer search for a counterexample using this Python implementation of Algorithm X. I found no solutions. You can run the program yourself here. To help convince you I coded everything correctly, I used the same algorithm to find $S(5,6,12)$ by brute force. You can play with the code to see it find/not find $S(k-1,k,n)$ for other values of $k,n$, and verify this agrees with the (non)existence of Steiner $k$-tuple systems for your chosen $n$.
In short, I think $n_{text{min}}le 25$.
answered Jan 16 at 22:40
Mike EarnestMike Earnest
26.9k22152
$endgroup$
add a comment |
$begingroup$
Continuing the thread in my comment above, I did a computer search for a counterexample using this Python implementation of Algorithm X. I found no solutions. You can run the program yourself here. To help convince you I coded everything correctly, I used the same algorithm to find $S(5,6,12)$ by brute force. You can play with the code to see it find/not find $S(k-1,k,n)$ for other values of $k,n$, and verify this agrees with the (non)existence of Steiner $k$-tuple systems for your chosen $n$.
In short, I think $n_{text{min}}le 25$.
answered Jan 16 at 22:40
Mike EarnestMike Earnest
26.9k22152
$endgroup$
add a comment |
$begingroup$
Continuing the thread in my comment above, I did a computer search for a counterexample using this Python implementation of Algorithm X. I found no solutions. You can run the program yourself here. To help convince you I coded everything correctly, I used the same algorithm to find $S(5,6,12)$ by brute force. You can play with the code to see it find/not find $S(k-1,k,n)$ for other values of $k,n$, and verify this agrees with the (non)existence of Steiner $k$-tuple systems for your chosen $n$.
In short, I think $n_{text{min}}le 25$.
answered Jan 16 at 22:40
Mike EarnestMike Earnest
26.9k22152
$endgroup$
Continuing the thread in my comment above, I did a computer search for a counterexample using this Python implementation of Algorithm X. I found no solutions. You can run the program yourself here. To help convince you I coded everything correctly, I used the same algorithm to find $S(5,6,12)$ by brute force. You can play with the code to see it find/not find $S(k-1,k,n)$ for other values of $k,n$, and verify this agrees with the (non)existence of Steiner $k$-tuple systems for your chosen $n$.
In short, I think $n_{text{min}}le 25$.
answered Jan 16 at 22:40
Mike EarnestMike Earnest
26.9k22152
edited Feb 11 at 20:52
answered Jan 16 at 22:40
Mike EarnestMike Earnest
26.9k22152
answered Jan 16 at 22:40
Mike EarnestMike Earnest
26.9k22152
answered Jan 16 at 22:40
Mike EarnestMike Earnest
26.9k22152
26.9k22152
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%2f3075845%2flet-t-a-subset-1-2-ldots-9-a-5-find-n-min-if-for-a%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
$begingroup$
A family $mathcal F$ of size $25$ would not quite be a Steiner system, as the number of subsets of ${1,dots,9}$ of size four contained in some element of $mathcal F$ would be $5cdot 25$, which is one less than $binom94=126$.
$endgroup$
– Mike Earnest
Jan 16 at 20:51
$begingroup$
You want $25$ five-element sets whose four-element subsets comprise all but one of the four element subsets of $[9]$. Consider the $120times 125$ matrix of 0's and 1's whose columns are indexed by four-element subset of $[9]$, except for ${1,2,3,4}$, and whose rows are indexed by five-element subsets of $[9]$, except for those who contain ${1,2,3,4}$. Then you want a subset of rows whose sum is the vector of $125$ ones, with a one where the row contains the column. This is solvable by Knuth's Algorithm X.
$endgroup$
– Mike Earnest
Jan 16 at 21:05