Degree of quotient graph of a regular graph
$begingroup$
What can we say about the degree of a quotient of a regular graph? Intuitively, I think the situation may get arbitrarily bad. Specifically, I am looking for an example of an infinite family of $k$-regular graphs $(X_n)$, and a family $(Y_n)$ where $Y_n$ is a quotient of $X_n$, and the maximal degree $Delta(Y_n)$ is unbounded.
The reason I am interested in this, is that I read in various references that quotients of expanding graphs are expanding graphs. Although it is easy to check that quotients of expanding graphs satisfy the expanding condition for the same constant, it is not clear to me why when taking quotients of an infinite family of expanders the degree should be bounded. In all instances where I have seen this fact to be applied, it turns out that it is, but I was wondering if this is a general fact or not.
Edit: I am especially interested in quotients where all the sets of the partition have the same size.
combinatorics graph-theory
asked Dec 17 '18 at 13:15
frafourfrafour
885312
$endgroup$
add a comment |
$begingroup$
What can we say about the degree of a quotient of a regular graph? Intuitively, I think the situation may get arbitrarily bad. Specifically, I am looking for an example of an infinite family of $k$-regular graphs $(X_n)$, and a family $(Y_n)$ where $Y_n$ is a quotient of $X_n$, and the maximal degree $Delta(Y_n)$ is unbounded.
The reason I am interested in this, is that I read in various references that quotients of expanding graphs are expanding graphs. Although it is easy to check that quotients of expanding graphs satisfy the expanding condition for the same constant, it is not clear to me why when taking quotients of an infinite family of expanders the degree should be bounded. In all instances where I have seen this fact to be applied, it turns out that it is, but I was wondering if this is a general fact or not.
Edit: I am especially interested in quotients where all the sets of the partition have the same size.
combinatorics graph-theory
asked Dec 17 '18 at 13:15
frafourfrafour
885312
$endgroup$
$begingroup$
Are you limiting the partition we choose to quotient by? It seems like on the one hand, we can take one part of the partition to be a dominating set and the rest to have size 1, and get one vertex with very high degree. On the other hand, if all parts have size at most $t$, then the quotient graph has maximum degree at most $kcdot t$.
$endgroup$
– Misha Lavrov
Dec 17 '18 at 15:18
$begingroup$
@MishaLavrov I just edited the question to make it more specific.
$endgroup$
– frafour
Dec 17 '18 at 16:12
add a comment |
$begingroup$
What can we say about the degree of a quotient of a regular graph? Intuitively, I think the situation may get arbitrarily bad. Specifically, I am looking for an example of an infinite family of $k$-regular graphs $(X_n)$, and a family $(Y_n)$ where $Y_n$ is a quotient of $X_n$, and the maximal degree $Delta(Y_n)$ is unbounded.
The reason I am interested in this, is that I read in various references that quotients of expanding graphs are expanding graphs. Although it is easy to check that quotients of expanding graphs satisfy the expanding condition for the same constant, it is not clear to me why when taking quotients of an infinite family of expanders the degree should be bounded. In all instances where I have seen this fact to be applied, it turns out that it is, but I was wondering if this is a general fact or not.
Edit: I am especially interested in quotients where all the sets of the partition have the same size.
combinatorics graph-theory
asked Dec 17 '18 at 13:15
frafourfrafour
885312
$endgroup$
What can we say about the degree of a quotient of a regular graph? Intuitively, I think the situation may get arbitrarily bad. Specifically, I am looking for an example of an infinite family of $k$-regular graphs $(X_n)$, and a family $(Y_n)$ where $Y_n$ is a quotient of $X_n$, and the maximal degree $Delta(Y_n)$ is unbounded.
The reason I am interested in this, is that I read in various references that quotients of expanding graphs are expanding graphs. Although it is easy to check that quotients of expanding graphs satisfy the expanding condition for the same constant, it is not clear to me why when taking quotients of an infinite family of expanders the degree should be bounded. In all instances where I have seen this fact to be applied, it turns out that it is, but I was wondering if this is a general fact or not.
Edit: I am especially interested in quotients where all the sets of the partition have the same size.
combinatorics graph-theory
combinatorics graph-theory
asked Dec 17 '18 at 13:15
frafourfrafour
885312
asked Dec 17 '18 at 13:15
frafourfrafour
885312
edited Dec 17 '18 at 16:12
frafour
asked Dec 17 '18 at 13:15
frafourfrafour
885312
asked Dec 17 '18 at 13:15
frafourfrafour
885312
asked Dec 17 '18 at 13:15
frafourfrafour
885312
885312
$begingroup$
Are you limiting the partition we choose to quotient by? It seems like on the one hand, we can take one part of the partition to be a dominating set and the rest to have size 1, and get one vertex with very high degree. On the other hand, if all parts have size at most $t$, then the quotient graph has maximum degree at most $kcdot t$.
$endgroup$
– Misha Lavrov
Dec 17 '18 at 15:18
$begingroup$
@MishaLavrov I just edited the question to make it more specific.
$endgroup$
– frafour
Dec 17 '18 at 16:12
add a comment |
$begingroup$
Are you limiting the partition we choose to quotient by? It seems like on the one hand, we can take one part of the partition to be a dominating set and the rest to have size 1, and get one vertex with very high degree. On the other hand, if all parts have size at most $t$, then the quotient graph has maximum degree at most $kcdot t$.
$endgroup$
– Misha Lavrov
Dec 17 '18 at 15:18
$begingroup$
@MishaLavrov I just edited the question to make it more specific.
$endgroup$
– frafour
Dec 17 '18 at 16:12
$begingroup$
Are you limiting the partition we choose to quotient by? It seems like on the one hand, we can take one part of the partition to be a dominating set and the rest to have size 1, and get one vertex with very high degree. On the other hand, if all parts have size at most $t$, then the quotient graph has maximum degree at most $kcdot t$.
$endgroup$
– Misha Lavrov
Dec 17 '18 at 15:18
$begingroup$
Are you limiting the partition we choose to quotient by? It seems like on the one hand, we can take one part of the partition to be a dominating set and the rest to have size 1, and get one vertex with very high degree. On the other hand, if all parts have size at most $t$, then the quotient graph has maximum degree at most $kcdot t$.
$endgroup$
– Misha Lavrov
Dec 17 '18 at 15:18
$begingroup$
@MishaLavrov I just edited the question to make it more specific.
$endgroup$
– frafour
Dec 17 '18 at 16:12
$begingroup$
@MishaLavrov I just edited the question to make it more specific.
$endgroup$
– frafour
Dec 17 '18 at 16:12
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
If the partition of $X_n$ we use to get $Y_n$ has bounded parts - e.g., each part has size at most $t$ - then $Delta(Y_n) le t cdot Delta(X_n) = tk$, since each part can have at most $tk$ edges out of it.
If the sizes of the parts can be large, then this inequality is not helpful, and $Delta(Y_n)$ may be unbounded. For an extreme example of this, let $X_n$ be an $n times n$ grid graph, wrapping around at the sides: a $4$-regular graph with $n^2$ vertices. Put vertex $(i,j)$ with $0 le i,j < n$ into part $(i + frac{j(j+1)}{2} bmod n)$ of the partition, and quotient by this partition to create $Y_n$.
This is an equitable partition into $n$ parts of size $n$, since for a fixed $j$, the vertices $(0,j), (1,j), dots, (n-1,j)$ are in $n$ different parts. However, there are edges between any two parts of the partition: to find an edge between parts $p$ and $q$ with $p<q$, let $j = q-p-1 bmod n$, and choose $i$ such that $i + frac{j(j+1)}{2} equiv p pmod n$. Then $(i,j)$ is in part $p$ and $(i,j+1)$ is in part $q$.
So in this example, $Y_n$ is the complete graph $K_n$, and $Delta(Y_n)$ is definitely unbounded.
answered Dec 17 '18 at 16:34
Misha LavrovMisha Lavrov
47.7k657107
$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%2f3043922%2fdegree-of-quotient-graph-of-a-regular-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$
If the partition of $X_n$ we use to get $Y_n$ has bounded parts - e.g., each part has size at most $t$ - then $Delta(Y_n) le t cdot Delta(X_n) = tk$, since each part can have at most $tk$ edges out of it.
If the sizes of the parts can be large, then this inequality is not helpful, and $Delta(Y_n)$ may be unbounded. For an extreme example of this, let $X_n$ be an $n times n$ grid graph, wrapping around at the sides: a $4$-regular graph with $n^2$ vertices. Put vertex $(i,j)$ with $0 le i,j < n$ into part $(i + frac{j(j+1)}{2} bmod n)$ of the partition, and quotient by this partition to create $Y_n$.
This is an equitable partition into $n$ parts of size $n$, since for a fixed $j$, the vertices $(0,j), (1,j), dots, (n-1,j)$ are in $n$ different parts. However, there are edges between any two parts of the partition: to find an edge between parts $p$ and $q$ with $p<q$, let $j = q-p-1 bmod n$, and choose $i$ such that $i + frac{j(j+1)}{2} equiv p pmod n$. Then $(i,j)$ is in part $p$ and $(i,j+1)$ is in part $q$.
So in this example, $Y_n$ is the complete graph $K_n$, and $Delta(Y_n)$ is definitely unbounded.
answered Dec 17 '18 at 16:34
Misha LavrovMisha Lavrov
47.7k657107
$endgroup$
add a comment |
$begingroup$
If the partition of $X_n$ we use to get $Y_n$ has bounded parts - e.g., each part has size at most $t$ - then $Delta(Y_n) le t cdot Delta(X_n) = tk$, since each part can have at most $tk$ edges out of it.
If the sizes of the parts can be large, then this inequality is not helpful, and $Delta(Y_n)$ may be unbounded. For an extreme example of this, let $X_n$ be an $n times n$ grid graph, wrapping around at the sides: a $4$-regular graph with $n^2$ vertices. Put vertex $(i,j)$ with $0 le i,j < n$ into part $(i + frac{j(j+1)}{2} bmod n)$ of the partition, and quotient by this partition to create $Y_n$.
This is an equitable partition into $n$ parts of size $n$, since for a fixed $j$, the vertices $(0,j), (1,j), dots, (n-1,j)$ are in $n$ different parts. However, there are edges between any two parts of the partition: to find an edge between parts $p$ and $q$ with $p<q$, let $j = q-p-1 bmod n$, and choose $i$ such that $i + frac{j(j+1)}{2} equiv p pmod n$. Then $(i,j)$ is in part $p$ and $(i,j+1)$ is in part $q$.
So in this example, $Y_n$ is the complete graph $K_n$, and $Delta(Y_n)$ is definitely unbounded.
answered Dec 17 '18 at 16:34
Misha LavrovMisha Lavrov
47.7k657107
$endgroup$
add a comment |
$begingroup$
If the partition of $X_n$ we use to get $Y_n$ has bounded parts - e.g., each part has size at most $t$ - then $Delta(Y_n) le t cdot Delta(X_n) = tk$, since each part can have at most $tk$ edges out of it.
If the sizes of the parts can be large, then this inequality is not helpful, and $Delta(Y_n)$ may be unbounded. For an extreme example of this, let $X_n$ be an $n times n$ grid graph, wrapping around at the sides: a $4$-regular graph with $n^2$ vertices. Put vertex $(i,j)$ with $0 le i,j < n$ into part $(i + frac{j(j+1)}{2} bmod n)$ of the partition, and quotient by this partition to create $Y_n$.
This is an equitable partition into $n$ parts of size $n$, since for a fixed $j$, the vertices $(0,j), (1,j), dots, (n-1,j)$ are in $n$ different parts. However, there are edges between any two parts of the partition: to find an edge between parts $p$ and $q$ with $p<q$, let $j = q-p-1 bmod n$, and choose $i$ such that $i + frac{j(j+1)}{2} equiv p pmod n$. Then $(i,j)$ is in part $p$ and $(i,j+1)$ is in part $q$.
So in this example, $Y_n$ is the complete graph $K_n$, and $Delta(Y_n)$ is definitely unbounded.
answered Dec 17 '18 at 16:34
Misha LavrovMisha Lavrov
47.7k657107
$endgroup$
If the partition of $X_n$ we use to get $Y_n$ has bounded parts - e.g., each part has size at most $t$ - then $Delta(Y_n) le t cdot Delta(X_n) = tk$, since each part can have at most $tk$ edges out of it.
If the sizes of the parts can be large, then this inequality is not helpful, and $Delta(Y_n)$ may be unbounded. For an extreme example of this, let $X_n$ be an $n times n$ grid graph, wrapping around at the sides: a $4$-regular graph with $n^2$ vertices. Put vertex $(i,j)$ with $0 le i,j < n$ into part $(i + frac{j(j+1)}{2} bmod n)$ of the partition, and quotient by this partition to create $Y_n$.
This is an equitable partition into $n$ parts of size $n$, since for a fixed $j$, the vertices $(0,j), (1,j), dots, (n-1,j)$ are in $n$ different parts. However, there are edges between any two parts of the partition: to find an edge between parts $p$ and $q$ with $p<q$, let $j = q-p-1 bmod n$, and choose $i$ such that $i + frac{j(j+1)}{2} equiv p pmod n$. Then $(i,j)$ is in part $p$ and $(i,j+1)$ is in part $q$.
So in this example, $Y_n$ is the complete graph $K_n$, and $Delta(Y_n)$ is definitely unbounded.
answered Dec 17 '18 at 16:34
Misha LavrovMisha Lavrov
47.7k657107
answered Dec 17 '18 at 16:34
Misha LavrovMisha Lavrov
47.7k657107
answered Dec 17 '18 at 16:34
Misha LavrovMisha Lavrov
47.7k657107
answered Dec 17 '18 at 16:34
Misha LavrovMisha Lavrov
47.7k657107
47.7k657107
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%2f3043922%2fdegree-of-quotient-graph-of-a-regular-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
$begingroup$
Are you limiting the partition we choose to quotient by? It seems like on the one hand, we can take one part of the partition to be a dominating set and the rest to have size 1, and get one vertex with very high degree. On the other hand, if all parts have size at most $t$, then the quotient graph has maximum degree at most $kcdot t$.
$endgroup$
– Misha Lavrov
Dec 17 '18 at 15:18
$begingroup$
@MishaLavrov I just edited the question to make it more specific.
$endgroup$
– frafour
Dec 17 '18 at 16:12