Mixing
Why this graph is connected?
$begingroup$
Let $R$ be a non-commutative finite ring with center $Z(R)$ and consider the graph $Gamma_R$ whose vertix set is $Rbackslash Z(R)$ and two vertices $a$ and $b$ are adjacent iff $ab neq ba$. In an article I am reading, [1],it is claimed that $Gamma_R$ is connected (their reasoning: just because the degree of any vertices is non zero) but I don’t get it. So please let me know why the graph is connected.
[1] On non-commuting graph of a finite ring,
J. Dutta, D. K. Basnet. 2017 submitted.
abstract-algebra graph-theory ring-theory
asked Feb 1 at 13:01
Sara.TSara.T
19510
$endgroup$
add a comment |
$begingroup$
Let $R$ be a non-commutative finite ring with center $Z(R)$ and consider the graph $Gamma_R$ whose vertix set is $Rbackslash Z(R)$ and two vertices $a$ and $b$ are adjacent iff $ab neq ba$. In an article I am reading, [1],it is claimed that $Gamma_R$ is connected (their reasoning: just because the degree of any vertices is non zero) but I don’t get it. So please let me know why the graph is connected.
[1] On non-commuting graph of a finite ring,
J. Dutta, D. K. Basnet. 2017 submitted.
abstract-algebra graph-theory ring-theory
asked Feb 1 at 13:01
Sara.TSara.T
19510
$endgroup$
$begingroup$
The title is somewhat misleading: "a graph of rings" would, presumably, have rings as vertices, not ring elements of a particular ring.
$endgroup$
– lisyarus
Feb 1 at 13:03
$begingroup$
@lisyarus you are right. I changed the title.
$endgroup$
– Sara.T
Feb 1 at 13:05
1
$begingroup$
The proper way to close an answered question is not to delete it, but to accept the appropriate answer.
$endgroup$
– lisyarus
Feb 1 at 13:26
$begingroup$
@lisyarus seems that u r always right!
$endgroup$
– Sara.T
Feb 1 at 13:27
$begingroup$
I hope not - I want to stay human and make mistakes :)
$endgroup$
– lisyarus
Feb 1 at 13:28
add a comment |
$begingroup$
Let $R$ be a non-commutative finite ring with center $Z(R)$ and consider the graph $Gamma_R$ whose vertix set is $Rbackslash Z(R)$ and two vertices $a$ and $b$ are adjacent iff $ab neq ba$. In an article I am reading, [1],it is claimed that $Gamma_R$ is connected (their reasoning: just because the degree of any vertices is non zero) but I don’t get it. So please let me know why the graph is connected.
[1] On non-commuting graph of a finite ring,
J. Dutta, D. K. Basnet. 2017 submitted.
abstract-algebra graph-theory ring-theory
asked Feb 1 at 13:01
Sara.TSara.T
19510
$endgroup$
Let $R$ be a non-commutative finite ring with center $Z(R)$ and consider the graph $Gamma_R$ whose vertix set is $Rbackslash Z(R)$ and two vertices $a$ and $b$ are adjacent iff $ab neq ba$. In an article I am reading, [1],it is claimed that $Gamma_R$ is connected (their reasoning: just because the degree of any vertices is non zero) but I don’t get it. So please let me know why the graph is connected.
[1] On non-commuting graph of a finite ring,
J. Dutta, D. K. Basnet. 2017 submitted.
abstract-algebra graph-theory ring-theory
abstract-algebra graph-theory ring-theory
asked Feb 1 at 13:01
Sara.TSara.T
19510
asked Feb 1 at 13:01
Sara.TSara.T
19510
edited Feb 1 at 13:04
Sara.T
asked Feb 1 at 13:01
Sara.TSara.T
19510
asked Feb 1 at 13:01
Sara.TSara.T
19510
asked Feb 1 at 13:01
Sara.TSara.T
19510
19510
$begingroup$
The title is somewhat misleading: "a graph of rings" would, presumably, have rings as vertices, not ring elements of a particular ring.
$endgroup$
– lisyarus
Feb 1 at 13:03
$begingroup$
@lisyarus you are right. I changed the title.
$endgroup$
– Sara.T
Feb 1 at 13:05
1
$begingroup$
The proper way to close an answered question is not to delete it, but to accept the appropriate answer.
$endgroup$
– lisyarus
Feb 1 at 13:26
$begingroup$
@lisyarus seems that u r always right!
$endgroup$
– Sara.T
Feb 1 at 13:27
$begingroup$
I hope not - I want to stay human and make mistakes :)
$endgroup$
– lisyarus
Feb 1 at 13:28
add a comment |
$begingroup$
The title is somewhat misleading: "a graph of rings" would, presumably, have rings as vertices, not ring elements of a particular ring.
$endgroup$
– lisyarus
Feb 1 at 13:03
$begingroup$
@lisyarus you are right. I changed the title.
$endgroup$
– Sara.T
Feb 1 at 13:05
1
$begingroup$
The proper way to close an answered question is not to delete it, but to accept the appropriate answer.
$endgroup$
– lisyarus
Feb 1 at 13:26
$begingroup$
@lisyarus seems that u r always right!
$endgroup$
– Sara.T
Feb 1 at 13:27
$begingroup$
I hope not - I want to stay human and make mistakes :)
$endgroup$
– lisyarus
Feb 1 at 13:28
$begingroup$
The title is somewhat misleading: "a graph of rings" would, presumably, have rings as vertices, not ring elements of a particular ring.
$endgroup$
– lisyarus
Feb 1 at 13:03
$begingroup$
The title is somewhat misleading: "a graph of rings" would, presumably, have rings as vertices, not ring elements of a particular ring.
$endgroup$
– lisyarus
Feb 1 at 13:03
$begingroup$
@lisyarus you are right. I changed the title.
$endgroup$
– Sara.T
Feb 1 at 13:05
$begingroup$
@lisyarus you are right. I changed the title.
$endgroup$
– Sara.T
Feb 1 at 13:05
1
1
$begingroup$
The proper way to close an answered question is not to delete it, but to accept the appropriate answer.
$endgroup$
– lisyarus
Feb 1 at 13:26
$begingroup$
The proper way to close an answered question is not to delete it, but to accept the appropriate answer.
$endgroup$
– lisyarus
Feb 1 at 13:26
$begingroup$
@lisyarus seems that u r always right!
$endgroup$
– Sara.T
Feb 1 at 13:27
$begingroup$
@lisyarus seems that u r always right!
$endgroup$
– Sara.T
Feb 1 at 13:27
$begingroup$
I hope not - I want to stay human and make mistakes :)
$endgroup$
– lisyarus
Feb 1 at 13:28
$begingroup$
I hope not - I want to stay human and make mistakes :)
$endgroup$
– lisyarus
Feb 1 at 13:28
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
I think the argument in the paper is incomplete, but here is how one can justify that the graph is indeed connected. Take two elements $a,bnotin Z(R)$. Consider the centralizers $C(a),C(b)$ (the set of elements commuting with $a$ and $b$, respectively). It's easy to see those are additive subgroups of $R$, and since $a,bnotin Z(R)$, they are proper subgroups, meaning $|C(a)|,|C(b)|leq |R|/2$. Since $C(a)cap C(b)$ is nonempty (it contains $0$), it follows $|C(a)cup C(b)|<|R|$. Take an element $cin Rsetminus(C(a)cup C(b))$. Then $a,c$ don't commute and neither do $b,c$, so $a,c$ and $b,c$ are edges in $Gamma_R$, showing $a,b$ are connected by a path (of length $2$).
In fact, this works even if $R$ is infinite, but we need a slightly different argument -- we need to know that a group, even an infinite one, can't be a union of two of its proper subgroups. Let $G_1,G_2subseteq G$ be two proper subgroups. If $G_1subseteq G_2$ or $G_2subseteq G_1$, it's clear their union is not $G$. Otherwise take $g_1in G_1setminus G_2,g_2in G_2setminus G_1$. Then $g_1+g_2notin G_1cup G_2$.
answered Feb 1 at 13:21
WojowuWojowu
19.3k23274
$endgroup$
$begingroup$
Thanks, very nice.
$endgroup$
– Sara.T
Feb 1 at 13:26
$begingroup$
So, it is even connected by a path of length at most 2, cool! I Wonder what happens for infinite rings.
$endgroup$
– lisyarus
Feb 1 at 13:28
1
$begingroup$
@lisyarus A very similar argument works, see my edit.
$endgroup$
– Wojowu
Feb 1 at 13:35
$begingroup$
@Wojowu Wow, this is absolutely amazing. Thank you!
$endgroup$
– lisyarus
Feb 1 at 13:39
$begingroup$
Very nice! Wish I could give this more than one upvote
$endgroup$
– Mike
Feb 1 at 18:30
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%2f3096202%2fwhy-this-graph-is-connected%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 the argument in the paper is incomplete, but here is how one can justify that the graph is indeed connected. Take two elements $a,bnotin Z(R)$. Consider the centralizers $C(a),C(b)$ (the set of elements commuting with $a$ and $b$, respectively). It's easy to see those are additive subgroups of $R$, and since $a,bnotin Z(R)$, they are proper subgroups, meaning $|C(a)|,|C(b)|leq |R|/2$. Since $C(a)cap C(b)$ is nonempty (it contains $0$), it follows $|C(a)cup C(b)|<|R|$. Take an element $cin Rsetminus(C(a)cup C(b))$. Then $a,c$ don't commute and neither do $b,c$, so $a,c$ and $b,c$ are edges in $Gamma_R$, showing $a,b$ are connected by a path (of length $2$).
In fact, this works even if $R$ is infinite, but we need a slightly different argument -- we need to know that a group, even an infinite one, can't be a union of two of its proper subgroups. Let $G_1,G_2subseteq G$ be two proper subgroups. If $G_1subseteq G_2$ or $G_2subseteq G_1$, it's clear their union is not $G$. Otherwise take $g_1in G_1setminus G_2,g_2in G_2setminus G_1$. Then $g_1+g_2notin G_1cup G_2$.
answered Feb 1 at 13:21
WojowuWojowu
19.3k23274
$endgroup$
$begingroup$
Thanks, very nice.
$endgroup$
– Sara.T
Feb 1 at 13:26
$begingroup$
So, it is even connected by a path of length at most 2, cool! I Wonder what happens for infinite rings.
$endgroup$
– lisyarus
Feb 1 at 13:28
1
$begingroup$
@lisyarus A very similar argument works, see my edit.
$endgroup$
– Wojowu
Feb 1 at 13:35
$begingroup$
@Wojowu Wow, this is absolutely amazing. Thank you!
$endgroup$
– lisyarus
Feb 1 at 13:39
$begingroup$
Very nice! Wish I could give this more than one upvote
$endgroup$
– Mike
Feb 1 at 18:30
add a comment |
$begingroup$
I think the argument in the paper is incomplete, but here is how one can justify that the graph is indeed connected. Take two elements $a,bnotin Z(R)$. Consider the centralizers $C(a),C(b)$ (the set of elements commuting with $a$ and $b$, respectively). It's easy to see those are additive subgroups of $R$, and since $a,bnotin Z(R)$, they are proper subgroups, meaning $|C(a)|,|C(b)|leq |R|/2$. Since $C(a)cap C(b)$ is nonempty (it contains $0$), it follows $|C(a)cup C(b)|<|R|$. Take an element $cin Rsetminus(C(a)cup C(b))$. Then $a,c$ don't commute and neither do $b,c$, so $a,c$ and $b,c$ are edges in $Gamma_R$, showing $a,b$ are connected by a path (of length $2$).
In fact, this works even if $R$ is infinite, but we need a slightly different argument -- we need to know that a group, even an infinite one, can't be a union of two of its proper subgroups. Let $G_1,G_2subseteq G$ be two proper subgroups. If $G_1subseteq G_2$ or $G_2subseteq G_1$, it's clear their union is not $G$. Otherwise take $g_1in G_1setminus G_2,g_2in G_2setminus G_1$. Then $g_1+g_2notin G_1cup G_2$.
answered Feb 1 at 13:21
WojowuWojowu
19.3k23274
$endgroup$
$begingroup$
Thanks, very nice.
$endgroup$
– Sara.T
Feb 1 at 13:26
$begingroup$
So, it is even connected by a path of length at most 2, cool! I Wonder what happens for infinite rings.
$endgroup$
– lisyarus
Feb 1 at 13:28
1
$begingroup$
@lisyarus A very similar argument works, see my edit.
$endgroup$
– Wojowu
Feb 1 at 13:35
$begingroup$
@Wojowu Wow, this is absolutely amazing. Thank you!
$endgroup$
– lisyarus
Feb 1 at 13:39
$begingroup$
Very nice! Wish I could give this more than one upvote
$endgroup$
– Mike
Feb 1 at 18:30
add a comment |
$begingroup$
I think the argument in the paper is incomplete, but here is how one can justify that the graph is indeed connected. Take two elements $a,bnotin Z(R)$. Consider the centralizers $C(a),C(b)$ (the set of elements commuting with $a$ and $b$, respectively). It's easy to see those are additive subgroups of $R$, and since $a,bnotin Z(R)$, they are proper subgroups, meaning $|C(a)|,|C(b)|leq |R|/2$. Since $C(a)cap C(b)$ is nonempty (it contains $0$), it follows $|C(a)cup C(b)|<|R|$. Take an element $cin Rsetminus(C(a)cup C(b))$. Then $a,c$ don't commute and neither do $b,c$, so $a,c$ and $b,c$ are edges in $Gamma_R$, showing $a,b$ are connected by a path (of length $2$).
In fact, this works even if $R$ is infinite, but we need a slightly different argument -- we need to know that a group, even an infinite one, can't be a union of two of its proper subgroups. Let $G_1,G_2subseteq G$ be two proper subgroups. If $G_1subseteq G_2$ or $G_2subseteq G_1$, it's clear their union is not $G$. Otherwise take $g_1in G_1setminus G_2,g_2in G_2setminus G_1$. Then $g_1+g_2notin G_1cup G_2$.
answered Feb 1 at 13:21
WojowuWojowu
19.3k23274
$endgroup$
I think the argument in the paper is incomplete, but here is how one can justify that the graph is indeed connected. Take two elements $a,bnotin Z(R)$. Consider the centralizers $C(a),C(b)$ (the set of elements commuting with $a$ and $b$, respectively). It's easy to see those are additive subgroups of $R$, and since $a,bnotin Z(R)$, they are proper subgroups, meaning $|C(a)|,|C(b)|leq |R|/2$. Since $C(a)cap C(b)$ is nonempty (it contains $0$), it follows $|C(a)cup C(b)|<|R|$. Take an element $cin Rsetminus(C(a)cup C(b))$. Then $a,c$ don't commute and neither do $b,c$, so $a,c$ and $b,c$ are edges in $Gamma_R$, showing $a,b$ are connected by a path (of length $2$).
In fact, this works even if $R$ is infinite, but we need a slightly different argument -- we need to know that a group, even an infinite one, can't be a union of two of its proper subgroups. Let $G_1,G_2subseteq G$ be two proper subgroups. If $G_1subseteq G_2$ or $G_2subseteq G_1$, it's clear their union is not $G$. Otherwise take $g_1in G_1setminus G_2,g_2in G_2setminus G_1$. Then $g_1+g_2notin G_1cup G_2$.
answered Feb 1 at 13:21
WojowuWojowu
19.3k23274
edited Feb 1 at 13:34
answered Feb 1 at 13:21
WojowuWojowu
19.3k23274
answered Feb 1 at 13:21
WojowuWojowu
19.3k23274
answered Feb 1 at 13:21
WojowuWojowu
19.3k23274
19.3k23274
$begingroup$
Thanks, very nice.
$endgroup$
– Sara.T
Feb 1 at 13:26
$begingroup$
So, it is even connected by a path of length at most 2, cool! I Wonder what happens for infinite rings.
$endgroup$
– lisyarus
Feb 1 at 13:28
1
$begingroup$
@lisyarus A very similar argument works, see my edit.
$endgroup$
– Wojowu
Feb 1 at 13:35
$begingroup$
@Wojowu Wow, this is absolutely amazing. Thank you!
$endgroup$
– lisyarus
Feb 1 at 13:39
$begingroup$
Very nice! Wish I could give this more than one upvote
$endgroup$
– Mike
Feb 1 at 18:30
add a comment |
$begingroup$
Thanks, very nice.
$endgroup$
– Sara.T
Feb 1 at 13:26
$begingroup$
So, it is even connected by a path of length at most 2, cool! I Wonder what happens for infinite rings.
$endgroup$
– lisyarus
Feb 1 at 13:28
1
$begingroup$
@lisyarus A very similar argument works, see my edit.
$endgroup$
– Wojowu
Feb 1 at 13:35
$begingroup$
@Wojowu Wow, this is absolutely amazing. Thank you!
$endgroup$
– lisyarus
Feb 1 at 13:39
$begingroup$
Very nice! Wish I could give this more than one upvote
$endgroup$
– Mike
Feb 1 at 18:30
$begingroup$
Thanks, very nice.
$endgroup$
– Sara.T
Feb 1 at 13:26
$begingroup$
Thanks, very nice.
$endgroup$
– Sara.T
Feb 1 at 13:26
$begingroup$
So, it is even connected by a path of length at most 2, cool! I Wonder what happens for infinite rings.
$endgroup$
– lisyarus
Feb 1 at 13:28
$begingroup$
So, it is even connected by a path of length at most 2, cool! I Wonder what happens for infinite rings.
$endgroup$
– lisyarus
Feb 1 at 13:28
1
1
$begingroup$
@lisyarus A very similar argument works, see my edit.
$endgroup$
– Wojowu
Feb 1 at 13:35
$begingroup$
@lisyarus A very similar argument works, see my edit.
$endgroup$
– Wojowu
Feb 1 at 13:35
$begingroup$
@Wojowu Wow, this is absolutely amazing. Thank you!
$endgroup$
– lisyarus
Feb 1 at 13:39
$begingroup$
@Wojowu Wow, this is absolutely amazing. Thank you!
$endgroup$
– lisyarus
Feb 1 at 13:39
$begingroup$
Very nice! Wish I could give this more than one upvote
$endgroup$
– Mike
Feb 1 at 18:30
$begingroup$
Very nice! Wish I could give this more than one upvote
$endgroup$
– Mike
Feb 1 at 18:30
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%2f3096202%2fwhy-this-graph-is-connected%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$
The title is somewhat misleading: "a graph of rings" would, presumably, have rings as vertices, not ring elements of a particular ring.
$endgroup$
– lisyarus
Feb 1 at 13:03
$begingroup$
@lisyarus you are right. I changed the title.
$endgroup$
– Sara.T
Feb 1 at 13:05
1
$begingroup$
The proper way to close an answered question is not to delete it, but to accept the appropriate answer.
$endgroup$
– lisyarus
Feb 1 at 13:26
$begingroup$
@lisyarus seems that u r always right!
$endgroup$
– Sara.T
Feb 1 at 13:27
$begingroup$
I hope not - I want to stay human and make mistakes :)
$endgroup$
– lisyarus
Feb 1 at 13:28