Mixing
A conjecture about minimal spanning trees among points in the unit square
up vote
3
down vote
favorite
For $ninBbb N$, consider $n$ points $x_1,ldots, x_n$ in the unit square $Q=[0,1]^2$. Let $f(x_1,ldots, x_n)$ denote the minimal total edge length of a tree with $x_1,ldots, x_n$ as vertices.
Let
$$ L_n=sup_{x_1,ldots, x_nin Q}f(x_1,ldots,x_n).$$
Then in Prove that there exists a graph with these points such that G is connected, it was asked to show that $$tag1forall nge 3colon L_nle csqrt n $$
is true for $c=10$ and false for $c=1$.
In my answer (see there), an inductive argument based on subdividing the square showed that $(1)$ is true for $c=2sqrt 2approx 2.828$, and has infinitely many counterexamples for $c=1$.
In a later addendum to my answer, I showed that
$$ tag2exists ell_0colon forall ncolon L_n<ell_0+csqrt n$$
holds for any $c>frac 4{sqrt{2sqrt 3}}approx 2.149$ and dared to
Conjecture. $$inf{,cinBbb Rmid (2) text{ is true},}=frac{4}{sqrt{2sqrt 3}}. $$
I dared to do so because the constant stems from the factor $frac{pi}{2sqrt 3}$ known from the densest circle packing.
My question for you us: Is my conjecture true?
trees packing-problem
asked 2 days ago
Hagen von Eitzen
273k21266493
add a comment |
up vote
3
down vote
favorite
For $ninBbb N$, consider $n$ points $x_1,ldots, x_n$ in the unit square $Q=[0,1]^2$. Let $f(x_1,ldots, x_n)$ denote the minimal total edge length of a tree with $x_1,ldots, x_n$ as vertices.
Let
$$ L_n=sup_{x_1,ldots, x_nin Q}f(x_1,ldots,x_n).$$
Then in Prove that there exists a graph with these points such that G is connected, it was asked to show that $$tag1forall nge 3colon L_nle csqrt n $$
is true for $c=10$ and false for $c=1$.
In my answer (see there), an inductive argument based on subdividing the square showed that $(1)$ is true for $c=2sqrt 2approx 2.828$, and has infinitely many counterexamples for $c=1$.
In a later addendum to my answer, I showed that
$$ tag2exists ell_0colon forall ncolon L_n<ell_0+csqrt n$$
holds for any $c>frac 4{sqrt{2sqrt 3}}approx 2.149$ and dared to
Conjecture. $$inf{,cinBbb Rmid (2) text{ is true},}=frac{4}{sqrt{2sqrt 3}}. $$
I dared to do so because the constant stems from the factor $frac{pi}{2sqrt 3}$ known from the densest circle packing.
My question for you us: Is my conjecture true?
trees packing-problem
asked 2 days ago
Hagen von Eitzen
273k21266493
add a comment |
up vote
3
down vote
favorite
up vote
3
down vote
favorite
For $ninBbb N$, consider $n$ points $x_1,ldots, x_n$ in the unit square $Q=[0,1]^2$. Let $f(x_1,ldots, x_n)$ denote the minimal total edge length of a tree with $x_1,ldots, x_n$ as vertices.
Let
$$ L_n=sup_{x_1,ldots, x_nin Q}f(x_1,ldots,x_n).$$
Then in Prove that there exists a graph with these points such that G is connected, it was asked to show that $$tag1forall nge 3colon L_nle csqrt n $$
is true for $c=10$ and false for $c=1$.
In my answer (see there), an inductive argument based on subdividing the square showed that $(1)$ is true for $c=2sqrt 2approx 2.828$, and has infinitely many counterexamples for $c=1$.
In a later addendum to my answer, I showed that
$$ tag2exists ell_0colon forall ncolon L_n<ell_0+csqrt n$$
holds for any $c>frac 4{sqrt{2sqrt 3}}approx 2.149$ and dared to
Conjecture. $$inf{,cinBbb Rmid (2) text{ is true},}=frac{4}{sqrt{2sqrt 3}}. $$
I dared to do so because the constant stems from the factor $frac{pi}{2sqrt 3}$ known from the densest circle packing.
My question for you us: Is my conjecture true?
trees packing-problem
asked 2 days ago
Hagen von Eitzen
273k21266493
For $ninBbb N$, consider $n$ points $x_1,ldots, x_n$ in the unit square $Q=[0,1]^2$. Let $f(x_1,ldots, x_n)$ denote the minimal total edge length of a tree with $x_1,ldots, x_n$ as vertices.
Let
$$ L_n=sup_{x_1,ldots, x_nin Q}f(x_1,ldots,x_n).$$
Then in Prove that there exists a graph with these points such that G is connected, it was asked to show that $$tag1forall nge 3colon L_nle csqrt n $$
is true for $c=10$ and false for $c=1$.
In my answer (see there), an inductive argument based on subdividing the square showed that $(1)$ is true for $c=2sqrt 2approx 2.828$, and has infinitely many counterexamples for $c=1$.
In a later addendum to my answer, I showed that
$$ tag2exists ell_0colon forall ncolon L_n<ell_0+csqrt n$$
holds for any $c>frac 4{sqrt{2sqrt 3}}approx 2.149$ and dared to
Conjecture. $$inf{,cinBbb Rmid (2) text{ is true},}=frac{4}{sqrt{2sqrt 3}}. $$
I dared to do so because the constant stems from the factor $frac{pi}{2sqrt 3}$ known from the densest circle packing.
My question for you us: Is my conjecture true?
trees packing-problem
trees packing-problem
asked 2 days ago
Hagen von Eitzen
273k21266493
asked 2 days ago
Hagen von Eitzen
273k21266493
asked 2 days ago
Hagen von Eitzen
273k21266493
asked 2 days ago
Hagen von Eitzen
273k21266493
asked 2 days ago
Hagen von Eitzen
273k21266493
273k21266493
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
Silly me! After a good night's rest, this direction is of course the trivial part!
For $mgg 0$, the lattice $frac 1mBbb Z[frac{1+isqrt 3}2]$ has $frac {2m}{sqrt 3}+O(1)$ rows of $m+O(1)$ points each in the unit square, so that's $n=frac 2{sqrt 3}m² +O(m)$ points with minimal distance $frac 1m$ between them. Any tree with these vertices certainly has edge length
$$ell =frac{n-1}m=frac 2{sqrt 3}m+O(1) =frac{sqrt 2}{sqrt[4]3}sqrt n+O(1)=frac 2{sqrt{2sqrt 3}}sqrt n+O(1).$$
I suppose, a spurious factor of $2$ somehow slipped into the calculations leading to the conjecture.
answered 2 days ago
Hagen von Eitzen
273k21266493
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
Silly me! After a good night's rest, this direction is of course the trivial part!
For $mgg 0$, the lattice $frac 1mBbb Z[frac{1+isqrt 3}2]$ has $frac {2m}{sqrt 3}+O(1)$ rows of $m+O(1)$ points each in the unit square, so that's $n=frac 2{sqrt 3}m² +O(m)$ points with minimal distance $frac 1m$ between them. Any tree with these vertices certainly has edge length
$$ell =frac{n-1}m=frac 2{sqrt 3}m+O(1) =frac{sqrt 2}{sqrt[4]3}sqrt n+O(1)=frac 2{sqrt{2sqrt 3}}sqrt n+O(1).$$
I suppose, a spurious factor of $2$ somehow slipped into the calculations leading to the conjecture.
answered 2 days ago
Hagen von Eitzen
273k21266493
add a comment |
up vote
0
down vote
Silly me! After a good night's rest, this direction is of course the trivial part!
For $mgg 0$, the lattice $frac 1mBbb Z[frac{1+isqrt 3}2]$ has $frac {2m}{sqrt 3}+O(1)$ rows of $m+O(1)$ points each in the unit square, so that's $n=frac 2{sqrt 3}m² +O(m)$ points with minimal distance $frac 1m$ between them. Any tree with these vertices certainly has edge length
$$ell =frac{n-1}m=frac 2{sqrt 3}m+O(1) =frac{sqrt 2}{sqrt[4]3}sqrt n+O(1)=frac 2{sqrt{2sqrt 3}}sqrt n+O(1).$$
I suppose, a spurious factor of $2$ somehow slipped into the calculations leading to the conjecture.
answered 2 days ago
Hagen von Eitzen
273k21266493
add a comment |
up vote
0
down vote
up vote
0
down vote
Silly me! After a good night's rest, this direction is of course the trivial part!
For $mgg 0$, the lattice $frac 1mBbb Z[frac{1+isqrt 3}2]$ has $frac {2m}{sqrt 3}+O(1)$ rows of $m+O(1)$ points each in the unit square, so that's $n=frac 2{sqrt 3}m² +O(m)$ points with minimal distance $frac 1m$ between them. Any tree with these vertices certainly has edge length
$$ell =frac{n-1}m=frac 2{sqrt 3}m+O(1) =frac{sqrt 2}{sqrt[4]3}sqrt n+O(1)=frac 2{sqrt{2sqrt 3}}sqrt n+O(1).$$
I suppose, a spurious factor of $2$ somehow slipped into the calculations leading to the conjecture.
answered 2 days ago
Hagen von Eitzen
273k21266493
Silly me! After a good night's rest, this direction is of course the trivial part!
For $mgg 0$, the lattice $frac 1mBbb Z[frac{1+isqrt 3}2]$ has $frac {2m}{sqrt 3}+O(1)$ rows of $m+O(1)$ points each in the unit square, so that's $n=frac 2{sqrt 3}m² +O(m)$ points with minimal distance $frac 1m$ between them. Any tree with these vertices certainly has edge length
$$ell =frac{n-1}m=frac 2{sqrt 3}m+O(1) =frac{sqrt 2}{sqrt[4]3}sqrt n+O(1)=frac 2{sqrt{2sqrt 3}}sqrt n+O(1).$$
I suppose, a spurious factor of $2$ somehow slipped into the calculations leading to the conjecture.
answered 2 days ago
Hagen von Eitzen
273k21266493
answered 2 days ago
Hagen von Eitzen
273k21266493
answered 2 days ago
Hagen von Eitzen
273k21266493
answered 2 days ago
Hagen von Eitzen
273k21266493
273k21266493
add a comment |
add a comment |
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%2f3005551%2fa-conjecture-about-minimal-spanning-trees-among-points-in-the-unit-square%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
