Show Rado Graphs Are Stable Under Edge and Vertex Removal
up vote
0
down vote
favorite
Assume $e$ is any edge in a graph $R$ and $v$ is any vertex in a graph $R$.
- Show that $R-e$ is a Rado Graph if and only if $R$ is a Rado Graph.
- Show that $R-v$ is a Rado Graph if $R$ is a Rado Graph
Do these proofs look good?
(1)
For the removal of an edge $e$, the proof follows from considering the Rado property that $forall$ 2 finite sets of vertices $V, W in R$, $exists$ a vertex $v$ that is connected by edges to every vertex in $V$ and not connected to any vertex in $W$.
Assume that $e$ was one of these edges joining a vertex $x in V$ to a vertex $v in (V cup W) backslash R$ satisfying the Rado property for the given $V, W$. I may also choose $V'$ and $W'$ to be sets s.t. $x in W$ and $V' cup W' = V cup W$. Then still $exists$ $v' in (V cup W) backslash R$ satisfying the Rado property for the given $V', W' in R$. Now, in the graph $R-e$, $v'$ will satisfy the Rado property for $V, W$, and $v$ will satisfy the Rado property for $V', W'$. The argument for the only if part of this condition is the same but consider adding an edge to the graph $R-e$. $square$
(2)
If I remove a vertex $x$ from the graph $R$, I may well have first removed $deg(x)$ edges from $x$. The Rado property will hold under removal of $deg(x)$ edges from a vertex $x in R$ by repeated application of (1). Now I want to remove $x$ which should cause no issue given that x could only be the vertex satisfying the Rado property for $R$ given $V=phi$ and $W$ finite with $W in R-v$, but $R$ was a Rado graph before removing all the edges from $v$ (which would have connected to some vertices possibly in $W$), so there is a vertex $v neq x in R$ that will satisfy the Rado property in this case. Thus, $R-v$ is necessarily Rado. $square$
proof-verification graph-theory
edited Dec 3 at 5:45
Alex Ravsky
37.3k32079
asked Dec 2 at 5:09
rjm27trekkie
1119
add a comment |
up vote
0
down vote
favorite
Assume $e$ is any edge in a graph $R$ and $v$ is any vertex in a graph $R$.
- Show that $R-e$ is a Rado Graph if and only if $R$ is a Rado Graph.
- Show that $R-v$ is a Rado Graph if $R$ is a Rado Graph
Do these proofs look good?
(1)
For the removal of an edge $e$, the proof follows from considering the Rado property that $forall$ 2 finite sets of vertices $V, W in R$, $exists$ a vertex $v$ that is connected by edges to every vertex in $V$ and not connected to any vertex in $W$.
Assume that $e$ was one of these edges joining a vertex $x in V$ to a vertex $v in (V cup W) backslash R$ satisfying the Rado property for the given $V, W$. I may also choose $V'$ and $W'$ to be sets s.t. $x in W$ and $V' cup W' = V cup W$. Then still $exists$ $v' in (V cup W) backslash R$ satisfying the Rado property for the given $V', W' in R$. Now, in the graph $R-e$, $v'$ will satisfy the Rado property for $V, W$, and $v$ will satisfy the Rado property for $V', W'$. The argument for the only if part of this condition is the same but consider adding an edge to the graph $R-e$. $square$
(2)
If I remove a vertex $x$ from the graph $R$, I may well have first removed $deg(x)$ edges from $x$. The Rado property will hold under removal of $deg(x)$ edges from a vertex $x in R$ by repeated application of (1). Now I want to remove $x$ which should cause no issue given that x could only be the vertex satisfying the Rado property for $R$ given $V=phi$ and $W$ finite with $W in R-v$, but $R$ was a Rado graph before removing all the edges from $v$ (which would have connected to some vertices possibly in $W$), so there is a vertex $v neq x in R$ that will satisfy the Rado property in this case. Thus, $R-v$ is necessarily Rado. $square$
proof-verification graph-theory
edited Dec 3 at 5:45
Alex Ravsky
37.3k32079
asked Dec 2 at 5:09
rjm27trekkie
1119
1
Does it have to be that complicated? Don't we know that, if $V$ and $W$ are disjoint finite sets of vertices in the Rado graph, than there is not just one but an infinite number of vertices $x$ joined to everything in $V$ and nothing in $W$? And isn't it pretty clear than adding or subtracting an edge, or subtracting a vertex, can't spoil more than $1$ of those infinitely many $x$'s?
– bof
Dec 2 at 11:55
If we suppose that the Rado property is satisfied by more than one vertex for any 2 finite sets then yes, but the definition doesn't tell me i get 2, just at least 1. So yes, i should have to care about there possibly being only one vertex satisfying the property for given V and W
– rjm27trekkie
Dec 2 at 16:45
Then why don't you first prove as a lemma that you can find more than one vertex for given $V$ and $W$? (Hint: what if you take the first vertex $x$ that you got, add it to $V$, and use the Rado property again?)
– bof
Dec 3 at 11:25
By the way, I believe the usual definition of the Rado property says that there is a vertex $x$ such that $x$ is joined to every vertex in $V$ and to no vertex in $W$, and $xnotin W$. You left out the $xnotin W$ part. Your version works too, but makes slightly more work. You might start by proving that your version is equivalent to the usual one.
– bof
Dec 3 at 11:28
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Assume $e$ is any edge in a graph $R$ and $v$ is any vertex in a graph $R$.
- Show that $R-e$ is a Rado Graph if and only if $R$ is a Rado Graph.
- Show that $R-v$ is a Rado Graph if $R$ is a Rado Graph
Do these proofs look good?
(1)
For the removal of an edge $e$, the proof follows from considering the Rado property that $forall$ 2 finite sets of vertices $V, W in R$, $exists$ a vertex $v$ that is connected by edges to every vertex in $V$ and not connected to any vertex in $W$.
Assume that $e$ was one of these edges joining a vertex $x in V$ to a vertex $v in (V cup W) backslash R$ satisfying the Rado property for the given $V, W$. I may also choose $V'$ and $W'$ to be sets s.t. $x in W$ and $V' cup W' = V cup W$. Then still $exists$ $v' in (V cup W) backslash R$ satisfying the Rado property for the given $V', W' in R$. Now, in the graph $R-e$, $v'$ will satisfy the Rado property for $V, W$, and $v$ will satisfy the Rado property for $V', W'$. The argument for the only if part of this condition is the same but consider adding an edge to the graph $R-e$. $square$
(2)
If I remove a vertex $x$ from the graph $R$, I may well have first removed $deg(x)$ edges from $x$. The Rado property will hold under removal of $deg(x)$ edges from a vertex $x in R$ by repeated application of (1). Now I want to remove $x$ which should cause no issue given that x could only be the vertex satisfying the Rado property for $R$ given $V=phi$ and $W$ finite with $W in R-v$, but $R$ was a Rado graph before removing all the edges from $v$ (which would have connected to some vertices possibly in $W$), so there is a vertex $v neq x in R$ that will satisfy the Rado property in this case. Thus, $R-v$ is necessarily Rado. $square$
proof-verification graph-theory
edited Dec 3 at 5:45
Alex Ravsky
37.3k32079
asked Dec 2 at 5:09
rjm27trekkie
1119
Assume $e$ is any edge in a graph $R$ and $v$ is any vertex in a graph $R$.
- Show that $R-e$ is a Rado Graph if and only if $R$ is a Rado Graph.
- Show that $R-v$ is a Rado Graph if $R$ is a Rado Graph
Do these proofs look good?
(1)
For the removal of an edge $e$, the proof follows from considering the Rado property that $forall$ 2 finite sets of vertices $V, W in R$, $exists$ a vertex $v$ that is connected by edges to every vertex in $V$ and not connected to any vertex in $W$.
Assume that $e$ was one of these edges joining a vertex $x in V$ to a vertex $v in (V cup W) backslash R$ satisfying the Rado property for the given $V, W$. I may also choose $V'$ and $W'$ to be sets s.t. $x in W$ and $V' cup W' = V cup W$. Then still $exists$ $v' in (V cup W) backslash R$ satisfying the Rado property for the given $V', W' in R$. Now, in the graph $R-e$, $v'$ will satisfy the Rado property for $V, W$, and $v$ will satisfy the Rado property for $V', W'$. The argument for the only if part of this condition is the same but consider adding an edge to the graph $R-e$. $square$
(2)
If I remove a vertex $x$ from the graph $R$, I may well have first removed $deg(x)$ edges from $x$. The Rado property will hold under removal of $deg(x)$ edges from a vertex $x in R$ by repeated application of (1). Now I want to remove $x$ which should cause no issue given that x could only be the vertex satisfying the Rado property for $R$ given $V=phi$ and $W$ finite with $W in R-v$, but $R$ was a Rado graph before removing all the edges from $v$ (which would have connected to some vertices possibly in $W$), so there is a vertex $v neq x in R$ that will satisfy the Rado property in this case. Thus, $R-v$ is necessarily Rado. $square$
proof-verification graph-theory
proof-verification graph-theory
edited Dec 3 at 5:45
Alex Ravsky
37.3k32079
asked Dec 2 at 5:09
rjm27trekkie
1119
edited Dec 3 at 5:45
Alex Ravsky
37.3k32079
asked Dec 2 at 5:09
rjm27trekkie
1119
edited Dec 3 at 5:45
Alex Ravsky
37.3k32079
edited Dec 3 at 5:45
Alex Ravsky
37.3k32079
edited Dec 3 at 5:45
Alex Ravsky
37.3k32079
37.3k32079
asked Dec 2 at 5:09
rjm27trekkie
1119
asked Dec 2 at 5:09
rjm27trekkie
1119
asked Dec 2 at 5:09
rjm27trekkie
1119
1119
1
Does it have to be that complicated? Don't we know that, if $V$ and $W$ are disjoint finite sets of vertices in the Rado graph, than there is not just one but an infinite number of vertices $x$ joined to everything in $V$ and nothing in $W$? And isn't it pretty clear than adding or subtracting an edge, or subtracting a vertex, can't spoil more than $1$ of those infinitely many $x$'s?
– bof
Dec 2 at 11:55
If we suppose that the Rado property is satisfied by more than one vertex for any 2 finite sets then yes, but the definition doesn't tell me i get 2, just at least 1. So yes, i should have to care about there possibly being only one vertex satisfying the property for given V and W
– rjm27trekkie
Dec 2 at 16:45
Then why don't you first prove as a lemma that you can find more than one vertex for given $V$ and $W$? (Hint: what if you take the first vertex $x$ that you got, add it to $V$, and use the Rado property again?)
– bof
Dec 3 at 11:25
By the way, I believe the usual definition of the Rado property says that there is a vertex $x$ such that $x$ is joined to every vertex in $V$ and to no vertex in $W$, and $xnotin W$. You left out the $xnotin W$ part. Your version works too, but makes slightly more work. You might start by proving that your version is equivalent to the usual one.
– bof
Dec 3 at 11:28
add a comment |
1
Does it have to be that complicated? Don't we know that, if $V$ and $W$ are disjoint finite sets of vertices in the Rado graph, than there is not just one but an infinite number of vertices $x$ joined to everything in $V$ and nothing in $W$? And isn't it pretty clear than adding or subtracting an edge, or subtracting a vertex, can't spoil more than $1$ of those infinitely many $x$'s?
– bof
Dec 2 at 11:55
If we suppose that the Rado property is satisfied by more than one vertex for any 2 finite sets then yes, but the definition doesn't tell me i get 2, just at least 1. So yes, i should have to care about there possibly being only one vertex satisfying the property for given V and W
– rjm27trekkie
Dec 2 at 16:45
Then why don't you first prove as a lemma that you can find more than one vertex for given $V$ and $W$? (Hint: what if you take the first vertex $x$ that you got, add it to $V$, and use the Rado property again?)
– bof
Dec 3 at 11:25
By the way, I believe the usual definition of the Rado property says that there is a vertex $x$ such that $x$ is joined to every vertex in $V$ and to no vertex in $W$, and $xnotin W$. You left out the $xnotin W$ part. Your version works too, but makes slightly more work. You might start by proving that your version is equivalent to the usual one.
– bof
Dec 3 at 11:28
1
1
Does it have to be that complicated? Don't we know that, if $V$ and $W$ are disjoint finite sets of vertices in the Rado graph, than there is not just one but an infinite number of vertices $x$ joined to everything in $V$ and nothing in $W$? And isn't it pretty clear than adding or subtracting an edge, or subtracting a vertex, can't spoil more than $1$ of those infinitely many $x$'s?
– bof
Dec 2 at 11:55
Does it have to be that complicated? Don't we know that, if $V$ and $W$ are disjoint finite sets of vertices in the Rado graph, than there is not just one but an infinite number of vertices $x$ joined to everything in $V$ and nothing in $W$? And isn't it pretty clear than adding or subtracting an edge, or subtracting a vertex, can't spoil more than $1$ of those infinitely many $x$'s?
– bof
Dec 2 at 11:55
If we suppose that the Rado property is satisfied by more than one vertex for any 2 finite sets then yes, but the definition doesn't tell me i get 2, just at least 1. So yes, i should have to care about there possibly being only one vertex satisfying the property for given V and W
– rjm27trekkie
Dec 2 at 16:45
If we suppose that the Rado property is satisfied by more than one vertex for any 2 finite sets then yes, but the definition doesn't tell me i get 2, just at least 1. So yes, i should have to care about there possibly being only one vertex satisfying the property for given V and W
– rjm27trekkie
Dec 2 at 16:45
Then why don't you first prove as a lemma that you can find more than one vertex for given $V$ and $W$? (Hint: what if you take the first vertex $x$ that you got, add it to $V$, and use the Rado property again?)
– bof
Dec 3 at 11:25
Then why don't you first prove as a lemma that you can find more than one vertex for given $V$ and $W$? (Hint: what if you take the first vertex $x$ that you got, add it to $V$, and use the Rado property again?)
– bof
Dec 3 at 11:25
By the way, I believe the usual definition of the Rado property says that there is a vertex $x$ such that $x$ is joined to every vertex in $V$ and to no vertex in $W$, and $xnotin W$. You left out the $xnotin W$ part. Your version works too, but makes slightly more work. You might start by proving that your version is equivalent to the usual one.
– bof
Dec 3 at 11:28
By the way, I believe the usual definition of the Rado property says that there is a vertex $x$ such that $x$ is joined to every vertex in $V$ and to no vertex in $W$, and $xnotin W$. You left out the $xnotin W$ part. Your version works too, but makes slightly more work. You might start by proving that your version is equivalent to the usual one.
– bof
Dec 3 at 11:28
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
I disagree with part of your first proof. A vertex $v in (V cup W) backslash R$ makes no sense, since $V$ and $W$ are both subsets of R, thus $(V cup W) backslash R = phi$. A definition of $R backslash (V cup W)$ makes more sense to me, especially given how you defined the Rado property (each vertex $v$ which fulfills the property for some $V$ and $W$ cannot be a member of either $V$ nor $W$).
answered Dec 3 at 9:46
theasianpianist
31
This is the definition. $V subset R, W subset R$ but $V cup W neq R$. They are not spanning subsets of $R$ because they are FINITE while $R$ is countably infinite. (V cup W) | R describes all these vertices not in V or W (2 finite subsets of R) that are also in R (that's what the relative set complement under R ( operator) means
– rjm27trekkie
Dec 3 at 15:38
en.wikipedia.org/wiki/Complement_(set_theory) I stand by the statement that $(V cup W) backslash R$ means all members of $V cup W$ which are not in $R$.
– theasianpianist
Dec 3 at 15:54
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
I disagree with part of your first proof. A vertex $v in (V cup W) backslash R$ makes no sense, since $V$ and $W$ are both subsets of R, thus $(V cup W) backslash R = phi$. A definition of $R backslash (V cup W)$ makes more sense to me, especially given how you defined the Rado property (each vertex $v$ which fulfills the property for some $V$ and $W$ cannot be a member of either $V$ nor $W$).
answered Dec 3 at 9:46
theasianpianist
31
This is the definition. $V subset R, W subset R$ but $V cup W neq R$. They are not spanning subsets of $R$ because they are FINITE while $R$ is countably infinite. (V cup W) | R describes all these vertices not in V or W (2 finite subsets of R) that are also in R (that's what the relative set complement under R ( operator) means
– rjm27trekkie
Dec 3 at 15:38
en.wikipedia.org/wiki/Complement_(set_theory) I stand by the statement that $(V cup W) backslash R$ means all members of $V cup W$ which are not in $R$.
– theasianpianist
Dec 3 at 15:54
add a comment |
up vote
0
down vote
I disagree with part of your first proof. A vertex $v in (V cup W) backslash R$ makes no sense, since $V$ and $W$ are both subsets of R, thus $(V cup W) backslash R = phi$. A definition of $R backslash (V cup W)$ makes more sense to me, especially given how you defined the Rado property (each vertex $v$ which fulfills the property for some $V$ and $W$ cannot be a member of either $V$ nor $W$).
answered Dec 3 at 9:46
theasianpianist
31
This is the definition. $V subset R, W subset R$ but $V cup W neq R$. They are not spanning subsets of $R$ because they are FINITE while $R$ is countably infinite. (V cup W) | R describes all these vertices not in V or W (2 finite subsets of R) that are also in R (that's what the relative set complement under R ( operator) means
– rjm27trekkie
Dec 3 at 15:38
en.wikipedia.org/wiki/Complement_(set_theory) I stand by the statement that $(V cup W) backslash R$ means all members of $V cup W$ which are not in $R$.
– theasianpianist
Dec 3 at 15:54
add a comment |
up vote
0
down vote
up vote
0
down vote
I disagree with part of your first proof. A vertex $v in (V cup W) backslash R$ makes no sense, since $V$ and $W$ are both subsets of R, thus $(V cup W) backslash R = phi$. A definition of $R backslash (V cup W)$ makes more sense to me, especially given how you defined the Rado property (each vertex $v$ which fulfills the property for some $V$ and $W$ cannot be a member of either $V$ nor $W$).
answered Dec 3 at 9:46
theasianpianist
31
I disagree with part of your first proof. A vertex $v in (V cup W) backslash R$ makes no sense, since $V$ and $W$ are both subsets of R, thus $(V cup W) backslash R = phi$. A definition of $R backslash (V cup W)$ makes more sense to me, especially given how you defined the Rado property (each vertex $v$ which fulfills the property for some $V$ and $W$ cannot be a member of either $V$ nor $W$).
answered Dec 3 at 9:46
theasianpianist
31
answered Dec 3 at 9:46
theasianpianist
31
answered Dec 3 at 9:46
theasianpianist
31
answered Dec 3 at 9:46
theasianpianist
31
31
This is the definition. $V subset R, W subset R$ but $V cup W neq R$. They are not spanning subsets of $R$ because they are FINITE while $R$ is countably infinite. (V cup W) | R describes all these vertices not in V or W (2 finite subsets of R) that are also in R (that's what the relative set complement under R ( operator) means
– rjm27trekkie
Dec 3 at 15:38
en.wikipedia.org/wiki/Complement_(set_theory) I stand by the statement that $(V cup W) backslash R$ means all members of $V cup W$ which are not in $R$.
– theasianpianist
Dec 3 at 15:54
add a comment |
This is the definition. $V subset R, W subset R$ but $V cup W neq R$. They are not spanning subsets of $R$ because they are FINITE while $R$ is countably infinite. (V cup W) | R describes all these vertices not in V or W (2 finite subsets of R) that are also in R (that's what the relative set complement under R ( operator) means
– rjm27trekkie
Dec 3 at 15:38
en.wikipedia.org/wiki/Complement_(set_theory) I stand by the statement that $(V cup W) backslash R$ means all members of $V cup W$ which are not in $R$.
– theasianpianist
Dec 3 at 15:54
This is the definition. $V subset R, W subset R$ but $V cup W neq R$. They are not spanning subsets of $R$ because they are FINITE while $R$ is countably infinite. (V cup W) | R describes all these vertices not in V or W (2 finite subsets of R) that are also in R (that's what the relative set complement under R ( operator) means
– rjm27trekkie
Dec 3 at 15:38
This is the definition. $V subset R, W subset R$ but $V cup W neq R$. They are not spanning subsets of $R$ because they are FINITE while $R$ is countably infinite. (V cup W) | R describes all these vertices not in V or W (2 finite subsets of R) that are also in R (that's what the relative set complement under R ( operator) means
– rjm27trekkie
Dec 3 at 15:38
en.wikipedia.org/wiki/Complement_(set_theory) I stand by the statement that $(V cup W) backslash R$ means all members of $V cup W$ which are not in $R$.
– theasianpianist
Dec 3 at 15:54
en.wikipedia.org/wiki/Complement_(set_theory) I stand by the statement that $(V cup W) backslash R$ means all members of $V cup W$ which are not in $R$.
– theasianpianist
Dec 3 at 15:54
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3022260%2fshow-rado-graphs-are-stable-under-edge-and-vertex-removal%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
Does it have to be that complicated? Don't we know that, if $V$ and $W$ are disjoint finite sets of vertices in the Rado graph, than there is not just one but an infinite number of vertices $x$ joined to everything in $V$ and nothing in $W$? And isn't it pretty clear than adding or subtracting an edge, or subtracting a vertex, can't spoil more than $1$ of those infinitely many $x$'s?
– bof
Dec 2 at 11:55
If we suppose that the Rado property is satisfied by more than one vertex for any 2 finite sets then yes, but the definition doesn't tell me i get 2, just at least 1. So yes, i should have to care about there possibly being only one vertex satisfying the property for given V and W
– rjm27trekkie
Dec 2 at 16:45
Then why don't you first prove as a lemma that you can find more than one vertex for given $V$ and $W$? (Hint: what if you take the first vertex $x$ that you got, add it to $V$, and use the Rado property again?)
– bof
Dec 3 at 11:25
By the way, I believe the usual definition of the Rado property says that there is a vertex $x$ such that $x$ is joined to every vertex in $V$ and to no vertex in $W$, and $xnotin W$. You left out the $xnotin W$ part. Your version works too, but makes slightly more work. You might start by proving that your version is equivalent to the usual one.
– bof
Dec 3 at 11:28