Number of chords in a $n$-gon if each chord is crossed at most $k$ times
$begingroup$
Say we have a $n$-gon where we denote the points by $v_1, dots, v_n$.
If we allow each chord to have at most $k$ crossings, how many chords can we put into the $n$-gon (denoted as $c(n,k)$).
Obviously, if we choose $k$ large enough, we can always put in all $frac{n cdot (n-3)}{2}$ possible chords.
One can solve this problem for small $n$ and $k$ with an integer linear programm (I can post the code if somebody would be interested) which yields
Do you think there is any hope to solve this problem with a formula?
Actual Code (Python, using the librar pulp):
Pastebin Link to the Code
"Code" Explained:
Initialize a binary variable for each possible chord (e.g. $c_{1,3}$ is the chord incident to $v_1$ and $v_3$).
Define for each variable $c_{i,j}$ the set of crossing chords $S(c_{i,j})$, that is all chords $c_{q,p}$ with either $i < q < j$ and $ j < p leq n$ or $1 leq q < i$ and $ i < p < j$
- maximize the sum over all chords
- for each possible chord $c_{i,j}$ we have the constraint that
$n^2 cdot c_{i,j} + | S(c_{i,j})| leq n^2 + k$
(which implies that if $c_{i,j}$ exists, at most k edges that cross $c_{i,j}$ exist, but in the absence of $c_{i,j}$ the constraint is never active)
For even $n$, if $k geq (frac{n-2}{2})^2$, then we can put in all chords.
Simlarly for odd $n$ this is guaranteed for $k geq (frac{n-1}{2} cdot frac{n-3}{2})$.
Example calculations for $c(n,k)$:
begin{array}{c|rrrrrrrrrrrrr}
{_n,backslash, ^k} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \
hline
4 & 1 & 2 & & & & & & & & & & & \
5 & 2 & 3 & 5 & & & & & & & & & & \
6 & 3 & 5 & 6 & 8 & 9 & & & & & & & & \
7 & 4 & 6 & 8 & 9 & 11 & 12 & 14 & & & & & & \
8 & 5 & 8 & 11 & 11 & 13 & 14 & 16 & 18 & 19 & 20 & & & \
9 & 6 & 9 & 12 & 14 & 15 & 17 & 18 & 20 & 22 & 23 & 24 & 25 & 27
end{array}
Interesting observation : $c(8,2) = c(8,3)$
combinatorics graph-theory polygons
asked Jul 21 '18 at 19:06
MrLemmingMrLemming
364
$endgroup$
|
show 7 more comments
$begingroup$
Say we have a $n$-gon where we denote the points by $v_1, dots, v_n$.
If we allow each chord to have at most $k$ crossings, how many chords can we put into the $n$-gon (denoted as $c(n,k)$).
Obviously, if we choose $k$ large enough, we can always put in all $frac{n cdot (n-3)}{2}$ possible chords.
One can solve this problem for small $n$ and $k$ with an integer linear programm (I can post the code if somebody would be interested) which yields
Do you think there is any hope to solve this problem with a formula?
Actual Code (Python, using the librar pulp):
Pastebin Link to the Code
"Code" Explained:
Initialize a binary variable for each possible chord (e.g. $c_{1,3}$ is the chord incident to $v_1$ and $v_3$).
Define for each variable $c_{i,j}$ the set of crossing chords $S(c_{i,j})$, that is all chords $c_{q,p}$ with either $i < q < j$ and $ j < p leq n$ or $1 leq q < i$ and $ i < p < j$
- maximize the sum over all chords
- for each possible chord $c_{i,j}$ we have the constraint that
$n^2 cdot c_{i,j} + | S(c_{i,j})| leq n^2 + k$
(which implies that if $c_{i,j}$ exists, at most k edges that cross $c_{i,j}$ exist, but in the absence of $c_{i,j}$ the constraint is never active)
For even $n$, if $k geq (frac{n-2}{2})^2$, then we can put in all chords.
Simlarly for odd $n$ this is guaranteed for $k geq (frac{n-1}{2} cdot frac{n-3}{2})$.
Example calculations for $c(n,k)$:
begin{array}{c|rrrrrrrrrrrrr}
{_n,backslash, ^k} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \
hline
4 & 1 & 2 & & & & & & & & & & & \
5 & 2 & 3 & 5 & & & & & & & & & & \
6 & 3 & 5 & 6 & 8 & 9 & & & & & & & & \
7 & 4 & 6 & 8 & 9 & 11 & 12 & 14 & & & & & & \
8 & 5 & 8 & 11 & 11 & 13 & 14 & 16 & 18 & 19 & 20 & & & \
9 & 6 & 9 & 12 & 14 & 15 & 17 & 18 & 20 & 22 & 23 & 24 & 25 & 27
end{array}
Interesting observation : $c(8,2) = c(8,3)$
combinatorics graph-theory polygons
asked Jul 21 '18 at 19:06
MrLemmingMrLemming
364
$endgroup$
1
$begingroup$
The code would be good; but more results would be even better, so people who can't run the code could also use them. I get the impression that $c(n,1)=n-2$.
$endgroup$
– joriki
Jul 21 '18 at 19:21
1
$begingroup$
@joriki $c(6,1)geq 5$, though. I have $c(2n,1)geq 3n-4$.
$endgroup$
– Batominovski
Jul 21 '18 at 19:30
1
$begingroup$
And $c(2n+1,1)geq 3n-3$.
$endgroup$
– Batominovski
Jul 21 '18 at 19:36
1
$begingroup$
@joriki Let $ABCDEF$ be a cyclic hexagon. Draw $AC$, $BD$, $AD$, $DF$, and $EA$.
$endgroup$
– Batominovski
Jul 21 '18 at 19:43
1
$begingroup$
“if we choose $k$ large enough, we can always put in all $frac{n cdot (n-3)}{2}$ possible chords”. This is possible iff $kge ab$ for each $1le a,b$ with $a+b=n-2$, that is iff $kge lfloor n^2/4rfloor-n+1$.
$endgroup$
– Alex Ravsky
Dec 28 '18 at 10:02
|
show 7 more comments
$begingroup$
Say we have a $n$-gon where we denote the points by $v_1, dots, v_n$.
If we allow each chord to have at most $k$ crossings, how many chords can we put into the $n$-gon (denoted as $c(n,k)$).
Obviously, if we choose $k$ large enough, we can always put in all $frac{n cdot (n-3)}{2}$ possible chords.
One can solve this problem for small $n$ and $k$ with an integer linear programm (I can post the code if somebody would be interested) which yields
Do you think there is any hope to solve this problem with a formula?
Actual Code (Python, using the librar pulp):
Pastebin Link to the Code
"Code" Explained:
Initialize a binary variable for each possible chord (e.g. $c_{1,3}$ is the chord incident to $v_1$ and $v_3$).
Define for each variable $c_{i,j}$ the set of crossing chords $S(c_{i,j})$, that is all chords $c_{q,p}$ with either $i < q < j$ and $ j < p leq n$ or $1 leq q < i$ and $ i < p < j$
- maximize the sum over all chords
- for each possible chord $c_{i,j}$ we have the constraint that
$n^2 cdot c_{i,j} + | S(c_{i,j})| leq n^2 + k$
(which implies that if $c_{i,j}$ exists, at most k edges that cross $c_{i,j}$ exist, but in the absence of $c_{i,j}$ the constraint is never active)
For even $n$, if $k geq (frac{n-2}{2})^2$, then we can put in all chords.
Simlarly for odd $n$ this is guaranteed for $k geq (frac{n-1}{2} cdot frac{n-3}{2})$.
Example calculations for $c(n,k)$:
begin{array}{c|rrrrrrrrrrrrr}
{_n,backslash, ^k} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \
hline
4 & 1 & 2 & & & & & & & & & & & \
5 & 2 & 3 & 5 & & & & & & & & & & \
6 & 3 & 5 & 6 & 8 & 9 & & & & & & & & \
7 & 4 & 6 & 8 & 9 & 11 & 12 & 14 & & & & & & \
8 & 5 & 8 & 11 & 11 & 13 & 14 & 16 & 18 & 19 & 20 & & & \
9 & 6 & 9 & 12 & 14 & 15 & 17 & 18 & 20 & 22 & 23 & 24 & 25 & 27
end{array}
Interesting observation : $c(8,2) = c(8,3)$
combinatorics graph-theory polygons
asked Jul 21 '18 at 19:06
MrLemmingMrLemming
364
$endgroup$
Say we have a $n$-gon where we denote the points by $v_1, dots, v_n$.
If we allow each chord to have at most $k$ crossings, how many chords can we put into the $n$-gon (denoted as $c(n,k)$).
Obviously, if we choose $k$ large enough, we can always put in all $frac{n cdot (n-3)}{2}$ possible chords.
One can solve this problem for small $n$ and $k$ with an integer linear programm (I can post the code if somebody would be interested) which yields
Do you think there is any hope to solve this problem with a formula?
Actual Code (Python, using the librar pulp):
Pastebin Link to the Code
"Code" Explained:
Initialize a binary variable for each possible chord (e.g. $c_{1,3}$ is the chord incident to $v_1$ and $v_3$).
Define for each variable $c_{i,j}$ the set of crossing chords $S(c_{i,j})$, that is all chords $c_{q,p}$ with either $i < q < j$ and $ j < p leq n$ or $1 leq q < i$ and $ i < p < j$
- maximize the sum over all chords
- for each possible chord $c_{i,j}$ we have the constraint that
$n^2 cdot c_{i,j} + | S(c_{i,j})| leq n^2 + k$
(which implies that if $c_{i,j}$ exists, at most k edges that cross $c_{i,j}$ exist, but in the absence of $c_{i,j}$ the constraint is never active)
For even $n$, if $k geq (frac{n-2}{2})^2$, then we can put in all chords.
Simlarly for odd $n$ this is guaranteed for $k geq (frac{n-1}{2} cdot frac{n-3}{2})$.
Example calculations for $c(n,k)$:
begin{array}{c|rrrrrrrrrrrrr}
{_n,backslash, ^k} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \
hline
4 & 1 & 2 & & & & & & & & & & & \
5 & 2 & 3 & 5 & & & & & & & & & & \
6 & 3 & 5 & 6 & 8 & 9 & & & & & & & & \
7 & 4 & 6 & 8 & 9 & 11 & 12 & 14 & & & & & & \
8 & 5 & 8 & 11 & 11 & 13 & 14 & 16 & 18 & 19 & 20 & & & \
9 & 6 & 9 & 12 & 14 & 15 & 17 & 18 & 20 & 22 & 23 & 24 & 25 & 27
end{array}
Interesting observation : $c(8,2) = c(8,3)$
combinatorics graph-theory polygons
combinatorics graph-theory polygons
asked Jul 21 '18 at 19:06
MrLemmingMrLemming
364
asked Jul 21 '18 at 19:06
MrLemmingMrLemming
364
edited Jul 23 '18 at 17:05
MrLemming
asked Jul 21 '18 at 19:06
MrLemmingMrLemming
364
asked Jul 21 '18 at 19:06
MrLemmingMrLemming
364
asked Jul 21 '18 at 19:06
MrLemmingMrLemming
364
364
1
$begingroup$
The code would be good; but more results would be even better, so people who can't run the code could also use them. I get the impression that $c(n,1)=n-2$.
$endgroup$
– joriki
Jul 21 '18 at 19:21
1
$begingroup$
@joriki $c(6,1)geq 5$, though. I have $c(2n,1)geq 3n-4$.
$endgroup$
– Batominovski
Jul 21 '18 at 19:30
1
$begingroup$
And $c(2n+1,1)geq 3n-3$.
$endgroup$
– Batominovski
Jul 21 '18 at 19:36
1
$begingroup$
@joriki Let $ABCDEF$ be a cyclic hexagon. Draw $AC$, $BD$, $AD$, $DF$, and $EA$.
$endgroup$
– Batominovski
Jul 21 '18 at 19:43
1
$begingroup$
“if we choose $k$ large enough, we can always put in all $frac{n cdot (n-3)}{2}$ possible chords”. This is possible iff $kge ab$ for each $1le a,b$ with $a+b=n-2$, that is iff $kge lfloor n^2/4rfloor-n+1$.
$endgroup$
– Alex Ravsky
Dec 28 '18 at 10:02
|
show 7 more comments
1
$begingroup$
The code would be good; but more results would be even better, so people who can't run the code could also use them. I get the impression that $c(n,1)=n-2$.
$endgroup$
– joriki
Jul 21 '18 at 19:21
1
$begingroup$
@joriki $c(6,1)geq 5$, though. I have $c(2n,1)geq 3n-4$.
$endgroup$
– Batominovski
Jul 21 '18 at 19:30
1
$begingroup$
And $c(2n+1,1)geq 3n-3$.
$endgroup$
– Batominovski
Jul 21 '18 at 19:36
1
$begingroup$
@joriki Let $ABCDEF$ be a cyclic hexagon. Draw $AC$, $BD$, $AD$, $DF$, and $EA$.
$endgroup$
– Batominovski
Jul 21 '18 at 19:43
1
$begingroup$
“if we choose $k$ large enough, we can always put in all $frac{n cdot (n-3)}{2}$ possible chords”. This is possible iff $kge ab$ for each $1le a,b$ with $a+b=n-2$, that is iff $kge lfloor n^2/4rfloor-n+1$.
$endgroup$
– Alex Ravsky
Dec 28 '18 at 10:02
1
1
$begingroup$
The code would be good; but more results would be even better, so people who can't run the code could also use them. I get the impression that $c(n,1)=n-2$.
$endgroup$
– joriki
Jul 21 '18 at 19:21
$begingroup$
The code would be good; but more results would be even better, so people who can't run the code could also use them. I get the impression that $c(n,1)=n-2$.
$endgroup$
– joriki
Jul 21 '18 at 19:21
1
1
$begingroup$
@joriki $c(6,1)geq 5$, though. I have $c(2n,1)geq 3n-4$.
$endgroup$
– Batominovski
Jul 21 '18 at 19:30
$begingroup$
@joriki $c(6,1)geq 5$, though. I have $c(2n,1)geq 3n-4$.
$endgroup$
– Batominovski
Jul 21 '18 at 19:30
1
1
$begingroup$
And $c(2n+1,1)geq 3n-3$.
$endgroup$
– Batominovski
Jul 21 '18 at 19:36
$begingroup$
And $c(2n+1,1)geq 3n-3$.
$endgroup$
– Batominovski
Jul 21 '18 at 19:36
1
1
$begingroup$
@joriki Let $ABCDEF$ be a cyclic hexagon. Draw $AC$, $BD$, $AD$, $DF$, and $EA$.
$endgroup$
– Batominovski
Jul 21 '18 at 19:43
$begingroup$
@joriki Let $ABCDEF$ be a cyclic hexagon. Draw $AC$, $BD$, $AD$, $DF$, and $EA$.
$endgroup$
– Batominovski
Jul 21 '18 at 19:43
1
1
$begingroup$
“if we choose $k$ large enough, we can always put in all $frac{n cdot (n-3)}{2}$ possible chords”. This is possible iff $kge ab$ for each $1le a,b$ with $a+b=n-2$, that is iff $kge lfloor n^2/4rfloor-n+1$.
$endgroup$
– Alex Ravsky
Dec 28 '18 at 10:02
$begingroup$
“if we choose $k$ large enough, we can always put in all $frac{n cdot (n-3)}{2}$ possible chords”. This is possible iff $kge ab$ for each $1le a,b$ with $a+b=n-2$, that is iff $kge lfloor n^2/4rfloor-n+1$.
$endgroup$
– Alex Ravsky
Dec 28 '18 at 10:02
|
show 7 more comments
1 Answer
1
active
oldest
votes
$begingroup$
You are asking about a maximal possible number of edges in an outer $k$-planar graph (minus $n$ for the number of sides of the $n$-gon). As far as I know, these graphs are a very recent topic in graph theory and they are studied in Würzburg. It is already known that an outer $1$-planar graph with $n$ vertices has at most $2.5n-4$ edges and this bound is tight [A] (that coincides with the second column of your table). But I found no results for bigger $k$, so I have sent a link to your question to Würzburg team.
References
[A] C. Auer, C. Bachmaier, F. J. Brandenburg, A. Gleißner, K. Hanauer, D. Neuwirth, and J. Reislhuber. Outer 1-planar graphs. Algorithmica, 74(4):1293-1320, 2016.
answered Dec 28 '18 at 9:41
Alex RavskyAlex Ravsky
43.2k32583
$endgroup$
1
$begingroup$
Hello Alex, this is indeed the origin of the problem and thus I am already familiar with the reference, but still thanks for that. I tried to keep the formulation of the problem more general, but in hindsight it might have been useful to also include the origin.
$endgroup$
– MrLemming
Jan 5 at 15:00
add a comment |
Your Answer
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%2f2858794%2fnumber-of-chords-in-a-n-gon-if-each-chord-is-crossed-at-most-k-times%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$
You are asking about a maximal possible number of edges in an outer $k$-planar graph (minus $n$ for the number of sides of the $n$-gon). As far as I know, these graphs are a very recent topic in graph theory and they are studied in Würzburg. It is already known that an outer $1$-planar graph with $n$ vertices has at most $2.5n-4$ edges and this bound is tight [A] (that coincides with the second column of your table). But I found no results for bigger $k$, so I have sent a link to your question to Würzburg team.
References
[A] C. Auer, C. Bachmaier, F. J. Brandenburg, A. Gleißner, K. Hanauer, D. Neuwirth, and J. Reislhuber. Outer 1-planar graphs. Algorithmica, 74(4):1293-1320, 2016.
answered Dec 28 '18 at 9:41
Alex RavskyAlex Ravsky
43.2k32583
$endgroup$
1
$begingroup$
Hello Alex, this is indeed the origin of the problem and thus I am already familiar with the reference, but still thanks for that. I tried to keep the formulation of the problem more general, but in hindsight it might have been useful to also include the origin.
$endgroup$
– MrLemming
Jan 5 at 15:00
add a comment |
$begingroup$
You are asking about a maximal possible number of edges in an outer $k$-planar graph (minus $n$ for the number of sides of the $n$-gon). As far as I know, these graphs are a very recent topic in graph theory and they are studied in Würzburg. It is already known that an outer $1$-planar graph with $n$ vertices has at most $2.5n-4$ edges and this bound is tight [A] (that coincides with the second column of your table). But I found no results for bigger $k$, so I have sent a link to your question to Würzburg team.
References
[A] C. Auer, C. Bachmaier, F. J. Brandenburg, A. Gleißner, K. Hanauer, D. Neuwirth, and J. Reislhuber. Outer 1-planar graphs. Algorithmica, 74(4):1293-1320, 2016.
answered Dec 28 '18 at 9:41
Alex RavskyAlex Ravsky
43.2k32583
$endgroup$
1
$begingroup$
Hello Alex, this is indeed the origin of the problem and thus I am already familiar with the reference, but still thanks for that. I tried to keep the formulation of the problem more general, but in hindsight it might have been useful to also include the origin.
$endgroup$
– MrLemming
Jan 5 at 15:00
add a comment |
$begingroup$
You are asking about a maximal possible number of edges in an outer $k$-planar graph (minus $n$ for the number of sides of the $n$-gon). As far as I know, these graphs are a very recent topic in graph theory and they are studied in Würzburg. It is already known that an outer $1$-planar graph with $n$ vertices has at most $2.5n-4$ edges and this bound is tight [A] (that coincides with the second column of your table). But I found no results for bigger $k$, so I have sent a link to your question to Würzburg team.
References
[A] C. Auer, C. Bachmaier, F. J. Brandenburg, A. Gleißner, K. Hanauer, D. Neuwirth, and J. Reislhuber. Outer 1-planar graphs. Algorithmica, 74(4):1293-1320, 2016.
answered Dec 28 '18 at 9:41
Alex RavskyAlex Ravsky
43.2k32583
$endgroup$
You are asking about a maximal possible number of edges in an outer $k$-planar graph (minus $n$ for the number of sides of the $n$-gon). As far as I know, these graphs are a very recent topic in graph theory and they are studied in Würzburg. It is already known that an outer $1$-planar graph with $n$ vertices has at most $2.5n-4$ edges and this bound is tight [A] (that coincides with the second column of your table). But I found no results for bigger $k$, so I have sent a link to your question to Würzburg team.
References
[A] C. Auer, C. Bachmaier, F. J. Brandenburg, A. Gleißner, K. Hanauer, D. Neuwirth, and J. Reislhuber. Outer 1-planar graphs. Algorithmica, 74(4):1293-1320, 2016.
answered Dec 28 '18 at 9:41
Alex RavskyAlex Ravsky
43.2k32583
edited Dec 28 '18 at 9:50
answered Dec 28 '18 at 9:41
Alex RavskyAlex Ravsky
43.2k32583
answered Dec 28 '18 at 9:41
Alex RavskyAlex Ravsky
43.2k32583
answered Dec 28 '18 at 9:41
Alex RavskyAlex Ravsky
43.2k32583
43.2k32583
1
$begingroup$
Hello Alex, this is indeed the origin of the problem and thus I am already familiar with the reference, but still thanks for that. I tried to keep the formulation of the problem more general, but in hindsight it might have been useful to also include the origin.
$endgroup$
– MrLemming
Jan 5 at 15:00
add a comment |
1
$begingroup$
Hello Alex, this is indeed the origin of the problem and thus I am already familiar with the reference, but still thanks for that. I tried to keep the formulation of the problem more general, but in hindsight it might have been useful to also include the origin.
$endgroup$
– MrLemming
Jan 5 at 15:00
1
1
$begingroup$
Hello Alex, this is indeed the origin of the problem and thus I am already familiar with the reference, but still thanks for that. I tried to keep the formulation of the problem more general, but in hindsight it might have been useful to also include the origin.
$endgroup$
– MrLemming
Jan 5 at 15:00
$begingroup$
Hello Alex, this is indeed the origin of the problem and thus I am already familiar with the reference, but still thanks for that. I tried to keep the formulation of the problem more general, but in hindsight it might have been useful to also include the origin.
$endgroup$
– MrLemming
Jan 5 at 15:00
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%2f2858794%2fnumber-of-chords-in-a-n-gon-if-each-chord-is-crossed-at-most-k-times%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
$begingroup$
The code would be good; but more results would be even better, so people who can't run the code could also use them. I get the impression that $c(n,1)=n-2$.
$endgroup$
– joriki
Jul 21 '18 at 19:21
1
$begingroup$
@joriki $c(6,1)geq 5$, though. I have $c(2n,1)geq 3n-4$.
$endgroup$
– Batominovski
Jul 21 '18 at 19:30
1
$begingroup$
And $c(2n+1,1)geq 3n-3$.
$endgroup$
– Batominovski
Jul 21 '18 at 19:36
1
$begingroup$
@joriki Let $ABCDEF$ be a cyclic hexagon. Draw $AC$, $BD$, $AD$, $DF$, and $EA$.
$endgroup$
– Batominovski
Jul 21 '18 at 19:43
1
$begingroup$
“if we choose $k$ large enough, we can always put in all $frac{n cdot (n-3)}{2}$ possible chords”. This is possible iff $kge ab$ for each $1le a,b$ with $a+b=n-2$, that is iff $kge lfloor n^2/4rfloor-n+1$.
$endgroup$
– Alex Ravsky
Dec 28 '18 at 10:02