Mixing
Partitions of the set of vertices of a directed graph
$begingroup$
Consider a directed graph and a partition $P$ of its set of vertices. We construct a new partition $P'$ of this set as follows: declare $v_1$ and $v_2$ to be in the same part of the partition $P'$ if for every $pin P$, $v_1$ arrows into $xin p$ for some $x$ iff $v_2$ arrows into $yin p$ for some $y$. The problem is to prove or give a counterexample to the statement that the finer the original partition is, the finer the new partition will be. (By finer I mean either the same or strictly finer.)
I haven't been able come up with a counterexample, so I'm trying to prove this. Suppose this is false. Let $P_1$ and $P_2$ be two partitions. Denote by $P_i'$ the corresponding new partition. By assumption, $P_2'$ is not finer than $P_1'$. So there is $xin P_2'$ such that for all $yin P_1'$ it is not the case that $xsubset y$. I need to show that then there is $Xin P_2$ such that for all $Yin P_1$ it is not the case that $Xsubset Y$. But I don't quite understand how to use the definition of the new partition to deduce this. Any help?
combinatorics discrete-mathematics graph-theory directed-graphs
asked Jan 28 at 0:49
user638943user638943
84
$endgroup$
add a comment |
$begingroup$
Consider a directed graph and a partition $P$ of its set of vertices. We construct a new partition $P'$ of this set as follows: declare $v_1$ and $v_2$ to be in the same part of the partition $P'$ if for every $pin P$, $v_1$ arrows into $xin p$ for some $x$ iff $v_2$ arrows into $yin p$ for some $y$. The problem is to prove or give a counterexample to the statement that the finer the original partition is, the finer the new partition will be. (By finer I mean either the same or strictly finer.)
I haven't been able come up with a counterexample, so I'm trying to prove this. Suppose this is false. Let $P_1$ and $P_2$ be two partitions. Denote by $P_i'$ the corresponding new partition. By assumption, $P_2'$ is not finer than $P_1'$. So there is $xin P_2'$ such that for all $yin P_1'$ it is not the case that $xsubset y$. I need to show that then there is $Xin P_2$ such that for all $Yin P_1$ it is not the case that $Xsubset Y$. But I don't quite understand how to use the definition of the new partition to deduce this. Any help?
combinatorics discrete-mathematics graph-theory directed-graphs
asked Jan 28 at 0:49
user638943user638943
84
$endgroup$
add a comment |
$begingroup$
Consider a directed graph and a partition $P$ of its set of vertices. We construct a new partition $P'$ of this set as follows: declare $v_1$ and $v_2$ to be in the same part of the partition $P'$ if for every $pin P$, $v_1$ arrows into $xin p$ for some $x$ iff $v_2$ arrows into $yin p$ for some $y$. The problem is to prove or give a counterexample to the statement that the finer the original partition is, the finer the new partition will be. (By finer I mean either the same or strictly finer.)
I haven't been able come up with a counterexample, so I'm trying to prove this. Suppose this is false. Let $P_1$ and $P_2$ be two partitions. Denote by $P_i'$ the corresponding new partition. By assumption, $P_2'$ is not finer than $P_1'$. So there is $xin P_2'$ such that for all $yin P_1'$ it is not the case that $xsubset y$. I need to show that then there is $Xin P_2$ such that for all $Yin P_1$ it is not the case that $Xsubset Y$. But I don't quite understand how to use the definition of the new partition to deduce this. Any help?
combinatorics discrete-mathematics graph-theory directed-graphs
asked Jan 28 at 0:49
user638943user638943
84
$endgroup$
Consider a directed graph and a partition $P$ of its set of vertices. We construct a new partition $P'$ of this set as follows: declare $v_1$ and $v_2$ to be in the same part of the partition $P'$ if for every $pin P$, $v_1$ arrows into $xin p$ for some $x$ iff $v_2$ arrows into $yin p$ for some $y$. The problem is to prove or give a counterexample to the statement that the finer the original partition is, the finer the new partition will be. (By finer I mean either the same or strictly finer.)
I haven't been able come up with a counterexample, so I'm trying to prove this. Suppose this is false. Let $P_1$ and $P_2$ be two partitions. Denote by $P_i'$ the corresponding new partition. By assumption, $P_2'$ is not finer than $P_1'$. So there is $xin P_2'$ such that for all $yin P_1'$ it is not the case that $xsubset y$. I need to show that then there is $Xin P_2$ such that for all $Yin P_1$ it is not the case that $Xsubset Y$. But I don't quite understand how to use the definition of the new partition to deduce this. Any help?
combinatorics discrete-mathematics graph-theory directed-graphs
combinatorics discrete-mathematics graph-theory directed-graphs
asked Jan 28 at 0:49
user638943user638943
84
asked Jan 28 at 0:49
user638943user638943
84
edited Jan 28 at 1:16
user638943
asked Jan 28 at 0:49
user638943user638943
84
asked Jan 28 at 0:49
user638943user638943
84
asked Jan 28 at 0:49
user638943user638943
84
84
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
I think that a direct proof is more simple than a proof to the contrary. Assume that $P_2$ is finer than $P_1$. Consider any $p’_2in P_2’$. Let $v,uin p’_2$ be any vertices and $p_1in P_1$ be any element. If $v$ arrows to $x$ for some $xin p_1$ then, since $P_2$ is finer than $P_1$, there exist $p_2in P_2$ with $xin p_2subset p_1$. Since $v,uin p’_2$, there exists $yin p_2subset p_1$ such that $u$ arrows to $y$. Similarly we can show that if $u$ arrows to $x$ for some $xin p_1$ then there exists $yin p_1$ such that $v$ arrows to $y$. Thus $v$ and $u$ are in the same part of the partition $P’_1$. So $P’_2$ is finer than $P'_1$.
answered Jan 28 at 2:22
Alex RavskyAlex Ravsky
42.7k32383
$endgroup$
$begingroup$
What definition of "$P_2$ is finer than $P_1$" are you using? I thought it means that every element of $P_2$ is a subset of some element of $P_1$. But it looks you're using another definition. Is your definition equivalent to the above?
$endgroup$
– user638943
Jan 28 at 3:03
$begingroup$
(Addition to the above: you must be using the definition in line 3 and in the last line, and I don't quite understand what's the definition that you are using and what exactly you are proving.) And could you clarify how this follows: "since $u,vin p_2'$, there exists $yin p_2subset p_1$ such that $u$ arrows to $y$"? Also, you write "if $v$ arrows to $x$" or "if $u$ arrows to $x$", but what if not?
$endgroup$
– user638943
Jan 28 at 3:41
$begingroup$
@user638943 1. Yes, I use the same definition as you. 2. Since $v$ arrows to $x$, $xin p_2$, and $v,uin p’_2$, by definition of $P’_2$, $u$ arrows to $y$ for som $yin p_2$. 3. In order to show that $v$ and $u$ are in the same part of the partition $P’_1$ we have to sheck that for every $p_1in P_1$, $v$ arrows into $xin p_1$ for some $x$ $Leftrightarrow$ $u$ arrows into $yin p_1$ for some $y$. When we consider $v$ arrows to $x$, we show $Rightarrow$, when we consider $u$ arrows to $x$, we show $Leftarrow$.
$endgroup$
– Alex Ravsky
Jan 29 at 3:32
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%2f3090312%2fpartitions-of-the-set-of-vertices-of-a-directed-graph%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$
I think that a direct proof is more simple than a proof to the contrary. Assume that $P_2$ is finer than $P_1$. Consider any $p’_2in P_2’$. Let $v,uin p’_2$ be any vertices and $p_1in P_1$ be any element. If $v$ arrows to $x$ for some $xin p_1$ then, since $P_2$ is finer than $P_1$, there exist $p_2in P_2$ with $xin p_2subset p_1$. Since $v,uin p’_2$, there exists $yin p_2subset p_1$ such that $u$ arrows to $y$. Similarly we can show that if $u$ arrows to $x$ for some $xin p_1$ then there exists $yin p_1$ such that $v$ arrows to $y$. Thus $v$ and $u$ are in the same part of the partition $P’_1$. So $P’_2$ is finer than $P'_1$.
answered Jan 28 at 2:22
Alex RavskyAlex Ravsky
42.7k32383
$endgroup$
$begingroup$
What definition of "$P_2$ is finer than $P_1$" are you using? I thought it means that every element of $P_2$ is a subset of some element of $P_1$. But it looks you're using another definition. Is your definition equivalent to the above?
$endgroup$
– user638943
Jan 28 at 3:03
$begingroup$
(Addition to the above: you must be using the definition in line 3 and in the last line, and I don't quite understand what's the definition that you are using and what exactly you are proving.) And could you clarify how this follows: "since $u,vin p_2'$, there exists $yin p_2subset p_1$ such that $u$ arrows to $y$"? Also, you write "if $v$ arrows to $x$" or "if $u$ arrows to $x$", but what if not?
$endgroup$
– user638943
Jan 28 at 3:41
$begingroup$
@user638943 1. Yes, I use the same definition as you. 2. Since $v$ arrows to $x$, $xin p_2$, and $v,uin p’_2$, by definition of $P’_2$, $u$ arrows to $y$ for som $yin p_2$. 3. In order to show that $v$ and $u$ are in the same part of the partition $P’_1$ we have to sheck that for every $p_1in P_1$, $v$ arrows into $xin p_1$ for some $x$ $Leftrightarrow$ $u$ arrows into $yin p_1$ for some $y$. When we consider $v$ arrows to $x$, we show $Rightarrow$, when we consider $u$ arrows to $x$, we show $Leftarrow$.
$endgroup$
– Alex Ravsky
Jan 29 at 3:32
add a comment |
$begingroup$
I think that a direct proof is more simple than a proof to the contrary. Assume that $P_2$ is finer than $P_1$. Consider any $p’_2in P_2’$. Let $v,uin p’_2$ be any vertices and $p_1in P_1$ be any element. If $v$ arrows to $x$ for some $xin p_1$ then, since $P_2$ is finer than $P_1$, there exist $p_2in P_2$ with $xin p_2subset p_1$. Since $v,uin p’_2$, there exists $yin p_2subset p_1$ such that $u$ arrows to $y$. Similarly we can show that if $u$ arrows to $x$ for some $xin p_1$ then there exists $yin p_1$ such that $v$ arrows to $y$. Thus $v$ and $u$ are in the same part of the partition $P’_1$. So $P’_2$ is finer than $P'_1$.
answered Jan 28 at 2:22
Alex RavskyAlex Ravsky
42.7k32383
$endgroup$
$begingroup$
What definition of "$P_2$ is finer than $P_1$" are you using? I thought it means that every element of $P_2$ is a subset of some element of $P_1$. But it looks you're using another definition. Is your definition equivalent to the above?
$endgroup$
– user638943
Jan 28 at 3:03
$begingroup$
(Addition to the above: you must be using the definition in line 3 and in the last line, and I don't quite understand what's the definition that you are using and what exactly you are proving.) And could you clarify how this follows: "since $u,vin p_2'$, there exists $yin p_2subset p_1$ such that $u$ arrows to $y$"? Also, you write "if $v$ arrows to $x$" or "if $u$ arrows to $x$", but what if not?
$endgroup$
– user638943
Jan 28 at 3:41
$begingroup$
@user638943 1. Yes, I use the same definition as you. 2. Since $v$ arrows to $x$, $xin p_2$, and $v,uin p’_2$, by definition of $P’_2$, $u$ arrows to $y$ for som $yin p_2$. 3. In order to show that $v$ and $u$ are in the same part of the partition $P’_1$ we have to sheck that for every $p_1in P_1$, $v$ arrows into $xin p_1$ for some $x$ $Leftrightarrow$ $u$ arrows into $yin p_1$ for some $y$. When we consider $v$ arrows to $x$, we show $Rightarrow$, when we consider $u$ arrows to $x$, we show $Leftarrow$.
$endgroup$
– Alex Ravsky
Jan 29 at 3:32
add a comment |
$begingroup$
I think that a direct proof is more simple than a proof to the contrary. Assume that $P_2$ is finer than $P_1$. Consider any $p’_2in P_2’$. Let $v,uin p’_2$ be any vertices and $p_1in P_1$ be any element. If $v$ arrows to $x$ for some $xin p_1$ then, since $P_2$ is finer than $P_1$, there exist $p_2in P_2$ with $xin p_2subset p_1$. Since $v,uin p’_2$, there exists $yin p_2subset p_1$ such that $u$ arrows to $y$. Similarly we can show that if $u$ arrows to $x$ for some $xin p_1$ then there exists $yin p_1$ such that $v$ arrows to $y$. Thus $v$ and $u$ are in the same part of the partition $P’_1$. So $P’_2$ is finer than $P'_1$.
answered Jan 28 at 2:22
Alex RavskyAlex Ravsky
42.7k32383
$endgroup$
I think that a direct proof is more simple than a proof to the contrary. Assume that $P_2$ is finer than $P_1$. Consider any $p’_2in P_2’$. Let $v,uin p’_2$ be any vertices and $p_1in P_1$ be any element. If $v$ arrows to $x$ for some $xin p_1$ then, since $P_2$ is finer than $P_1$, there exist $p_2in P_2$ with $xin p_2subset p_1$. Since $v,uin p’_2$, there exists $yin p_2subset p_1$ such that $u$ arrows to $y$. Similarly we can show that if $u$ arrows to $x$ for some $xin p_1$ then there exists $yin p_1$ such that $v$ arrows to $y$. Thus $v$ and $u$ are in the same part of the partition $P’_1$. So $P’_2$ is finer than $P'_1$.
answered Jan 28 at 2:22
Alex RavskyAlex Ravsky
42.7k32383
answered Jan 28 at 2:22
Alex RavskyAlex Ravsky
42.7k32383
answered Jan 28 at 2:22
Alex RavskyAlex Ravsky
42.7k32383
answered Jan 28 at 2:22
Alex RavskyAlex Ravsky
42.7k32383
42.7k32383
$begingroup$
What definition of "$P_2$ is finer than $P_1$" are you using? I thought it means that every element of $P_2$ is a subset of some element of $P_1$. But it looks you're using another definition. Is your definition equivalent to the above?
$endgroup$
– user638943
Jan 28 at 3:03
$begingroup$
(Addition to the above: you must be using the definition in line 3 and in the last line, and I don't quite understand what's the definition that you are using and what exactly you are proving.) And could you clarify how this follows: "since $u,vin p_2'$, there exists $yin p_2subset p_1$ such that $u$ arrows to $y$"? Also, you write "if $v$ arrows to $x$" or "if $u$ arrows to $x$", but what if not?
$endgroup$
– user638943
Jan 28 at 3:41
$begingroup$
@user638943 1. Yes, I use the same definition as you. 2. Since $v$ arrows to $x$, $xin p_2$, and $v,uin p’_2$, by definition of $P’_2$, $u$ arrows to $y$ for som $yin p_2$. 3. In order to show that $v$ and $u$ are in the same part of the partition $P’_1$ we have to sheck that for every $p_1in P_1$, $v$ arrows into $xin p_1$ for some $x$ $Leftrightarrow$ $u$ arrows into $yin p_1$ for some $y$. When we consider $v$ arrows to $x$, we show $Rightarrow$, when we consider $u$ arrows to $x$, we show $Leftarrow$.
$endgroup$
– Alex Ravsky
Jan 29 at 3:32
add a comment |
$begingroup$
What definition of "$P_2$ is finer than $P_1$" are you using? I thought it means that every element of $P_2$ is a subset of some element of $P_1$. But it looks you're using another definition. Is your definition equivalent to the above?
$endgroup$
– user638943
Jan 28 at 3:03
$begingroup$
(Addition to the above: you must be using the definition in line 3 and in the last line, and I don't quite understand what's the definition that you are using and what exactly you are proving.) And could you clarify how this follows: "since $u,vin p_2'$, there exists $yin p_2subset p_1$ such that $u$ arrows to $y$"? Also, you write "if $v$ arrows to $x$" or "if $u$ arrows to $x$", but what if not?
$endgroup$
– user638943
Jan 28 at 3:41
$begingroup$
@user638943 1. Yes, I use the same definition as you. 2. Since $v$ arrows to $x$, $xin p_2$, and $v,uin p’_2$, by definition of $P’_2$, $u$ arrows to $y$ for som $yin p_2$. 3. In order to show that $v$ and $u$ are in the same part of the partition $P’_1$ we have to sheck that for every $p_1in P_1$, $v$ arrows into $xin p_1$ for some $x$ $Leftrightarrow$ $u$ arrows into $yin p_1$ for some $y$. When we consider $v$ arrows to $x$, we show $Rightarrow$, when we consider $u$ arrows to $x$, we show $Leftarrow$.
$endgroup$
– Alex Ravsky
Jan 29 at 3:32
$begingroup$
What definition of "$P_2$ is finer than $P_1$" are you using? I thought it means that every element of $P_2$ is a subset of some element of $P_1$. But it looks you're using another definition. Is your definition equivalent to the above?
$endgroup$
– user638943
Jan 28 at 3:03
$begingroup$
What definition of "$P_2$ is finer than $P_1$" are you using? I thought it means that every element of $P_2$ is a subset of some element of $P_1$. But it looks you're using another definition. Is your definition equivalent to the above?
$endgroup$
– user638943
Jan 28 at 3:03
$begingroup$
(Addition to the above: you must be using the definition in line 3 and in the last line, and I don't quite understand what's the definition that you are using and what exactly you are proving.) And could you clarify how this follows: "since $u,vin p_2'$, there exists $yin p_2subset p_1$ such that $u$ arrows to $y$"? Also, you write "if $v$ arrows to $x$" or "if $u$ arrows to $x$", but what if not?
$endgroup$
– user638943
Jan 28 at 3:41
$begingroup$
(Addition to the above: you must be using the definition in line 3 and in the last line, and I don't quite understand what's the definition that you are using and what exactly you are proving.) And could you clarify how this follows: "since $u,vin p_2'$, there exists $yin p_2subset p_1$ such that $u$ arrows to $y$"? Also, you write "if $v$ arrows to $x$" or "if $u$ arrows to $x$", but what if not?
$endgroup$
– user638943
Jan 28 at 3:41
$begingroup$
@user638943 1. Yes, I use the same definition as you. 2. Since $v$ arrows to $x$, $xin p_2$, and $v,uin p’_2$, by definition of $P’_2$, $u$ arrows to $y$ for som $yin p_2$. 3. In order to show that $v$ and $u$ are in the same part of the partition $P’_1$ we have to sheck that for every $p_1in P_1$, $v$ arrows into $xin p_1$ for some $x$ $Leftrightarrow$ $u$ arrows into $yin p_1$ for some $y$. When we consider $v$ arrows to $x$, we show $Rightarrow$, when we consider $u$ arrows to $x$, we show $Leftarrow$.
$endgroup$
– Alex Ravsky
Jan 29 at 3:32
$begingroup$
@user638943 1. Yes, I use the same definition as you. 2. Since $v$ arrows to $x$, $xin p_2$, and $v,uin p’_2$, by definition of $P’_2$, $u$ arrows to $y$ for som $yin p_2$. 3. In order to show that $v$ and $u$ are in the same part of the partition $P’_1$ we have to sheck that for every $p_1in P_1$, $v$ arrows into $xin p_1$ for some $x$ $Leftrightarrow$ $u$ arrows into $yin p_1$ for some $y$. When we consider $v$ arrows to $x$, we show $Rightarrow$, when we consider $u$ arrows to $x$, we show $Leftarrow$.
$endgroup$
– Alex Ravsky
Jan 29 at 3:32
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%2f3090312%2fpartitions-of-the-set-of-vertices-of-a-directed-graph%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
