A maximal cardinality subset of n lattice points so that all points in the subset have distance at least 4
If we have some random set of $n$ lattice points what is the maximum cardinality of a subset in which all points have distance at least $4$ (or some other number).
I really hope the best bound is not the trivial $n/16$. I'm not asking for a proof that this bound is the best possible, just provide the best bound you can.
combinatorics combinatorial-geometry extremal-combinatorics
edited Dec 4 '18 at 6:16
Alex Ravsky
39.2k32080
asked Dec 3 '18 at 8:26
mr. clock
203
add a comment |
If we have some random set of $n$ lattice points what is the maximum cardinality of a subset in which all points have distance at least $4$ (or some other number).
I really hope the best bound is not the trivial $n/16$. I'm not asking for a proof that this bound is the best possible, just provide the best bound you can.
combinatorics combinatorial-geometry extremal-combinatorics
edited Dec 4 '18 at 6:16
Alex Ravsky
39.2k32080
asked Dec 3 '18 at 8:26
mr. clock
203
add a comment |
If we have some random set of $n$ lattice points what is the maximum cardinality of a subset in which all points have distance at least $4$ (or some other number).
I really hope the best bound is not the trivial $n/16$. I'm not asking for a proof that this bound is the best possible, just provide the best bound you can.
combinatorics combinatorial-geometry extremal-combinatorics
edited Dec 4 '18 at 6:16
Alex Ravsky
39.2k32080
asked Dec 3 '18 at 8:26
mr. clock
203
If we have some random set of $n$ lattice points what is the maximum cardinality of a subset in which all points have distance at least $4$ (or some other number).
I really hope the best bound is not the trivial $n/16$. I'm not asking for a proof that this bound is the best possible, just provide the best bound you can.
combinatorics combinatorial-geometry extremal-combinatorics
combinatorics combinatorial-geometry extremal-combinatorics
edited Dec 4 '18 at 6:16
Alex Ravsky
39.2k32080
asked Dec 3 '18 at 8:26
mr. clock
203
edited Dec 4 '18 at 6:16
Alex Ravsky
39.2k32080
asked Dec 3 '18 at 8:26
mr. clock
203
edited Dec 4 '18 at 6:16
Alex Ravsky
39.2k32080
edited Dec 4 '18 at 6:16
Alex Ravsky
39.2k32080
edited Dec 4 '18 at 6:16
Alex Ravsky
39.2k32080
39.2k32080
asked Dec 3 '18 at 8:26
mr. clock
203
asked Dec 3 '18 at 8:26
mr. clock
203
asked Dec 3 '18 at 8:26
mr. clock
203
203
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
I’ll try to provide a framework for the question. Let $d$ be a fixed distance $d$ (equal to $4$ in our case).
A set $A’$ of lattice points we shall call $d$-separated, if any two distinct points of $B$ are placed at distance at least $d$. We are interested in a smallest $r=r(d)$ such that any finite set $A$ of lattice points has a $d$-separated subset $B$ of size at least $|A|/r$. I guess Empy2 obtained a bound $rle 15$ by constructing a coloring of $Bbb Z^2$ into $15$ colors such that each monochromatic subset is $d$-separated. Indeed, in this case as $B$ we can chose a largest monochromatic subset of $A$, which imply $|B|ge |A|/15$ . Unfortunately, it can be easily shown that there is no such coloring in $14$ colors. (I’m going to write a proof later.) But this not imply that $r>14$, because a $d$-separated subset $B$ of $A$ may be chosen by different method. So there is sense to look for subsets $A$ of lattice points with the biggest ratio $|A|/|B|$, where $B$ is a maximal $d$-separated subset of $A$.
The following set has ratio $14$.
...
....
....
...
Are there subsets of lattice points with the bigger ratio?
answered Dec 5 '18 at 20:14
Alex Ravsky
39.2k32080
add a comment |
From the $ntimes n$ array, the following gives about $ n^2/15$, or one point in every fifteen.
$$x(3,3)+y(-1,4)$$
answered Dec 4 '18 at 7:13
Empy2
33.4k12261
1
Do you think it's possible to achieve $n^2/14$? That was actually a bound I was hoping for to solve a problem which led me to this question. The problem says that it's always possible to choose a subset of a set of unit circles having area $S$ so that the area of a chosen subset is at least $2S/9$. If you use a well-known result saying that for a figure of area $S$ it's always possible to set a coordinate system so that the figure contains at least $S$ lattice points it quickly becomes clear that a bound of $n^2/14$ would solve the problem.
– mr. clock
Dec 4 '18 at 8:48
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%2f3023777%2fa-maximal-cardinality-subset-of-n-lattice-points-so-that-all-points-in-the-subse%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
I’ll try to provide a framework for the question. Let $d$ be a fixed distance $d$ (equal to $4$ in our case).
A set $A’$ of lattice points we shall call $d$-separated, if any two distinct points of $B$ are placed at distance at least $d$. We are interested in a smallest $r=r(d)$ such that any finite set $A$ of lattice points has a $d$-separated subset $B$ of size at least $|A|/r$. I guess Empy2 obtained a bound $rle 15$ by constructing a coloring of $Bbb Z^2$ into $15$ colors such that each monochromatic subset is $d$-separated. Indeed, in this case as $B$ we can chose a largest monochromatic subset of $A$, which imply $|B|ge |A|/15$ . Unfortunately, it can be easily shown that there is no such coloring in $14$ colors. (I’m going to write a proof later.) But this not imply that $r>14$, because a $d$-separated subset $B$ of $A$ may be chosen by different method. So there is sense to look for subsets $A$ of lattice points with the biggest ratio $|A|/|B|$, where $B$ is a maximal $d$-separated subset of $A$.
The following set has ratio $14$.
...
....
....
...
Are there subsets of lattice points with the bigger ratio?
answered Dec 5 '18 at 20:14
Alex Ravsky
39.2k32080
add a comment |
I’ll try to provide a framework for the question. Let $d$ be a fixed distance $d$ (equal to $4$ in our case).
A set $A’$ of lattice points we shall call $d$-separated, if any two distinct points of $B$ are placed at distance at least $d$. We are interested in a smallest $r=r(d)$ such that any finite set $A$ of lattice points has a $d$-separated subset $B$ of size at least $|A|/r$. I guess Empy2 obtained a bound $rle 15$ by constructing a coloring of $Bbb Z^2$ into $15$ colors such that each monochromatic subset is $d$-separated. Indeed, in this case as $B$ we can chose a largest monochromatic subset of $A$, which imply $|B|ge |A|/15$ . Unfortunately, it can be easily shown that there is no such coloring in $14$ colors. (I’m going to write a proof later.) But this not imply that $r>14$, because a $d$-separated subset $B$ of $A$ may be chosen by different method. So there is sense to look for subsets $A$ of lattice points with the biggest ratio $|A|/|B|$, where $B$ is a maximal $d$-separated subset of $A$.
The following set has ratio $14$.
...
....
....
...
Are there subsets of lattice points with the bigger ratio?
answered Dec 5 '18 at 20:14
Alex Ravsky
39.2k32080
add a comment |
I’ll try to provide a framework for the question. Let $d$ be a fixed distance $d$ (equal to $4$ in our case).
A set $A’$ of lattice points we shall call $d$-separated, if any two distinct points of $B$ are placed at distance at least $d$. We are interested in a smallest $r=r(d)$ such that any finite set $A$ of lattice points has a $d$-separated subset $B$ of size at least $|A|/r$. I guess Empy2 obtained a bound $rle 15$ by constructing a coloring of $Bbb Z^2$ into $15$ colors such that each monochromatic subset is $d$-separated. Indeed, in this case as $B$ we can chose a largest monochromatic subset of $A$, which imply $|B|ge |A|/15$ . Unfortunately, it can be easily shown that there is no such coloring in $14$ colors. (I’m going to write a proof later.) But this not imply that $r>14$, because a $d$-separated subset $B$ of $A$ may be chosen by different method. So there is sense to look for subsets $A$ of lattice points with the biggest ratio $|A|/|B|$, where $B$ is a maximal $d$-separated subset of $A$.
The following set has ratio $14$.
...
....
....
...
Are there subsets of lattice points with the bigger ratio?
answered Dec 5 '18 at 20:14
Alex Ravsky
39.2k32080
I’ll try to provide a framework for the question. Let $d$ be a fixed distance $d$ (equal to $4$ in our case).
A set $A’$ of lattice points we shall call $d$-separated, if any two distinct points of $B$ are placed at distance at least $d$. We are interested in a smallest $r=r(d)$ such that any finite set $A$ of lattice points has a $d$-separated subset $B$ of size at least $|A|/r$. I guess Empy2 obtained a bound $rle 15$ by constructing a coloring of $Bbb Z^2$ into $15$ colors such that each monochromatic subset is $d$-separated. Indeed, in this case as $B$ we can chose a largest monochromatic subset of $A$, which imply $|B|ge |A|/15$ . Unfortunately, it can be easily shown that there is no such coloring in $14$ colors. (I’m going to write a proof later.) But this not imply that $r>14$, because a $d$-separated subset $B$ of $A$ may be chosen by different method. So there is sense to look for subsets $A$ of lattice points with the biggest ratio $|A|/|B|$, where $B$ is a maximal $d$-separated subset of $A$.
The following set has ratio $14$.
...
....
....
...
Are there subsets of lattice points with the bigger ratio?
answered Dec 5 '18 at 20:14
Alex Ravsky
39.2k32080
answered Dec 5 '18 at 20:14
Alex Ravsky
39.2k32080
answered Dec 5 '18 at 20:14
Alex Ravsky
39.2k32080
answered Dec 5 '18 at 20:14
Alex Ravsky
39.2k32080
39.2k32080
add a comment |
add a comment |
From the $ntimes n$ array, the following gives about $ n^2/15$, or one point in every fifteen.
$$x(3,3)+y(-1,4)$$
answered Dec 4 '18 at 7:13
Empy2
33.4k12261
1
Do you think it's possible to achieve $n^2/14$? That was actually a bound I was hoping for to solve a problem which led me to this question. The problem says that it's always possible to choose a subset of a set of unit circles having area $S$ so that the area of a chosen subset is at least $2S/9$. If you use a well-known result saying that for a figure of area $S$ it's always possible to set a coordinate system so that the figure contains at least $S$ lattice points it quickly becomes clear that a bound of $n^2/14$ would solve the problem.
– mr. clock
Dec 4 '18 at 8:48
add a comment |
From the $ntimes n$ array, the following gives about $ n^2/15$, or one point in every fifteen.
$$x(3,3)+y(-1,4)$$
answered Dec 4 '18 at 7:13
Empy2
33.4k12261
1
Do you think it's possible to achieve $n^2/14$? That was actually a bound I was hoping for to solve a problem which led me to this question. The problem says that it's always possible to choose a subset of a set of unit circles having area $S$ so that the area of a chosen subset is at least $2S/9$. If you use a well-known result saying that for a figure of area $S$ it's always possible to set a coordinate system so that the figure contains at least $S$ lattice points it quickly becomes clear that a bound of $n^2/14$ would solve the problem.
– mr. clock
Dec 4 '18 at 8:48
add a comment |
From the $ntimes n$ array, the following gives about $ n^2/15$, or one point in every fifteen.
$$x(3,3)+y(-1,4)$$
answered Dec 4 '18 at 7:13
Empy2
33.4k12261
From the $ntimes n$ array, the following gives about $ n^2/15$, or one point in every fifteen.
$$x(3,3)+y(-1,4)$$
answered Dec 4 '18 at 7:13
Empy2
33.4k12261
edited Dec 4 '18 at 7:18
answered Dec 4 '18 at 7:13
Empy2
33.4k12261
answered Dec 4 '18 at 7:13
Empy2
33.4k12261
answered Dec 4 '18 at 7:13
Empy2
33.4k12261
33.4k12261
1
Do you think it's possible to achieve $n^2/14$? That was actually a bound I was hoping for to solve a problem which led me to this question. The problem says that it's always possible to choose a subset of a set of unit circles having area $S$ so that the area of a chosen subset is at least $2S/9$. If you use a well-known result saying that for a figure of area $S$ it's always possible to set a coordinate system so that the figure contains at least $S$ lattice points it quickly becomes clear that a bound of $n^2/14$ would solve the problem.
– mr. clock
Dec 4 '18 at 8:48
add a comment |
1
Do you think it's possible to achieve $n^2/14$? That was actually a bound I was hoping for to solve a problem which led me to this question. The problem says that it's always possible to choose a subset of a set of unit circles having area $S$ so that the area of a chosen subset is at least $2S/9$. If you use a well-known result saying that for a figure of area $S$ it's always possible to set a coordinate system so that the figure contains at least $S$ lattice points it quickly becomes clear that a bound of $n^2/14$ would solve the problem.
– mr. clock
Dec 4 '18 at 8:48
1
1
Do you think it's possible to achieve $n^2/14$? That was actually a bound I was hoping for to solve a problem which led me to this question. The problem says that it's always possible to choose a subset of a set of unit circles having area $S$ so that the area of a chosen subset is at least $2S/9$. If you use a well-known result saying that for a figure of area $S$ it's always possible to set a coordinate system so that the figure contains at least $S$ lattice points it quickly becomes clear that a bound of $n^2/14$ would solve the problem.
– mr. clock
Dec 4 '18 at 8:48
Do you think it's possible to achieve $n^2/14$? That was actually a bound I was hoping for to solve a problem which led me to this question. The problem says that it's always possible to choose a subset of a set of unit circles having area $S$ so that the area of a chosen subset is at least $2S/9$. If you use a well-known result saying that for a figure of area $S$ it's always possible to set a coordinate system so that the figure contains at least $S$ lattice points it quickly becomes clear that a bound of $n^2/14$ would solve the problem.
– mr. clock
Dec 4 '18 at 8:48
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3023777%2fa-maximal-cardinality-subset-of-n-lattice-points-so-that-all-points-in-the-subse%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
