All Questions
Tagged with co.combinatorics mg.metric-geometry
246 questions
18
votes
2
answers
700
views
Can all unit-distance graphs have their vertices at algebraic integers?
A graph $G$ is described as a unit-distance graph if there exists a function $f:G \rightarrow \mathbb{C}$ such that for every edge $(u,v) \in E(G)$, we have $|f(u) - f(v)| = 1$.
Obviously, we can ...
- 12.4k
11
votes
1
answer
807
views
Soft question: mathematics about truchet tiles
It seems that this is the first question on Truchet tiles on MO.
Shown above is a picture of a random tile, which you can see the resulting configuration is much like many membranes of cells.
I ...
- 191
9
votes
3
answers
1k
views
Generalization of Sylvester-Gallai theorem
The Sylvester-Gallai theorem states that it is not possible to arrange a finite number
of points so that a line through every two of them passes through a
third unless they are all on a single ...
4
votes
1
answer
288
views
Stable equilibria of points on the 2-sphere
Suppose $n$ points lie on the sphere $S^2=\{x\in\mathbb{R}^3\mid \|x\|=1\}$ and are subjected to a repulsive acceleration that pushes away a point from each other point with an intensity proportional ...
- 43
6
votes
2
answers
268
views
Counting valid coordinates
We are given a matrix $D = (d(i,j))_{1 \leq i,j \leq n}$ such that $d(x,z) \leq d(x,y) + d(y,z)$ for each $1 \leq x,y,z \leq n$. It is also known that $d(x,y) \in \mathbb{N}$ (In this question $0 \in \...
- 323
9
votes
3
answers
605
views
Separating points in the plane II
Let A be a set of $2m$ points on the plane so that no open set of diameter $2$ has more than m of them. Define $A+A+...+A$ ($k$ times) to be the multiset of $k$-sums from $A$. That is, we consider all ...
- 2,288
7
votes
2
answers
191
views
Trees with a maximal convex hull: are the only optimal solutions Steiner trees?
For given $n\geqslant 3$, I'm looking for a connected set composed of $n$ equal segments in the plane such that the convex hull of it has maximal area $A(n)$. To simplify notation, we'll take $\dfrac{...
- 13.4k
6
votes
2
answers
168
views
Which criteria guarantee an orthogonal circuit in $\mathbb R^3$ to be rigid?
For $n\ge4$, define an orthogonal circuit or O-circuit as a closed circuit of $n$ unit segments in $\mathbb R^3$ such that any two neighboring segments form a right angle. (Physically this could be ...
- 13.4k
28
votes
5
answers
2k
views
Visibility of vertices in polyhedra
Suppose $P$ is a closed polyhedron in space (i.e. a union of polygons which is homeomorphic to $S^2$) and $X$ is an interior point of $P$. Is it true that $X$ can see at least one vertex of $P$? More ...
- 4,484
10
votes
0
answers
365
views
diameter as a Morse function
Consider the space $X_1$ of closed subsets not containing a pair of antipodal points of the unit circle. Here we have a kind of degenerate Morse function, defined by the diameter of the pointset. ...
- 16.6k
12
votes
2
answers
805
views
A question about pairs of lines in 3D projective space
Consider a 3-dimensional projective space $X$.
Let $m$ be the smallest number so that there are $m$ pairs of lines
$ \ell_1,\ell'_1$, $ \ell_2,\ell_2'$, ... , $\ell_m, \ell'_m$ in $X$:
a) For ...
- 24.7k
11
votes
3
answers
2k
views
Could a perfect squared square be split into two perfect squared squares?
This is a geometric puzzle though it might conceivably
also define a special class of Pythagorean triples.
A perfect squared square PSS is a square (as a plane figure)
partitioned into smaller ...
- 1,375
6
votes
1
answer
185
views
Maximizing ratio volume/diameter^n by an affinity
Suppose we have a convex compact body $D\subset \mathbb R^n$. We can try to apply affine transformation keeping the volume and decreasing the diameter of $D$.
It is clear that there is a constant $\...
- 5,053
12
votes
1
answer
504
views
Tverberg's theorem in CAT(0) spaces
Does Tverberg's theorem hold for CAT(0) spaces of covering dimension $d<\infty$:
Is it true that for any $d$-dimensional $CAT(0)$-space $X$ and a subset $E\subset X$ of cardinality $(d + 1)(r - ...
- 31.2k
16
votes
0
answers
298
views
Realization spaces of 3-dimensional polytopes with fixed face areas
It is a well-know result (Steinitz, 1922) that the realization space of 3-dimensional convex polytopes with fixed combinatorics is contractible.
A proof of this theorem can be found for instance in ...
- 31.2k
20
votes
1
answer
452
views
Hidden points in polygons
Let $h(n)$ be the largest number of mutually invisible points that can be located in a
polygon $P$ of $n$ vertices. Two points $x$ and $y$ are mutually invisible if the segment
$xy$ contains a point ...
- 151k
6
votes
1
answer
483
views
Separating pairs of points in R^n
Let $A$ be a set of $2k$ points in $\mathbb{R}^n$ such that no open set in $\mathbb{R}^n$ of diameter $2$ contains more than $k$ of these points. What is the largest possible distance $r_n>0$ one ...
- 2,288
11
votes
0
answers
352
views
Right-angled polytopes
%This question is motivated by the little discussion here at the bottom.
The following thing are known about hyperbolic right-angled polytopes:
Compact hyperbolic right-angled polytopes do not exist ...
- 1,268
14
votes
2
answers
878
views
Sets of evenly distributed points in the Euclidean plane
Is there a set $P \subset \mathbb{R}^2$ of points in the Euclidean plane whose intersection
with every convex subset of $\mathbb{R}^2$ of area $1$ is nonempty but finite?
If the answer is yes, can $P$...
- 19.6k
8
votes
0
answers
276
views
Generalized flag complex?
Assume we glue an $n$-dimensional simplicial complex $K$
from copies of an $n$-simplex $\Delta$ with fixed spherical metric.
We may think that $\Delta$ has colored vertices
and we glue so that the ...
- 45k
4
votes
2
answers
287
views
Problems similar to Borsuk’s Theorem in the plane
Consider a 2-dimensional Borsuk's theorem:
Every bounded set $S$ in the plane can be partitioned into three parts with diameter smaller than the diameter of $S$.
I wonder if there are any results ...
- 181
11
votes
1
answer
369
views
The number of relevant scales for a finite metric space
For an $n$-element metric space $X=\{x_1,\dots,x_n\}$ with metric
$d$ we introduce an array containing $\frac{n(n-1)}2$ numbers
$d(x_i,x_j)$, $i<j$. We assume that all distances are at least
$1$. ...
- 4,878
1
vote
1
answer
210
views
Pythagorean triples related to non-isometric equidistant plane quadruples
QUESTION Do there exist integers $u\ x\ A\ B$ such that $x\ne 0$, and the following two equalities hold:
$ x^2 + (x-u)^2\ =\ A^2$
$ x^2 + (x+u)^2\ =\ B^2$
?
...
- 7,500
9
votes
1
answer
665
views
Question about tetrahedron decomposition
Are there tetrahedra which can be subdivided into three non-overlapping parts similar to the original? I believe this would require splitting one face into three parts. I know some types of tetrahedra ...
- 93
1
vote
2
answers
164
views
General and translational Birkhoff lattices. Equational classes
By lattice I'll mean Birkhoff lattice.
The two classical equational classes of lattices are modular lattices and distributive lattices. The old problem used to be:
Is there an equational class ...
- 7,500
10
votes
1
answer
535
views
Maximum number of Vertices of Hypercube covered by Ball of radius R
Let $R>0$ be given and let $H^n$ be the unit hypercube in $\mathbb{R}^n$. The problem I am facing is to find the maximum number of vertices of $H^n$ which can be covered by a closed $n$-dimensional ...
- 185
4
votes
1
answer
399
views
A regular polytope
For positive integers $m$ and $n$, consider a regular polytope in ${\mathbb R}^{m+n+mn}$ with $2^{m+n}$ vertices, corresponding to each $\sigma \in \{-1,1\}^{m+n}$ as follows. The first $m+n$ ...
- 54.2k
7
votes
0
answers
292
views
Minimal spanning tree of a point set in the unit square, under an unusual distance function
For two points $x$, $y \in [0,1]^2$, let their distance be $d(x,y) := \|x-y\|_2^2$ (i.e. the usual distance, squared). Technically, this is a semimetric, as it does not satisfy the triangle inequality....
- 1,318
4
votes
1
answer
275
views
Nontrivial lower bounds on Cheeger inequalities for Markov chains
For a reversible Markov chain $X_{t}$ on $\mathbb{R}^{n}$ with transition kernel $K$ and stationary distribution $\pi$, it is well-known that the `spectral gap' (basically, the size of $K$ when ...
- 51
7
votes
2
answers
549
views
Kissing Number of Spheres in Non-Euclidean Geometry
There has been much work done on the kissing number problem (of determining the greatest number of congruent spheres which can touch a single sphere in a packing) in Euclidean space for dimensions $1$ ...
- 1,431
1
vote
1
answer
427
views
Is this min not less than a min
Let $\mathbf{D}$ be the unit disk, is
$$\inf_{\begin{array}{c}
v_{1},v_{2},v_{3},v_{4}\in\mathbf{D},\\
v_{0}\in\mbox{convexhull}\left(v_{1},v_{2},v_{3},v_{4}\right)
\end{array}}\max_{0\le i,j,k\le4}\...
- 27
12
votes
1
answer
670
views
Volume-like property to upper bound lattice points in a convex body
The following question arises in passing in a joint paper that I am working on. Let $K$ be a centrally symmetric convex body in an $n$-dimensional real vector space $V$ which contains a lattice $L$. ...
- 56.6k
3
votes
1
answer
443
views
What is the expected value for this
If there are $8$ random points in the plane whose horizontal coordinate
and vertical coordinate are uniformly distributed on the open interval
$\left(0,1\right)$, what is the expected largest size of ...
- 31
6
votes
0
answers
271
views
Families of triangulations of polygons in the plane
Let $P$ be a polygon in the plane. An "efficient" triangulation of $P$ is one that introduces no new vertices. We require that all introduced edges be straight and inside $P$. Every polygon in the ...
- 1,625
11
votes
1
answer
413
views
Polyominoes with double contact
Here is a problem which arose from an earlier question. I'll change the terminology but not the question: A polyomino is a region with a connected interior made by joining one or more unit squares ...
- 30.1k
2
votes
2
answers
255
views
What is the smallest number of subsets in such a subdivision?
Given any $30$ points in the plane, what is the smallest number of
subsets in a subdivision of the set of $30$ points into subsets such
that all the points in each subset are on the boundary of the ...
- 21
0
votes
1
answer
229
views
Is this bounded?
May be better to ask for help here. Let $v_{1}$, $v_{2}$, $\ldots$, $v_{m}$ be the vertices of a
convex polygon in the plane and $v_{m+1}$ be a vertex in the interior
of the convex polygon. Connect ...
- 1
1
vote
1
answer
178
views
Planar eucliean bipartite matching with squared distances
This is probably a really stupid question, but suppose I have two sets of points in the plane $X$ and $Y$ each with cardinality $|X| = |Y| = n$. For any bipartite matching $M$ between $X$ and $Y$, ...
11
votes
2
answers
797
views
Three half circles on the plane may not meet nicely
Let $H$ denote the union of the northern hemisphere of the unit circle $S^{1}$ with the interval $[-1,1]$ on the $x$-axis. That is, $H=\{(x,\sqrt{1-x^{2}}):-1\le x\le 1\}\cup\{(x,0):-1\le x\le 1\}$
...
- 2,136
6
votes
3
answers
780
views
Cylinders dividing $\mathbb{R}^{3}$
Consider $n$ affine copies of a compact cylinder, say $S^{1}\times [-3,3]$ with top and botom, sitting inside $\mathbb{R}^{3}$.
For each $n$ we may ask ourselves how to arrange the $n$ cylinders so ...
- 2,136
18
votes
1
answer
641
views
Can all convex polytopes be realized with vertices on surface of convex body?
The following question was asked by me on Mathematics.SE. Unfortunately, no one answered it so I thought I might give it a try one level higher. Below the line you can find the slightly edited ...
- 907
6
votes
2
answers
381
views
Lattice-cube minimal blocking sets
Let $C_d(n)$ be the lattice cube consisting of the $n^d$ points with
each of its $d$ coorindates in $\lbrace 1,2,\ldots,n \rbrace$.
Define a blocking set for a lattice cube to be a set of points
in ...
- 151k
1
vote
0
answers
247
views
dissections and vertices of non-convex polytopes
Let us call a finite union $P$ of $n$-dimensional compact convex polytopes in $\mathbb{R}^n$ a non-convex polytope. Recall that a dissection of $P$ is a finite collection $T$ of $n$-dimensional ...
- 14k
21
votes
1
answer
1k
views
A Weak Form of Borsuk's Conjecture
Problem: Let P be a d-dimensional polytope with n facets. Is it always true that P can be covered by n sets of smaller diameter?
Background and motivation
The Borsuk conjecture (disproved in 1993) ...
- 24.7k
10
votes
5
answers
834
views
Tessellating $\mathbb{R}^n$ by bricks.
Let us call the $\ell_1$-product of intervals $[0,k_1]\times...\times [0,k_n]$ a brick of size $k_1+...+k_n$. Consider a tessellation $T$ of $\mathbb{R^n}$ by (shifted) bricks so that every point ...
user6976
12
votes
1
answer
3k
views
Doubling dimension of a Euclidean space
The doubling dimension of a metric space $X$ is the smallest positive integer $k$ such that every ball of $X$ can be covered by $2^k$ balls of half the radius.
It is well known that the doubling ...
- 6,034