Count the number of sets of subsets of (Steiner?) triples
$begingroup$
Given a set of $v$ numbers. Fix $v$. How many sets of $v$ sorted triples can be created, matching the following conditions:
- two triples shall have at most one number in common
- over all triples each number shall appear three times?
A representative example set of triples with $v=8$:
$$
S_A=(color{red}1,color{blue}2,color{green}5);;;S_B=(color{blue}2,color{grey}3,color{purple}6);;;S_C=(color{grey}3,color{pink}4,color{orange}7);;;S_D=(color{red}1,color{pink}4,8)
$$
$$
S_E=(color{blue}2,color{orange}7,8);;;S_F=(color{grey}3,color{green}5,8);;;S_G=(color{pink}4,color{green}5,color{purple}6);;;S_H=(color{red}1,color{purple}6,color{orange}7)
$$
Can this be seen as $(v, b, r, k, λ)$ block designs? When I read the definition there I find:
$v(=8)$: points, number of elements of X
$b(=8)$: number of blocks
$r(=3)$: number of blocks containing a given point
$k(=3)$: number of points in a block
$lambda(=1)$: number of blocks containing any 2 distinct points
But obviously this doesn't fulfill the condition ${displaystyle lambda (v-1)=r(k-1)}$...
UPDATE My example looks like a subset of elements of the Steiner Triple System $STS(9)$, where subsets that contain $9$ are omitted.
The question is motivated by bipartite cubic graphs. Bipartiteness forces $v=b$, cubicity asks for $r=k=3$. $lambda =1 $ means that the graph is simple and has no squares.
The example above is derived from the graph shown here. It has 6 octagons leaving on a double torus. Black points are labelled with numbers $1$ to $6$; white points are labelled with characters $A$ to $H$.
combinatorics algebraic-graph-theory combinatorial-designs
asked Jan 8 at 6:29
draks ...draks ...
11.5k644129
$endgroup$
This question has an open bounty worth +50
reputation from draks ... ending in 2 days.
This question has not received enough attention.
add a comment |
$begingroup$
Given a set of $v$ numbers. Fix $v$. How many sets of $v$ sorted triples can be created, matching the following conditions:
- two triples shall have at most one number in common
- over all triples each number shall appear three times?
A representative example set of triples with $v=8$:
$$
S_A=(color{red}1,color{blue}2,color{green}5);;;S_B=(color{blue}2,color{grey}3,color{purple}6);;;S_C=(color{grey}3,color{pink}4,color{orange}7);;;S_D=(color{red}1,color{pink}4,8)
$$
$$
S_E=(color{blue}2,color{orange}7,8);;;S_F=(color{grey}3,color{green}5,8);;;S_G=(color{pink}4,color{green}5,color{purple}6);;;S_H=(color{red}1,color{purple}6,color{orange}7)
$$
Can this be seen as $(v, b, r, k, λ)$ block designs? When I read the definition there I find:
$v(=8)$: points, number of elements of X
$b(=8)$: number of blocks
$r(=3)$: number of blocks containing a given point
$k(=3)$: number of points in a block
$lambda(=1)$: number of blocks containing any 2 distinct points
But obviously this doesn't fulfill the condition ${displaystyle lambda (v-1)=r(k-1)}$...
UPDATE My example looks like a subset of elements of the Steiner Triple System $STS(9)$, where subsets that contain $9$ are omitted.
The question is motivated by bipartite cubic graphs. Bipartiteness forces $v=b$, cubicity asks for $r=k=3$. $lambda =1 $ means that the graph is simple and has no squares.
The example above is derived from the graph shown here. It has 6 octagons leaving on a double torus. Black points are labelled with numbers $1$ to $6$; white points are labelled with characters $A$ to $H$.
combinatorics algebraic-graph-theory combinatorial-designs
asked Jan 8 at 6:29
draks ...draks ...
11.5k644129
$endgroup$
This question has an open bounty worth +50
reputation from draks ... ending in 2 days.
This question has not received enough attention.
1
$begingroup$
Your definition is not equivalent to having a $lambda=1$ in the design sense. Having $lambda = 1$ would mean every pair of points would be contained in a unique block, in your example you have every pair of points contained in at most one block. I think this would sometimes be referred to as a partial design, or a $(v,v,3,3,{0,1})$ partial design.
$endgroup$
– Morgan Rodgers
Jan 11 at 17:05
$begingroup$
I think it is unlikely that there will be an exact formula for this based in terms of $v$, you would probably need to do an exhaustive computer search for each case.
$endgroup$
– Morgan Rodgers
Jan 11 at 17:09
$begingroup$
@MorganRodgers partial design, I'll check that, thanks ...
$endgroup$
– draks ...
2 days ago
add a comment |
$begingroup$
Given a set of $v$ numbers. Fix $v$. How many sets of $v$ sorted triples can be created, matching the following conditions:
- two triples shall have at most one number in common
- over all triples each number shall appear three times?
A representative example set of triples with $v=8$:
$$
S_A=(color{red}1,color{blue}2,color{green}5);;;S_B=(color{blue}2,color{grey}3,color{purple}6);;;S_C=(color{grey}3,color{pink}4,color{orange}7);;;S_D=(color{red}1,color{pink}4,8)
$$
$$
S_E=(color{blue}2,color{orange}7,8);;;S_F=(color{grey}3,color{green}5,8);;;S_G=(color{pink}4,color{green}5,color{purple}6);;;S_H=(color{red}1,color{purple}6,color{orange}7)
$$
Can this be seen as $(v, b, r, k, λ)$ block designs? When I read the definition there I find:
$v(=8)$: points, number of elements of X
$b(=8)$: number of blocks
$r(=3)$: number of blocks containing a given point
$k(=3)$: number of points in a block
$lambda(=1)$: number of blocks containing any 2 distinct points
But obviously this doesn't fulfill the condition ${displaystyle lambda (v-1)=r(k-1)}$...
UPDATE My example looks like a subset of elements of the Steiner Triple System $STS(9)$, where subsets that contain $9$ are omitted.
The question is motivated by bipartite cubic graphs. Bipartiteness forces $v=b$, cubicity asks for $r=k=3$. $lambda =1 $ means that the graph is simple and has no squares.
The example above is derived from the graph shown here. It has 6 octagons leaving on a double torus. Black points are labelled with numbers $1$ to $6$; white points are labelled with characters $A$ to $H$.
combinatorics algebraic-graph-theory combinatorial-designs
asked Jan 8 at 6:29
draks ...draks ...
11.5k644129
$endgroup$
Given a set of $v$ numbers. Fix $v$. How many sets of $v$ sorted triples can be created, matching the following conditions:
- two triples shall have at most one number in common
- over all triples each number shall appear three times?
A representative example set of triples with $v=8$:
$$
S_A=(color{red}1,color{blue}2,color{green}5);;;S_B=(color{blue}2,color{grey}3,color{purple}6);;;S_C=(color{grey}3,color{pink}4,color{orange}7);;;S_D=(color{red}1,color{pink}4,8)
$$
$$
S_E=(color{blue}2,color{orange}7,8);;;S_F=(color{grey}3,color{green}5,8);;;S_G=(color{pink}4,color{green}5,color{purple}6);;;S_H=(color{red}1,color{purple}6,color{orange}7)
$$
Can this be seen as $(v, b, r, k, λ)$ block designs? When I read the definition there I find:
$v(=8)$: points, number of elements of X
$b(=8)$: number of blocks
$r(=3)$: number of blocks containing a given point
$k(=3)$: number of points in a block
$lambda(=1)$: number of blocks containing any 2 distinct points
But obviously this doesn't fulfill the condition ${displaystyle lambda (v-1)=r(k-1)}$...
UPDATE My example looks like a subset of elements of the Steiner Triple System $STS(9)$, where subsets that contain $9$ are omitted.
The question is motivated by bipartite cubic graphs. Bipartiteness forces $v=b$, cubicity asks for $r=k=3$. $lambda =1 $ means that the graph is simple and has no squares.
The example above is derived from the graph shown here. It has 6 octagons leaving on a double torus. Black points are labelled with numbers $1$ to $6$; white points are labelled with characters $A$ to $H$.
combinatorics algebraic-graph-theory combinatorial-designs
combinatorics algebraic-graph-theory combinatorial-designs
asked Jan 8 at 6:29
draks ...draks ...
11.5k644129
asked Jan 8 at 6:29
draks ...draks ...
11.5k644129
edited Jan 10 at 10:16
draks ...
asked Jan 8 at 6:29
draks ...draks ...
11.5k644129
asked Jan 8 at 6:29
draks ...draks ...
11.5k644129
asked Jan 8 at 6:29
draks ...draks ...
11.5k644129
11.5k644129
This question has an open bounty worth +50
reputation from draks ... ending in 2 days.
This question has not received enough attention.
This question has an open bounty worth +50
reputation from draks ... ending in 2 days.
This question has not received enough attention.
1
$begingroup$
Your definition is not equivalent to having a $lambda=1$ in the design sense. Having $lambda = 1$ would mean every pair of points would be contained in a unique block, in your example you have every pair of points contained in at most one block. I think this would sometimes be referred to as a partial design, or a $(v,v,3,3,{0,1})$ partial design.
$endgroup$
– Morgan Rodgers
Jan 11 at 17:05
$begingroup$
I think it is unlikely that there will be an exact formula for this based in terms of $v$, you would probably need to do an exhaustive computer search for each case.
$endgroup$
– Morgan Rodgers
Jan 11 at 17:09
$begingroup$
@MorganRodgers partial design, I'll check that, thanks ...
$endgroup$
– draks ...
2 days ago
add a comment |
1
$begingroup$
Your definition is not equivalent to having a $lambda=1$ in the design sense. Having $lambda = 1$ would mean every pair of points would be contained in a unique block, in your example you have every pair of points contained in at most one block. I think this would sometimes be referred to as a partial design, or a $(v,v,3,3,{0,1})$ partial design.
$endgroup$
– Morgan Rodgers
Jan 11 at 17:05
$begingroup$
I think it is unlikely that there will be an exact formula for this based in terms of $v$, you would probably need to do an exhaustive computer search for each case.
$endgroup$
– Morgan Rodgers
Jan 11 at 17:09
$begingroup$
@MorganRodgers partial design, I'll check that, thanks ...
$endgroup$
– draks ...
2 days ago
1
1
$begingroup$
Your definition is not equivalent to having a $lambda=1$ in the design sense. Having $lambda = 1$ would mean every pair of points would be contained in a unique block, in your example you have every pair of points contained in at most one block. I think this would sometimes be referred to as a partial design, or a $(v,v,3,3,{0,1})$ partial design.
$endgroup$
– Morgan Rodgers
Jan 11 at 17:05
$begingroup$
Your definition is not equivalent to having a $lambda=1$ in the design sense. Having $lambda = 1$ would mean every pair of points would be contained in a unique block, in your example you have every pair of points contained in at most one block. I think this would sometimes be referred to as a partial design, or a $(v,v,3,3,{0,1})$ partial design.
$endgroup$
– Morgan Rodgers
Jan 11 at 17:05
$begingroup$
I think it is unlikely that there will be an exact formula for this based in terms of $v$, you would probably need to do an exhaustive computer search for each case.
$endgroup$
– Morgan Rodgers
Jan 11 at 17:09
$begingroup$
I think it is unlikely that there will be an exact formula for this based in terms of $v$, you would probably need to do an exhaustive computer search for each case.
$endgroup$
– Morgan Rodgers
Jan 11 at 17:09
$begingroup$
@MorganRodgers partial design, I'll check that, thanks ...
$endgroup$
– draks ...
2 days ago
$begingroup$
@MorganRodgers partial design, I'll check that, thanks ...
$endgroup$
– draks ...
2 days ago
add a comment |
0
active
oldest
votes
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%2f3065865%2fcount-the-number-of-sets-of-subsets-of-steiner-triples%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3065865%2fcount-the-number-of-sets-of-subsets-of-steiner-triples%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$
Your definition is not equivalent to having a $lambda=1$ in the design sense. Having $lambda = 1$ would mean every pair of points would be contained in a unique block, in your example you have every pair of points contained in at most one block. I think this would sometimes be referred to as a partial design, or a $(v,v,3,3,{0,1})$ partial design.
$endgroup$
– Morgan Rodgers
Jan 11 at 17:05
$begingroup$
I think it is unlikely that there will be an exact formula for this based in terms of $v$, you would probably need to do an exhaustive computer search for each case.
$endgroup$
– Morgan Rodgers
Jan 11 at 17:09
$begingroup$
@MorganRodgers partial design, I'll check that, thanks ...
$endgroup$
– draks ...
2 days ago