Mixing
Show that there are at most $n^2$ roads.
$begingroup$
There are $2n$ places. If place $a$ and place $b$ has a road between them and place $b$ and place $c$ has a road between them, then there is no road between place $a$ and place $c$.
Now show that there are at most $n^2$ roads.
I observed that if we also include the odd number of places during examination of the total number of roads, a pattern is found. When total number of places is 0, 1, 2, 3, 4, 5, 6, 7; the maximum number of paths are 0, 0, 1, 2, 4, 6, 9, 12 respectively. The differences between the maximum number of paths are like 0, 1, 1, 2, 2, 3, 3 respectively.
Another approach can be: We can choose two places in $^nC_2$ ways and then subtract $^nC_3$ (every triangle formed). I am not sure of this.
combinatorics graph-theory
asked Jan 11 at 11:09
tomriddle99tomriddle99
1157
$endgroup$
add a comment |
$begingroup$
There are $2n$ places. If place $a$ and place $b$ has a road between them and place $b$ and place $c$ has a road between them, then there is no road between place $a$ and place $c$.
Now show that there are at most $n^2$ roads.
I observed that if we also include the odd number of places during examination of the total number of roads, a pattern is found. When total number of places is 0, 1, 2, 3, 4, 5, 6, 7; the maximum number of paths are 0, 0, 1, 2, 4, 6, 9, 12 respectively. The differences between the maximum number of paths are like 0, 1, 1, 2, 2, 3, 3 respectively.
Another approach can be: We can choose two places in $^nC_2$ ways and then subtract $^nC_3$ (every triangle formed). I am not sure of this.
combinatorics graph-theory
asked Jan 11 at 11:09
tomriddle99tomriddle99
1157
$endgroup$
add a comment |
$begingroup$
There are $2n$ places. If place $a$ and place $b$ has a road between them and place $b$ and place $c$ has a road between them, then there is no road between place $a$ and place $c$.
Now show that there are at most $n^2$ roads.
I observed that if we also include the odd number of places during examination of the total number of roads, a pattern is found. When total number of places is 0, 1, 2, 3, 4, 5, 6, 7; the maximum number of paths are 0, 0, 1, 2, 4, 6, 9, 12 respectively. The differences between the maximum number of paths are like 0, 1, 1, 2, 2, 3, 3 respectively.
Another approach can be: We can choose two places in $^nC_2$ ways and then subtract $^nC_3$ (every triangle formed). I am not sure of this.
combinatorics graph-theory
asked Jan 11 at 11:09
tomriddle99tomriddle99
1157
$endgroup$
There are $2n$ places. If place $a$ and place $b$ has a road between them and place $b$ and place $c$ has a road between them, then there is no road between place $a$ and place $c$.
Now show that there are at most $n^2$ roads.
I observed that if we also include the odd number of places during examination of the total number of roads, a pattern is found. When total number of places is 0, 1, 2, 3, 4, 5, 6, 7; the maximum number of paths are 0, 0, 1, 2, 4, 6, 9, 12 respectively. The differences between the maximum number of paths are like 0, 1, 1, 2, 2, 3, 3 respectively.
Another approach can be: We can choose two places in $^nC_2$ ways and then subtract $^nC_3$ (every triangle formed). I am not sure of this.
combinatorics graph-theory
combinatorics graph-theory
asked Jan 11 at 11:09
tomriddle99tomriddle99
1157
asked Jan 11 at 11:09
tomriddle99tomriddle99
1157
asked Jan 11 at 11:09
tomriddle99tomriddle99
1157
asked Jan 11 at 11:09
tomriddle99tomriddle99
1157
asked Jan 11 at 11:09
tomriddle99tomriddle99
1157
1157
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Let us form a graph $V$ where $V= {1,2,ldots,2n}$, and $ileftrightarrow j$ if $i$-th place and $j$-th place are connected by a road between them. Each place is not connected with itself. Let $d_i$ denote the number of $j$ such that $ileftrightarrow j$. Then we can see that the number of edges is $$N = frac{1}{2}sumlimits_{iin V}d_i.$$ Our goal is to show $Nle n^2$. Let us define
$$
M=sum_{ileftrightarrow j}sum_{kin V}left(1_{ileftrightarrow k}+1_{jleftrightarrow
k}right)
$$ where $1_{jleftrightarrow k}=1$ if $jleftrightarrow k$ and is $0$ otherwise. By the assumption, there is no $k$ such that $ 1_{ileftrightarrow k}+1_{jleftrightarrow
k}=2.$ This gives
$$
Mle sum_{ileftrightarrow j}sum_{kin V}1=2nsum_{iin V} d_i= 4nN.
$$ On the other hand, we have
$$begin{eqnarray}
M=sum_{kin V}sum_{ileftrightarrow j}left(1_{ileftrightarrow k}+1_{jleftrightarrow
k}right)&=&sum_{kin V}sum_{ileftrightarrow j}1_{ileftrightarrow k} +sum_{kin V}sum_{ileftrightarrow j}1_{jleftrightarrow k}\
&=&2sum_{kin V}sum_{ileftrightarrow j}1_{ileftrightarrow k}\
&=&2sum_{kin V}sum_{iin V}1_{ileftrightarrow k}sum_{j:ileftrightarrow j}1\
&=&2sum_{kin V}sum_{iin V}1_{ileftrightarrow k}cdot d_i\
&=&2sum_{iin V}d_isum_{kin V}1_{ileftrightarrow k}\
&=&2sum_{iin V}d_icdot d_i = 2sum_{iin V} d_i^2.
end{eqnarray}$$ By Cauchy-Schwarz, we have
$$
ncdot M=|V|cdotsum_{iin V} d_i^2ge left(sum_{iin V}d_iright)^2=4N^2
$$ Since $Mle 4nN$, it follows
$$
4N^2le 4n^2N,
$$ that is,
$$
Nle n^2
$$as desired.
answered Jan 11 at 12:12
SongSong
12.2k630
$endgroup$
add a comment |
$begingroup$
It's equivalent to prove that in graph with $2n$ vertices without triangles there at most $n^2$ edges. However, it's a case of Turán's theorem (about $K_{r}$-free graphs) for $r=3$. You can several proofs of this theorem in Proofs from THE BOOK by Aigner and Ziegler.
https://en.m.wikipedia.org/wiki/Turán%27s_theorem
answered Jan 11 at 11:20
richrowrichrow
1736
$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%2f3069723%2fshow-that-there-are-at-most-n2-roads%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Let us form a graph $V$ where $V= {1,2,ldots,2n}$, and $ileftrightarrow j$ if $i$-th place and $j$-th place are connected by a road between them. Each place is not connected with itself. Let $d_i$ denote the number of $j$ such that $ileftrightarrow j$. Then we can see that the number of edges is $$N = frac{1}{2}sumlimits_{iin V}d_i.$$ Our goal is to show $Nle n^2$. Let us define
$$
M=sum_{ileftrightarrow j}sum_{kin V}left(1_{ileftrightarrow k}+1_{jleftrightarrow
k}right)
$$ where $1_{jleftrightarrow k}=1$ if $jleftrightarrow k$ and is $0$ otherwise. By the assumption, there is no $k$ such that $ 1_{ileftrightarrow k}+1_{jleftrightarrow
k}=2.$ This gives
$$
Mle sum_{ileftrightarrow j}sum_{kin V}1=2nsum_{iin V} d_i= 4nN.
$$ On the other hand, we have
$$begin{eqnarray}
M=sum_{kin V}sum_{ileftrightarrow j}left(1_{ileftrightarrow k}+1_{jleftrightarrow
k}right)&=&sum_{kin V}sum_{ileftrightarrow j}1_{ileftrightarrow k} +sum_{kin V}sum_{ileftrightarrow j}1_{jleftrightarrow k}\
&=&2sum_{kin V}sum_{ileftrightarrow j}1_{ileftrightarrow k}\
&=&2sum_{kin V}sum_{iin V}1_{ileftrightarrow k}sum_{j:ileftrightarrow j}1\
&=&2sum_{kin V}sum_{iin V}1_{ileftrightarrow k}cdot d_i\
&=&2sum_{iin V}d_isum_{kin V}1_{ileftrightarrow k}\
&=&2sum_{iin V}d_icdot d_i = 2sum_{iin V} d_i^2.
end{eqnarray}$$ By Cauchy-Schwarz, we have
$$
ncdot M=|V|cdotsum_{iin V} d_i^2ge left(sum_{iin V}d_iright)^2=4N^2
$$ Since $Mle 4nN$, it follows
$$
4N^2le 4n^2N,
$$ that is,
$$
Nle n^2
$$as desired.
answered Jan 11 at 12:12
SongSong
12.2k630
$endgroup$
add a comment |
$begingroup$
Let us form a graph $V$ where $V= {1,2,ldots,2n}$, and $ileftrightarrow j$ if $i$-th place and $j$-th place are connected by a road between them. Each place is not connected with itself. Let $d_i$ denote the number of $j$ such that $ileftrightarrow j$. Then we can see that the number of edges is $$N = frac{1}{2}sumlimits_{iin V}d_i.$$ Our goal is to show $Nle n^2$. Let us define
$$
M=sum_{ileftrightarrow j}sum_{kin V}left(1_{ileftrightarrow k}+1_{jleftrightarrow
k}right)
$$ where $1_{jleftrightarrow k}=1$ if $jleftrightarrow k$ and is $0$ otherwise. By the assumption, there is no $k$ such that $ 1_{ileftrightarrow k}+1_{jleftrightarrow
k}=2.$ This gives
$$
Mle sum_{ileftrightarrow j}sum_{kin V}1=2nsum_{iin V} d_i= 4nN.
$$ On the other hand, we have
$$begin{eqnarray}
M=sum_{kin V}sum_{ileftrightarrow j}left(1_{ileftrightarrow k}+1_{jleftrightarrow
k}right)&=&sum_{kin V}sum_{ileftrightarrow j}1_{ileftrightarrow k} +sum_{kin V}sum_{ileftrightarrow j}1_{jleftrightarrow k}\
&=&2sum_{kin V}sum_{ileftrightarrow j}1_{ileftrightarrow k}\
&=&2sum_{kin V}sum_{iin V}1_{ileftrightarrow k}sum_{j:ileftrightarrow j}1\
&=&2sum_{kin V}sum_{iin V}1_{ileftrightarrow k}cdot d_i\
&=&2sum_{iin V}d_isum_{kin V}1_{ileftrightarrow k}\
&=&2sum_{iin V}d_icdot d_i = 2sum_{iin V} d_i^2.
end{eqnarray}$$ By Cauchy-Schwarz, we have
$$
ncdot M=|V|cdotsum_{iin V} d_i^2ge left(sum_{iin V}d_iright)^2=4N^2
$$ Since $Mle 4nN$, it follows
$$
4N^2le 4n^2N,
$$ that is,
$$
Nle n^2
$$as desired.
answered Jan 11 at 12:12
SongSong
12.2k630
$endgroup$
add a comment |
$begingroup$
Let us form a graph $V$ where $V= {1,2,ldots,2n}$, and $ileftrightarrow j$ if $i$-th place and $j$-th place are connected by a road between them. Each place is not connected with itself. Let $d_i$ denote the number of $j$ such that $ileftrightarrow j$. Then we can see that the number of edges is $$N = frac{1}{2}sumlimits_{iin V}d_i.$$ Our goal is to show $Nle n^2$. Let us define
$$
M=sum_{ileftrightarrow j}sum_{kin V}left(1_{ileftrightarrow k}+1_{jleftrightarrow
k}right)
$$ where $1_{jleftrightarrow k}=1$ if $jleftrightarrow k$ and is $0$ otherwise. By the assumption, there is no $k$ such that $ 1_{ileftrightarrow k}+1_{jleftrightarrow
k}=2.$ This gives
$$
Mle sum_{ileftrightarrow j}sum_{kin V}1=2nsum_{iin V} d_i= 4nN.
$$ On the other hand, we have
$$begin{eqnarray}
M=sum_{kin V}sum_{ileftrightarrow j}left(1_{ileftrightarrow k}+1_{jleftrightarrow
k}right)&=&sum_{kin V}sum_{ileftrightarrow j}1_{ileftrightarrow k} +sum_{kin V}sum_{ileftrightarrow j}1_{jleftrightarrow k}\
&=&2sum_{kin V}sum_{ileftrightarrow j}1_{ileftrightarrow k}\
&=&2sum_{kin V}sum_{iin V}1_{ileftrightarrow k}sum_{j:ileftrightarrow j}1\
&=&2sum_{kin V}sum_{iin V}1_{ileftrightarrow k}cdot d_i\
&=&2sum_{iin V}d_isum_{kin V}1_{ileftrightarrow k}\
&=&2sum_{iin V}d_icdot d_i = 2sum_{iin V} d_i^2.
end{eqnarray}$$ By Cauchy-Schwarz, we have
$$
ncdot M=|V|cdotsum_{iin V} d_i^2ge left(sum_{iin V}d_iright)^2=4N^2
$$ Since $Mle 4nN$, it follows
$$
4N^2le 4n^2N,
$$ that is,
$$
Nle n^2
$$as desired.
answered Jan 11 at 12:12
SongSong
12.2k630
$endgroup$
Let us form a graph $V$ where $V= {1,2,ldots,2n}$, and $ileftrightarrow j$ if $i$-th place and $j$-th place are connected by a road between them. Each place is not connected with itself. Let $d_i$ denote the number of $j$ such that $ileftrightarrow j$. Then we can see that the number of edges is $$N = frac{1}{2}sumlimits_{iin V}d_i.$$ Our goal is to show $Nle n^2$. Let us define
$$
M=sum_{ileftrightarrow j}sum_{kin V}left(1_{ileftrightarrow k}+1_{jleftrightarrow
k}right)
$$ where $1_{jleftrightarrow k}=1$ if $jleftrightarrow k$ and is $0$ otherwise. By the assumption, there is no $k$ such that $ 1_{ileftrightarrow k}+1_{jleftrightarrow
k}=2.$ This gives
$$
Mle sum_{ileftrightarrow j}sum_{kin V}1=2nsum_{iin V} d_i= 4nN.
$$ On the other hand, we have
$$begin{eqnarray}
M=sum_{kin V}sum_{ileftrightarrow j}left(1_{ileftrightarrow k}+1_{jleftrightarrow
k}right)&=&sum_{kin V}sum_{ileftrightarrow j}1_{ileftrightarrow k} +sum_{kin V}sum_{ileftrightarrow j}1_{jleftrightarrow k}\
&=&2sum_{kin V}sum_{ileftrightarrow j}1_{ileftrightarrow k}\
&=&2sum_{kin V}sum_{iin V}1_{ileftrightarrow k}sum_{j:ileftrightarrow j}1\
&=&2sum_{kin V}sum_{iin V}1_{ileftrightarrow k}cdot d_i\
&=&2sum_{iin V}d_isum_{kin V}1_{ileftrightarrow k}\
&=&2sum_{iin V}d_icdot d_i = 2sum_{iin V} d_i^2.
end{eqnarray}$$ By Cauchy-Schwarz, we have
$$
ncdot M=|V|cdotsum_{iin V} d_i^2ge left(sum_{iin V}d_iright)^2=4N^2
$$ Since $Mle 4nN$, it follows
$$
4N^2le 4n^2N,
$$ that is,
$$
Nle n^2
$$as desired.
answered Jan 11 at 12:12
SongSong
12.2k630
answered Jan 11 at 12:12
SongSong
12.2k630
answered Jan 11 at 12:12
SongSong
12.2k630
answered Jan 11 at 12:12
SongSong
12.2k630
12.2k630
add a comment |
add a comment |
$begingroup$
It's equivalent to prove that in graph with $2n$ vertices without triangles there at most $n^2$ edges. However, it's a case of Turán's theorem (about $K_{r}$-free graphs) for $r=3$. You can several proofs of this theorem in Proofs from THE BOOK by Aigner and Ziegler.
https://en.m.wikipedia.org/wiki/Turán%27s_theorem
answered Jan 11 at 11:20
richrowrichrow
1736
$endgroup$
add a comment |
$begingroup$
It's equivalent to prove that in graph with $2n$ vertices without triangles there at most $n^2$ edges. However, it's a case of Turán's theorem (about $K_{r}$-free graphs) for $r=3$. You can several proofs of this theorem in Proofs from THE BOOK by Aigner and Ziegler.
https://en.m.wikipedia.org/wiki/Turán%27s_theorem
answered Jan 11 at 11:20
richrowrichrow
1736
$endgroup$
add a comment |
$begingroup$
It's equivalent to prove that in graph with $2n$ vertices without triangles there at most $n^2$ edges. However, it's a case of Turán's theorem (about $K_{r}$-free graphs) for $r=3$. You can several proofs of this theorem in Proofs from THE BOOK by Aigner and Ziegler.
https://en.m.wikipedia.org/wiki/Turán%27s_theorem
answered Jan 11 at 11:20
richrowrichrow
1736
$endgroup$
It's equivalent to prove that in graph with $2n$ vertices without triangles there at most $n^2$ edges. However, it's a case of Turán's theorem (about $K_{r}$-free graphs) for $r=3$. You can several proofs of this theorem in Proofs from THE BOOK by Aigner and Ziegler.
https://en.m.wikipedia.org/wiki/Turán%27s_theorem
answered Jan 11 at 11:20
richrowrichrow
1736
answered Jan 11 at 11:20
richrowrichrow
1736
answered Jan 11 at 11:20
richrowrichrow
1736
answered Jan 11 at 11:20
richrowrichrow
1736
1736
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%2f3069723%2fshow-that-there-are-at-most-n2-roads%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
