Definitions of $epsilon$-regular partition
$begingroup$
I am wondering about the equivalence between two definitions of an $epsilon$-regular partition of a graph.
First of all, if $G$ is a graph and $A$ and $B$ are subsets of its vertex set, the density of edges between $A$ and $B$ is defined as
$$d(A,B)=frac{|E(A,B)|}{|A||B|},$$
where $|E(A,B)|$ is the number of edges between $A$ and $B$.
Given some $epsilon>0$, the pair $(A,B)$ is said to be $epsilon$-regular if, for every $A'subseteq A$ and $B'subseteq B$ with $|A'|geq epsilon |A|$ and $|B'|geq epsilon |B|$, we have that
$$|d(A',B')-d(A,B)|leq epsilon.$$
Now, what we want to do next is to define what it means for a partition of the vertex set to be $epsilon$-regular, and I have found two different definitions (from different sources).
Definition 1. Given a graph $G$ on $n$ vertices and an $epsilon>0$, a partition ${X_1, dots, X_k}$ of its vertex set is $epsilon$-regular if
$$sum frac{|X_i||X_j|}{n^2} leq epsilon,$$
where the sum is taken over all pairs $(X_i,X_j)$ which are not $epsilon$-regular.
Definition 2. Given a graph $G$ on $n$ vertices and an $epsilon>0$, a partition ${V_0, V_1, dots, V_k}$ of its vertex set $V$ is $epsilon$-regular if:
- $|V_0|leq epsilon |V|$
- $|V_1| = dots = |V_k|$
- at most $epsilonbinom{k}{2}$ pairs $(V_i,V_j)$ are not $epsilon$-regular.
I am assuming that these definitions are equivalent, and they are both used in various different sources in order to prove Szemeredi's regularity lemma, but I cannot see if that is indeed true.
Can anyone help?
Any help is much appreciated.
graph-theory definition
asked Dec 8 '18 at 15:49
IlefenIlefen
485215
$endgroup$
add a comment |
$begingroup$
I am wondering about the equivalence between two definitions of an $epsilon$-regular partition of a graph.
First of all, if $G$ is a graph and $A$ and $B$ are subsets of its vertex set, the density of edges between $A$ and $B$ is defined as
$$d(A,B)=frac{|E(A,B)|}{|A||B|},$$
where $|E(A,B)|$ is the number of edges between $A$ and $B$.
Given some $epsilon>0$, the pair $(A,B)$ is said to be $epsilon$-regular if, for every $A'subseteq A$ and $B'subseteq B$ with $|A'|geq epsilon |A|$ and $|B'|geq epsilon |B|$, we have that
$$|d(A',B')-d(A,B)|leq epsilon.$$
Now, what we want to do next is to define what it means for a partition of the vertex set to be $epsilon$-regular, and I have found two different definitions (from different sources).
Definition 1. Given a graph $G$ on $n$ vertices and an $epsilon>0$, a partition ${X_1, dots, X_k}$ of its vertex set is $epsilon$-regular if
$$sum frac{|X_i||X_j|}{n^2} leq epsilon,$$
where the sum is taken over all pairs $(X_i,X_j)$ which are not $epsilon$-regular.
Definition 2. Given a graph $G$ on $n$ vertices and an $epsilon>0$, a partition ${V_0, V_1, dots, V_k}$ of its vertex set $V$ is $epsilon$-regular if:
- $|V_0|leq epsilon |V|$
- $|V_1| = dots = |V_k|$
- at most $epsilonbinom{k}{2}$ pairs $(V_i,V_j)$ are not $epsilon$-regular.
I am assuming that these definitions are equivalent, and they are both used in various different sources in order to prove Szemeredi's regularity lemma, but I cannot see if that is indeed true.
Can anyone help?
Any help is much appreciated.
graph-theory definition
asked Dec 8 '18 at 15:49
IlefenIlefen
485215
$endgroup$
add a comment |
$begingroup$
I am wondering about the equivalence between two definitions of an $epsilon$-regular partition of a graph.
First of all, if $G$ is a graph and $A$ and $B$ are subsets of its vertex set, the density of edges between $A$ and $B$ is defined as
$$d(A,B)=frac{|E(A,B)|}{|A||B|},$$
where $|E(A,B)|$ is the number of edges between $A$ and $B$.
Given some $epsilon>0$, the pair $(A,B)$ is said to be $epsilon$-regular if, for every $A'subseteq A$ and $B'subseteq B$ with $|A'|geq epsilon |A|$ and $|B'|geq epsilon |B|$, we have that
$$|d(A',B')-d(A,B)|leq epsilon.$$
Now, what we want to do next is to define what it means for a partition of the vertex set to be $epsilon$-regular, and I have found two different definitions (from different sources).
Definition 1. Given a graph $G$ on $n$ vertices and an $epsilon>0$, a partition ${X_1, dots, X_k}$ of its vertex set is $epsilon$-regular if
$$sum frac{|X_i||X_j|}{n^2} leq epsilon,$$
where the sum is taken over all pairs $(X_i,X_j)$ which are not $epsilon$-regular.
Definition 2. Given a graph $G$ on $n$ vertices and an $epsilon>0$, a partition ${V_0, V_1, dots, V_k}$ of its vertex set $V$ is $epsilon$-regular if:
- $|V_0|leq epsilon |V|$
- $|V_1| = dots = |V_k|$
- at most $epsilonbinom{k}{2}$ pairs $(V_i,V_j)$ are not $epsilon$-regular.
I am assuming that these definitions are equivalent, and they are both used in various different sources in order to prove Szemeredi's regularity lemma, but I cannot see if that is indeed true.
Can anyone help?
Any help is much appreciated.
graph-theory definition
asked Dec 8 '18 at 15:49
IlefenIlefen
485215
$endgroup$
I am wondering about the equivalence between two definitions of an $epsilon$-regular partition of a graph.
First of all, if $G$ is a graph and $A$ and $B$ are subsets of its vertex set, the density of edges between $A$ and $B$ is defined as
$$d(A,B)=frac{|E(A,B)|}{|A||B|},$$
where $|E(A,B)|$ is the number of edges between $A$ and $B$.
Given some $epsilon>0$, the pair $(A,B)$ is said to be $epsilon$-regular if, for every $A'subseteq A$ and $B'subseteq B$ with $|A'|geq epsilon |A|$ and $|B'|geq epsilon |B|$, we have that
$$|d(A',B')-d(A,B)|leq epsilon.$$
Now, what we want to do next is to define what it means for a partition of the vertex set to be $epsilon$-regular, and I have found two different definitions (from different sources).
Definition 1. Given a graph $G$ on $n$ vertices and an $epsilon>0$, a partition ${X_1, dots, X_k}$ of its vertex set is $epsilon$-regular if
$$sum frac{|X_i||X_j|}{n^2} leq epsilon,$$
where the sum is taken over all pairs $(X_i,X_j)$ which are not $epsilon$-regular.
Definition 2. Given a graph $G$ on $n$ vertices and an $epsilon>0$, a partition ${V_0, V_1, dots, V_k}$ of its vertex set $V$ is $epsilon$-regular if:
- $|V_0|leq epsilon |V|$
- $|V_1| = dots = |V_k|$
- at most $epsilonbinom{k}{2}$ pairs $(V_i,V_j)$ are not $epsilon$-regular.
I am assuming that these definitions are equivalent, and they are both used in various different sources in order to prove Szemeredi's regularity lemma, but I cannot see if that is indeed true.
Can anyone help?
Any help is much appreciated.
graph-theory definition
graph-theory definition
asked Dec 8 '18 at 15:49
IlefenIlefen
485215
asked Dec 8 '18 at 15:49
IlefenIlefen
485215
asked Dec 8 '18 at 15:49
IlefenIlefen
485215
asked Dec 8 '18 at 15:49
IlefenIlefen
485215
asked Dec 8 '18 at 15:49
IlefenIlefen
485215
485215
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
It is easy to check that for each $epsilon>0$ each graph, which is $epsilon$-regular according to Definition 2 is $epsilon$-regular according to Definition 1. But not conversely, because according to Definition 1, any partition of any finite graph is $1$-regular, whereas Definition 2 imposes additional restrictions on the sizes of partition members.
answered Dec 9 '18 at 7:12
Alex RavskyAlex Ravsky
42.6k32383
$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%2f3031269%2fdefinitions-of-epsilon-regular-partition%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$
It is easy to check that for each $epsilon>0$ each graph, which is $epsilon$-regular according to Definition 2 is $epsilon$-regular according to Definition 1. But not conversely, because according to Definition 1, any partition of any finite graph is $1$-regular, whereas Definition 2 imposes additional restrictions on the sizes of partition members.
answered Dec 9 '18 at 7:12
Alex RavskyAlex Ravsky
42.6k32383
$endgroup$
add a comment |
$begingroup$
It is easy to check that for each $epsilon>0$ each graph, which is $epsilon$-regular according to Definition 2 is $epsilon$-regular according to Definition 1. But not conversely, because according to Definition 1, any partition of any finite graph is $1$-regular, whereas Definition 2 imposes additional restrictions on the sizes of partition members.
answered Dec 9 '18 at 7:12
Alex RavskyAlex Ravsky
42.6k32383
$endgroup$
add a comment |
$begingroup$
It is easy to check that for each $epsilon>0$ each graph, which is $epsilon$-regular according to Definition 2 is $epsilon$-regular according to Definition 1. But not conversely, because according to Definition 1, any partition of any finite graph is $1$-regular, whereas Definition 2 imposes additional restrictions on the sizes of partition members.
answered Dec 9 '18 at 7:12
Alex RavskyAlex Ravsky
42.6k32383
$endgroup$
It is easy to check that for each $epsilon>0$ each graph, which is $epsilon$-regular according to Definition 2 is $epsilon$-regular according to Definition 1. But not conversely, because according to Definition 1, any partition of any finite graph is $1$-regular, whereas Definition 2 imposes additional restrictions on the sizes of partition members.
answered Dec 9 '18 at 7:12
Alex RavskyAlex Ravsky
42.6k32383
answered Dec 9 '18 at 7:12
Alex RavskyAlex Ravsky
42.6k32383
answered Dec 9 '18 at 7:12
Alex RavskyAlex Ravsky
42.6k32383
answered Dec 9 '18 at 7:12
Alex RavskyAlex Ravsky
42.6k32383
42.6k32383
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%2f3031269%2fdefinitions-of-epsilon-regular-partition%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
