Dominating sets in tournaments; is $2^{n+1}-2$ tight?
$begingroup$
A tournement is a directed graph such that for every pair of distinct vertices ${x,y}$, there is either an edge from $x$ to $y$ or from $y$ to $x$, but not both. I will use "$xto y$" to mean "there is an edge from $x$ to $y$."
A dominating set of a directed graph is a subset $S$ of vertices such that for every $tnotin S$, there exists $sin S$ so $sto t$.
It can be shown$^*$ that every tournament on $2^{n+1}-2$ vertices has a dominating set of size $n$. My question is whether this result is tight.
Does there exist a tournament on $2^{n+1}-1$ vertices with no dominating set of size $n$?
If not, what is the smallest tournament with no dominating set of size $n$?
My thoughts:
A necessary condition for a graph on $2^{n+1}-1$ vertices with no dominating set of size $n$ is that every vertex must have an out-degree of exactly $2^n-1$, so exactly half of its edges are outgoing.
The answer is yes when $n=1,2$.
- The "rock-paper-scissors" graph on three vertices has no dominating set of size $1$.
- The graph on $mathbb Z/7mathbb Z$ where each $x$ has directed edges to $x+1,x+2$ and $x+4pmod7$ has no dominating set of size $2$.
For $nge 3$, the possibilities get too large, and I cannot come up with a clever solution. Can anyone see a pattern?
I came up with this problem while thinking about this puzzle.
$^*$Consider a vertex $s$ with maximal out-degree. By the hand-shaking lemma, this degree must be at least $(2^{n+1}-3)/2$, so at least $2^n-1$. Include $s$ in $S$, then ignore $s$ and the vertices $t$ for which $sto t$. What remains is tournament of size $(2^{n+1}-2)-1-(2^{n}-1)=2^n-2$. Proceed by induction.
combinatorics discrete-mathematics graph-theory directed-graphs extremal-graph-theory
asked Jan 8 at 22:06
Mike EarnestMike Earnest
26.7k22151
$endgroup$
add a comment |
$begingroup$
A tournement is a directed graph such that for every pair of distinct vertices ${x,y}$, there is either an edge from $x$ to $y$ or from $y$ to $x$, but not both. I will use "$xto y$" to mean "there is an edge from $x$ to $y$."
A dominating set of a directed graph is a subset $S$ of vertices such that for every $tnotin S$, there exists $sin S$ so $sto t$.
It can be shown$^*$ that every tournament on $2^{n+1}-2$ vertices has a dominating set of size $n$. My question is whether this result is tight.
Does there exist a tournament on $2^{n+1}-1$ vertices with no dominating set of size $n$?
If not, what is the smallest tournament with no dominating set of size $n$?
My thoughts:
A necessary condition for a graph on $2^{n+1}-1$ vertices with no dominating set of size $n$ is that every vertex must have an out-degree of exactly $2^n-1$, so exactly half of its edges are outgoing.
The answer is yes when $n=1,2$.
- The "rock-paper-scissors" graph on three vertices has no dominating set of size $1$.
- The graph on $mathbb Z/7mathbb Z$ where each $x$ has directed edges to $x+1,x+2$ and $x+4pmod7$ has no dominating set of size $2$.
For $nge 3$, the possibilities get too large, and I cannot come up with a clever solution. Can anyone see a pattern?
I came up with this problem while thinking about this puzzle.
$^*$Consider a vertex $s$ with maximal out-degree. By the hand-shaking lemma, this degree must be at least $(2^{n+1}-3)/2$, so at least $2^n-1$. Include $s$ in $S$, then ignore $s$ and the vertices $t$ for which $sto t$. What remains is tournament of size $(2^{n+1}-2)-1-(2^{n}-1)=2^n-2$. Proceed by induction.
combinatorics discrete-mathematics graph-theory directed-graphs extremal-graph-theory
asked Jan 8 at 22:06
Mike EarnestMike Earnest
26.7k22151
$endgroup$
add a comment |
$begingroup$
A tournement is a directed graph such that for every pair of distinct vertices ${x,y}$, there is either an edge from $x$ to $y$ or from $y$ to $x$, but not both. I will use "$xto y$" to mean "there is an edge from $x$ to $y$."
A dominating set of a directed graph is a subset $S$ of vertices such that for every $tnotin S$, there exists $sin S$ so $sto t$.
It can be shown$^*$ that every tournament on $2^{n+1}-2$ vertices has a dominating set of size $n$. My question is whether this result is tight.
Does there exist a tournament on $2^{n+1}-1$ vertices with no dominating set of size $n$?
If not, what is the smallest tournament with no dominating set of size $n$?
My thoughts:
A necessary condition for a graph on $2^{n+1}-1$ vertices with no dominating set of size $n$ is that every vertex must have an out-degree of exactly $2^n-1$, so exactly half of its edges are outgoing.
The answer is yes when $n=1,2$.
- The "rock-paper-scissors" graph on three vertices has no dominating set of size $1$.
- The graph on $mathbb Z/7mathbb Z$ where each $x$ has directed edges to $x+1,x+2$ and $x+4pmod7$ has no dominating set of size $2$.
For $nge 3$, the possibilities get too large, and I cannot come up with a clever solution. Can anyone see a pattern?
I came up with this problem while thinking about this puzzle.
$^*$Consider a vertex $s$ with maximal out-degree. By the hand-shaking lemma, this degree must be at least $(2^{n+1}-3)/2$, so at least $2^n-1$. Include $s$ in $S$, then ignore $s$ and the vertices $t$ for which $sto t$. What remains is tournament of size $(2^{n+1}-2)-1-(2^{n}-1)=2^n-2$. Proceed by induction.
combinatorics discrete-mathematics graph-theory directed-graphs extremal-graph-theory
asked Jan 8 at 22:06
Mike EarnestMike Earnest
26.7k22151
$endgroup$
A tournement is a directed graph such that for every pair of distinct vertices ${x,y}$, there is either an edge from $x$ to $y$ or from $y$ to $x$, but not both. I will use "$xto y$" to mean "there is an edge from $x$ to $y$."
A dominating set of a directed graph is a subset $S$ of vertices such that for every $tnotin S$, there exists $sin S$ so $sto t$.
It can be shown$^*$ that every tournament on $2^{n+1}-2$ vertices has a dominating set of size $n$. My question is whether this result is tight.
Does there exist a tournament on $2^{n+1}-1$ vertices with no dominating set of size $n$?
If not, what is the smallest tournament with no dominating set of size $n$?
My thoughts:
A necessary condition for a graph on $2^{n+1}-1$ vertices with no dominating set of size $n$ is that every vertex must have an out-degree of exactly $2^n-1$, so exactly half of its edges are outgoing.
The answer is yes when $n=1,2$.
- The "rock-paper-scissors" graph on three vertices has no dominating set of size $1$.
- The graph on $mathbb Z/7mathbb Z$ where each $x$ has directed edges to $x+1,x+2$ and $x+4pmod7$ has no dominating set of size $2$.
For $nge 3$, the possibilities get too large, and I cannot come up with a clever solution. Can anyone see a pattern?
I came up with this problem while thinking about this puzzle.
$^*$Consider a vertex $s$ with maximal out-degree. By the hand-shaking lemma, this degree must be at least $(2^{n+1}-3)/2$, so at least $2^n-1$. Include $s$ in $S$, then ignore $s$ and the vertices $t$ for which $sto t$. What remains is tournament of size $(2^{n+1}-2)-1-(2^{n}-1)=2^n-2$. Proceed by induction.
combinatorics discrete-mathematics graph-theory directed-graphs extremal-graph-theory
combinatorics discrete-mathematics graph-theory directed-graphs extremal-graph-theory
asked Jan 8 at 22:06
Mike EarnestMike Earnest
26.7k22151
asked Jan 8 at 22:06
Mike EarnestMike Earnest
26.7k22151
edited Jan 8 at 23:00
Mike Earnest
asked Jan 8 at 22:06
Mike EarnestMike Earnest
26.7k22151
asked Jan 8 at 22:06
Mike EarnestMike Earnest
26.7k22151
asked Jan 8 at 22:06
Mike EarnestMike Earnest
26.7k22151
26.7k22151
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The answer to your question is yes: if $f(n)$ is the least number of vertices in a tournament with no $n$-vertex dominating set, then $f(n) > 2^{n+1}-1$ for large $n$ and in general we know
$$
(n+2) 2^{n-1} - 1 le f(n) le C cdot n^2 cdot 2^n
$$
for some constant $C$. Already for $n=3$ there is a $19$-vertex tournament with no dominating set of size $3$: the quadratic residue tournament mod $19$. (Here, we have an edge from $i$ to $j$ if there is some $k$ such that $i + k^2 equiv j pmod{19}$; it is a generalization of your $7$-vertex construction.)
(For more details, see for example this paper by Szekeres and Szekeres.)
answered Jan 8 at 23:37
Misha LavrovMisha Lavrov
48.1k657107
$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%2f3066793%2fdominating-sets-in-tournaments-is-2n1-2-tight%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$
The answer to your question is yes: if $f(n)$ is the least number of vertices in a tournament with no $n$-vertex dominating set, then $f(n) > 2^{n+1}-1$ for large $n$ and in general we know
$$
(n+2) 2^{n-1} - 1 le f(n) le C cdot n^2 cdot 2^n
$$
for some constant $C$. Already for $n=3$ there is a $19$-vertex tournament with no dominating set of size $3$: the quadratic residue tournament mod $19$. (Here, we have an edge from $i$ to $j$ if there is some $k$ such that $i + k^2 equiv j pmod{19}$; it is a generalization of your $7$-vertex construction.)
(For more details, see for example this paper by Szekeres and Szekeres.)
answered Jan 8 at 23:37
Misha LavrovMisha Lavrov
48.1k657107
$endgroup$
add a comment |
$begingroup$
The answer to your question is yes: if $f(n)$ is the least number of vertices in a tournament with no $n$-vertex dominating set, then $f(n) > 2^{n+1}-1$ for large $n$ and in general we know
$$
(n+2) 2^{n-1} - 1 le f(n) le C cdot n^2 cdot 2^n
$$
for some constant $C$. Already for $n=3$ there is a $19$-vertex tournament with no dominating set of size $3$: the quadratic residue tournament mod $19$. (Here, we have an edge from $i$ to $j$ if there is some $k$ such that $i + k^2 equiv j pmod{19}$; it is a generalization of your $7$-vertex construction.)
(For more details, see for example this paper by Szekeres and Szekeres.)
answered Jan 8 at 23:37
Misha LavrovMisha Lavrov
48.1k657107
$endgroup$
add a comment |
$begingroup$
The answer to your question is yes: if $f(n)$ is the least number of vertices in a tournament with no $n$-vertex dominating set, then $f(n) > 2^{n+1}-1$ for large $n$ and in general we know
$$
(n+2) 2^{n-1} - 1 le f(n) le C cdot n^2 cdot 2^n
$$
for some constant $C$. Already for $n=3$ there is a $19$-vertex tournament with no dominating set of size $3$: the quadratic residue tournament mod $19$. (Here, we have an edge from $i$ to $j$ if there is some $k$ such that $i + k^2 equiv j pmod{19}$; it is a generalization of your $7$-vertex construction.)
(For more details, see for example this paper by Szekeres and Szekeres.)
answered Jan 8 at 23:37
Misha LavrovMisha Lavrov
48.1k657107
$endgroup$
The answer to your question is yes: if $f(n)$ is the least number of vertices in a tournament with no $n$-vertex dominating set, then $f(n) > 2^{n+1}-1$ for large $n$ and in general we know
$$
(n+2) 2^{n-1} - 1 le f(n) le C cdot n^2 cdot 2^n
$$
for some constant $C$. Already for $n=3$ there is a $19$-vertex tournament with no dominating set of size $3$: the quadratic residue tournament mod $19$. (Here, we have an edge from $i$ to $j$ if there is some $k$ such that $i + k^2 equiv j pmod{19}$; it is a generalization of your $7$-vertex construction.)
(For more details, see for example this paper by Szekeres and Szekeres.)
answered Jan 8 at 23:37
Misha LavrovMisha Lavrov
48.1k657107
answered Jan 8 at 23:37
Misha LavrovMisha Lavrov
48.1k657107
answered Jan 8 at 23:37
Misha LavrovMisha Lavrov
48.1k657107
answered Jan 8 at 23:37
Misha LavrovMisha Lavrov
48.1k657107
48.1k657107
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%2f3066793%2fdominating-sets-in-tournaments-is-2n1-2-tight%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
