Mixing
Does Steiner system S(2,11, 1331) exist?
$begingroup$
Does the Steiner system $S(2,11,1331)$ exist?
I think it exists because $S(2, q, q^n)$ exists when $q$ is a prime power, $nge 2$. Confirmation will be very useful to me. A Steiner system forms a cover-free family where each block has at least one element not covered by the union of D other blocks.
I am working on topology transparent scheduling in wireless networks [1]. A schedule is a collection of time slots where a node can transmit. One can use Steiner systems to come up with such schedules. Basically, a block in a Steiner system defines a schedule. The cover-free property ensures existence of a conflict-free slot in a block where a node's transmission will not fail. The number of blocks equals the number of nodes N. But the problem is that we may not have Steiner systems for a given (N, D). We have to use some Steiner system that is close enough at the loss of some efficiency. In this context, I was looking for some Steiner systems.
For $S(2,11,1331)$, the number of blocks = $ b = vr/q$ where $v = 1331$, $q=11$, $r=(v-1)/(q-1)=133$ giving $b = 16093$.
- Colbourn, Charles J., Alan CH Ling, and Violet R. Syrotiuk. "Cover-free families and topology-transparent scheduling for MANETs." Designs, Codes and Cryptography 32.1-3 (2004): 65-95.
algebraic-topology combinatorial-designs
asked Jan 14 at 14:16
DKSDKS
162
$endgroup$
|
show 5 more comments
$begingroup$
Does the Steiner system $S(2,11,1331)$ exist?
I think it exists because $S(2, q, q^n)$ exists when $q$ is a prime power, $nge 2$. Confirmation will be very useful to me. A Steiner system forms a cover-free family where each block has at least one element not covered by the union of D other blocks.
I am working on topology transparent scheduling in wireless networks [1]. A schedule is a collection of time slots where a node can transmit. One can use Steiner systems to come up with such schedules. Basically, a block in a Steiner system defines a schedule. The cover-free property ensures existence of a conflict-free slot in a block where a node's transmission will not fail. The number of blocks equals the number of nodes N. But the problem is that we may not have Steiner systems for a given (N, D). We have to use some Steiner system that is close enough at the loss of some efficiency. In this context, I was looking for some Steiner systems.
For $S(2,11,1331)$, the number of blocks = $ b = vr/q$ where $v = 1331$, $q=11$, $r=(v-1)/(q-1)=133$ giving $b = 16093$.
- Colbourn, Charles J., Alan CH Ling, and Violet R. Syrotiuk. "Cover-free families and topology-transparent scheduling for MANETs." Designs, Codes and Cryptography 32.1-3 (2004): 65-95.
algebraic-topology combinatorial-designs
asked Jan 14 at 14:16
DKSDKS
162
$endgroup$
$begingroup$
You tagged this with algebraic-topology. I think we would all appreciate it if you shed a bit more light on the connection. Add the material to the question body, please (click the edit button under your question). It may feel unnecessary, but I see how some users think your question is a bit lacking in context. A few words about the connection would serve that need. See our guide for new askers for a more verbose explanation as to why we insist on such context (or just ask :-). Welcome to MSE. Hope you enjoy the site!
$endgroup$
– Jyrki Lahtonen
Jan 14 at 14:26
$begingroup$
I didn't check this page for sometime after posting the query yesterday. Hope I was able to describe the context well.
$endgroup$
– DKS
Jan 15 at 6:52
$begingroup$
Thanks, DKS. Voting to reopen.
$endgroup$
– Jyrki Lahtonen
Jan 15 at 8:29
1
$begingroup$
(cont'd) [2] U N Kar et al. "A Survey of Topology-Transparent Scheduling Schemes in Multi-Hop Packet Radio Networks". IEEE Communications Surveys & Tutorials. 2017 Jan 1;19(4):2026-49.
$endgroup$
– DKS
Jan 16 at 4:04
1
$begingroup$
(cont'd) But channel utilization should be computed with respect to the total number of slots. Since a node can use only one slot out of a total of $v$ slots in the frame, the avg. channel utilization per node = $1/v = 1/q^n$. Typically, $n=2$ but in my example above, $n=3$.
$endgroup$
– DKS
Jan 16 at 4:21
|
show 5 more comments
$begingroup$
Does the Steiner system $S(2,11,1331)$ exist?
I think it exists because $S(2, q, q^n)$ exists when $q$ is a prime power, $nge 2$. Confirmation will be very useful to me. A Steiner system forms a cover-free family where each block has at least one element not covered by the union of D other blocks.
I am working on topology transparent scheduling in wireless networks [1]. A schedule is a collection of time slots where a node can transmit. One can use Steiner systems to come up with such schedules. Basically, a block in a Steiner system defines a schedule. The cover-free property ensures existence of a conflict-free slot in a block where a node's transmission will not fail. The number of blocks equals the number of nodes N. But the problem is that we may not have Steiner systems for a given (N, D). We have to use some Steiner system that is close enough at the loss of some efficiency. In this context, I was looking for some Steiner systems.
For $S(2,11,1331)$, the number of blocks = $ b = vr/q$ where $v = 1331$, $q=11$, $r=(v-1)/(q-1)=133$ giving $b = 16093$.
- Colbourn, Charles J., Alan CH Ling, and Violet R. Syrotiuk. "Cover-free families and topology-transparent scheduling for MANETs." Designs, Codes and Cryptography 32.1-3 (2004): 65-95.
algebraic-topology combinatorial-designs
asked Jan 14 at 14:16
DKSDKS
162
$endgroup$
Does the Steiner system $S(2,11,1331)$ exist?
I think it exists because $S(2, q, q^n)$ exists when $q$ is a prime power, $nge 2$. Confirmation will be very useful to me. A Steiner system forms a cover-free family where each block has at least one element not covered by the union of D other blocks.
I am working on topology transparent scheduling in wireless networks [1]. A schedule is a collection of time slots where a node can transmit. One can use Steiner systems to come up with such schedules. Basically, a block in a Steiner system defines a schedule. The cover-free property ensures existence of a conflict-free slot in a block where a node's transmission will not fail. The number of blocks equals the number of nodes N. But the problem is that we may not have Steiner systems for a given (N, D). We have to use some Steiner system that is close enough at the loss of some efficiency. In this context, I was looking for some Steiner systems.
For $S(2,11,1331)$, the number of blocks = $ b = vr/q$ where $v = 1331$, $q=11$, $r=(v-1)/(q-1)=133$ giving $b = 16093$.
- Colbourn, Charles J., Alan CH Ling, and Violet R. Syrotiuk. "Cover-free families and topology-transparent scheduling for MANETs." Designs, Codes and Cryptography 32.1-3 (2004): 65-95.
algebraic-topology combinatorial-designs
algebraic-topology combinatorial-designs
asked Jan 14 at 14:16
DKSDKS
162
asked Jan 14 at 14:16
DKSDKS
162
edited Jan 15 at 6:55
DKS
asked Jan 14 at 14:16
DKSDKS
162
asked Jan 14 at 14:16
DKSDKS
162
asked Jan 14 at 14:16
DKSDKS
162
162
$begingroup$
You tagged this with algebraic-topology. I think we would all appreciate it if you shed a bit more light on the connection. Add the material to the question body, please (click the edit button under your question). It may feel unnecessary, but I see how some users think your question is a bit lacking in context. A few words about the connection would serve that need. See our guide for new askers for a more verbose explanation as to why we insist on such context (or just ask :-). Welcome to MSE. Hope you enjoy the site!
$endgroup$
– Jyrki Lahtonen
Jan 14 at 14:26
$begingroup$
I didn't check this page for sometime after posting the query yesterday. Hope I was able to describe the context well.
$endgroup$
– DKS
Jan 15 at 6:52
$begingroup$
Thanks, DKS. Voting to reopen.
$endgroup$
– Jyrki Lahtonen
Jan 15 at 8:29
1
$begingroup$
(cont'd) [2] U N Kar et al. "A Survey of Topology-Transparent Scheduling Schemes in Multi-Hop Packet Radio Networks". IEEE Communications Surveys & Tutorials. 2017 Jan 1;19(4):2026-49.
$endgroup$
– DKS
Jan 16 at 4:04
1
$begingroup$
(cont'd) But channel utilization should be computed with respect to the total number of slots. Since a node can use only one slot out of a total of $v$ slots in the frame, the avg. channel utilization per node = $1/v = 1/q^n$. Typically, $n=2$ but in my example above, $n=3$.
$endgroup$
– DKS
Jan 16 at 4:21
|
show 5 more comments
$begingroup$
You tagged this with algebraic-topology. I think we would all appreciate it if you shed a bit more light on the connection. Add the material to the question body, please (click the edit button under your question). It may feel unnecessary, but I see how some users think your question is a bit lacking in context. A few words about the connection would serve that need. See our guide for new askers for a more verbose explanation as to why we insist on such context (or just ask :-). Welcome to MSE. Hope you enjoy the site!
$endgroup$
– Jyrki Lahtonen
Jan 14 at 14:26
$begingroup$
I didn't check this page for sometime after posting the query yesterday. Hope I was able to describe the context well.
$endgroup$
– DKS
Jan 15 at 6:52
$begingroup$
Thanks, DKS. Voting to reopen.
$endgroup$
– Jyrki Lahtonen
Jan 15 at 8:29
1
$begingroup$
(cont'd) [2] U N Kar et al. "A Survey of Topology-Transparent Scheduling Schemes in Multi-Hop Packet Radio Networks". IEEE Communications Surveys & Tutorials. 2017 Jan 1;19(4):2026-49.
$endgroup$
– DKS
Jan 16 at 4:04
1
$begingroup$
(cont'd) But channel utilization should be computed with respect to the total number of slots. Since a node can use only one slot out of a total of $v$ slots in the frame, the avg. channel utilization per node = $1/v = 1/q^n$. Typically, $n=2$ but in my example above, $n=3$.
$endgroup$
– DKS
Jan 16 at 4:21
$begingroup$
You tagged this with algebraic-topology. I think we would all appreciate it if you shed a bit more light on the connection. Add the material to the question body, please (click the edit button under your question). It may feel unnecessary, but I see how some users think your question is a bit lacking in context. A few words about the connection would serve that need. See our guide for new askers for a more verbose explanation as to why we insist on such context (or just ask :-). Welcome to MSE. Hope you enjoy the site!
$endgroup$
– Jyrki Lahtonen
Jan 14 at 14:26
$begingroup$
You tagged this with algebraic-topology. I think we would all appreciate it if you shed a bit more light on the connection. Add the material to the question body, please (click the edit button under your question). It may feel unnecessary, but I see how some users think your question is a bit lacking in context. A few words about the connection would serve that need. See our guide for new askers for a more verbose explanation as to why we insist on such context (or just ask :-). Welcome to MSE. Hope you enjoy the site!
$endgroup$
– Jyrki Lahtonen
Jan 14 at 14:26
$begingroup$
I didn't check this page for sometime after posting the query yesterday. Hope I was able to describe the context well.
$endgroup$
– DKS
Jan 15 at 6:52
$begingroup$
I didn't check this page for sometime after posting the query yesterday. Hope I was able to describe the context well.
$endgroup$
– DKS
Jan 15 at 6:52
$begingroup$
Thanks, DKS. Voting to reopen.
$endgroup$
– Jyrki Lahtonen
Jan 15 at 8:29
$begingroup$
Thanks, DKS. Voting to reopen.
$endgroup$
– Jyrki Lahtonen
Jan 15 at 8:29
1
1
$begingroup$
(cont'd) [2] U N Kar et al. "A Survey of Topology-Transparent Scheduling Schemes in Multi-Hop Packet Radio Networks". IEEE Communications Surveys & Tutorials. 2017 Jan 1;19(4):2026-49.
$endgroup$
– DKS
Jan 16 at 4:04
$begingroup$
(cont'd) [2] U N Kar et al. "A Survey of Topology-Transparent Scheduling Schemes in Multi-Hop Packet Radio Networks". IEEE Communications Surveys & Tutorials. 2017 Jan 1;19(4):2026-49.
$endgroup$
– DKS
Jan 16 at 4:04
1
1
$begingroup$
(cont'd) But channel utilization should be computed with respect to the total number of slots. Since a node can use only one slot out of a total of $v$ slots in the frame, the avg. channel utilization per node = $1/v = 1/q^n$. Typically, $n=2$ but in my example above, $n=3$.
$endgroup$
– DKS
Jan 16 at 4:21
$begingroup$
(cont'd) But channel utilization should be computed with respect to the total number of slots. Since a node can use only one slot out of a total of $v$ slots in the frame, the avg. channel utilization per node = $1/v = 1/q^n$. Typically, $n=2$ but in my example above, $n=3$.
$endgroup$
– DKS
Jan 16 at 4:21
|
show 5 more comments
1 Answer
1
active
oldest
votes
$begingroup$
Yes, it exists. Consider a 3-dimensional space $V$ over the field $K=Bbb{F}_{11}$. There are $11^3=1331$ points in $V$. Any two points in $V$ determine a unique line (= a coset of a 1-dimensional subspace). The collection of all the lines in $V$ is thus the desired Steiner system.
answered Jan 14 at 14:20
Jyrki LahtonenJyrki Lahtonen
109k13169372
$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%2f3073268%2fdoes-steiner-system-s2-11-1331-exist%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$
Yes, it exists. Consider a 3-dimensional space $V$ over the field $K=Bbb{F}_{11}$. There are $11^3=1331$ points in $V$. Any two points in $V$ determine a unique line (= a coset of a 1-dimensional subspace). The collection of all the lines in $V$ is thus the desired Steiner system.
answered Jan 14 at 14:20
Jyrki LahtonenJyrki Lahtonen
109k13169372
$endgroup$
add a comment |
$begingroup$
Yes, it exists. Consider a 3-dimensional space $V$ over the field $K=Bbb{F}_{11}$. There are $11^3=1331$ points in $V$. Any two points in $V$ determine a unique line (= a coset of a 1-dimensional subspace). The collection of all the lines in $V$ is thus the desired Steiner system.
answered Jan 14 at 14:20
Jyrki LahtonenJyrki Lahtonen
109k13169372
$endgroup$
add a comment |
$begingroup$
Yes, it exists. Consider a 3-dimensional space $V$ over the field $K=Bbb{F}_{11}$. There are $11^3=1331$ points in $V$. Any two points in $V$ determine a unique line (= a coset of a 1-dimensional subspace). The collection of all the lines in $V$ is thus the desired Steiner system.
answered Jan 14 at 14:20
Jyrki LahtonenJyrki Lahtonen
109k13169372
$endgroup$
Yes, it exists. Consider a 3-dimensional space $V$ over the field $K=Bbb{F}_{11}$. There are $11^3=1331$ points in $V$. Any two points in $V$ determine a unique line (= a coset of a 1-dimensional subspace). The collection of all the lines in $V$ is thus the desired Steiner system.
answered Jan 14 at 14:20
Jyrki LahtonenJyrki Lahtonen
109k13169372
edited Jan 14 at 14:27
answered Jan 14 at 14:20
Jyrki LahtonenJyrki Lahtonen
109k13169372
answered Jan 14 at 14:20
Jyrki LahtonenJyrki Lahtonen
109k13169372
answered Jan 14 at 14:20
Jyrki LahtonenJyrki Lahtonen
109k13169372
109k13169372
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%2f3073268%2fdoes-steiner-system-s2-11-1331-exist%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
$begingroup$
You tagged this with algebraic-topology. I think we would all appreciate it if you shed a bit more light on the connection. Add the material to the question body, please (click the edit button under your question). It may feel unnecessary, but I see how some users think your question is a bit lacking in context. A few words about the connection would serve that need. See our guide for new askers for a more verbose explanation as to why we insist on such context (or just ask :-). Welcome to MSE. Hope you enjoy the site!
$endgroup$
– Jyrki Lahtonen
Jan 14 at 14:26
$begingroup$
I didn't check this page for sometime after posting the query yesterday. Hope I was able to describe the context well.
$endgroup$
– DKS
Jan 15 at 6:52
$begingroup$
Thanks, DKS. Voting to reopen.
$endgroup$
– Jyrki Lahtonen
Jan 15 at 8:29
1
$begingroup$
(cont'd) [2] U N Kar et al. "A Survey of Topology-Transparent Scheduling Schemes in Multi-Hop Packet Radio Networks". IEEE Communications Surveys & Tutorials. 2017 Jan 1;19(4):2026-49.
$endgroup$
– DKS
Jan 16 at 4:04
1
$begingroup$
(cont'd) But channel utilization should be computed with respect to the total number of slots. Since a node can use only one slot out of a total of $v$ slots in the frame, the avg. channel utilization per node = $1/v = 1/q^n$. Typically, $n=2$ but in my example above, $n=3$.
$endgroup$
– DKS
Jan 16 at 4:21