All Questions
Tagged with co.combinatorics mg.metric-geometry
246 questions
4
votes
1
answer
422
views
Can $n$ circles on a plane generate $m$ intersection points where at least $k$ circles intersect?
Can $n$ circles on a plane generate $m$ intersection points where at least $k$ circles intersect?
For $k = 2$ the answer is obvious since we can always place circles so that every one of them ...
CommunityBot
- 1
3
votes
3
answers
310
views
measuring $n\ 2$-planes in $\mathbb{R}^{2n}$
Given $n$ vectors $v_1, \ldots, v_n$ in $\mathbb{R}^n$ of course we all know at least one measure for their relative configuration: $|v_1 \wedge\ldots \wedge v_n|$. Now suppose one were given $n$ ...
- 1,100
23
votes
6
answers
2k
views
Is there a topological description of combinatorial Euler characteristic?
There are a collection of definitions of "combinatorial Euler characteristic", which is different from the "homotopy Euler characteristic". I will describe a few of them and give some references, and ...
- 6,337
10
votes
2
answers
387
views
What is Kept Fixed for Flexible Spheres
For background to this question much recent exciting related things, see this videotaped lecture by Alexander Gaifullin.
Consider a triangulation $K$ of a two-dimensional sphere and consider maps ...
- 6,337
7
votes
1
answer
318
views
Finding a short path using $(0.99n)!$ permutations
Suppose I have $n$ points $x_1,\dots,x_n$ that are all independent uniform samples in the unit square, and I'd like to find a short path (in terms of Euclidean length) that touches all of them (a ...
- 61.9k
6
votes
1
answer
585
views
Union of almost Hamming balls
This question is connected with my previous question: Union of Hamming balls
Let $V \subseteq \{0,1\}^n$, $\log|V| = k < 0.9n$.
Harper's theorem states that the set $V_r:= \bigcup_{x \in V} V_r(...
CommunityBot
- 1
2
votes
1
answer
354
views
Union of Hamming balls
Let $V \subseteq \{0,1\}^n$, $\log|V| = k$. Consider
$V_r:= \bigcup_{x \in V} V_r(x)$, where $V_r(x)$ is a Hamming full-ball of radius $r$ and center $x$.
What is a lower bound for the cardinality ...
- 4,679
5
votes
1
answer
289
views
When does there exist a convex polyhedron with given edge lengths?
Let $n$ be a positive integer, and let $n = \ell_1 + \dots + \ell_k$ be
a partition of $n$. Then there exists a convex polygon with side lengths
$\ell_1, \dots, \ell_k$ if and only if all of the $\...
- 10.7k
4
votes
2
answers
306
views
k nearest points
Assume $n$ points $P_i \in \mathbb{R}^2, i \in {1,2,...,n}$. For each point there is a $k$ nearest neighbour $(k<n)$, or equivalently for each point $P_i$ there is one circle with center the point $...
- 153
3
votes
1
answer
190
views
How many points are in such set with the same norm-2
Let $L=[a,b]\cap\mathbb{N}$ with $a,b\in\mathbb{N}$, let $D\in\mathbb{N}$, and let $C=L^D$. Then I would like to know how many points are there in $C$ with the same given norm-2 $d$. I.e., I'm looking ...
CommunityBot
- 1
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
10
votes
1
answer
277
views
Optimization of points on a plane
Suppose we have $n$ points on a plane. Let $D$ be the sum of the squares of all the pairwise distances between the points. Let $A$ be the area of the convex hull. What is the minimum possible value of ...
- 15.8k
5
votes
2
answers
237
views
Volume of the convex hull of the set of all graphic sequences of a given length
Consider the set of all graphic sequences with $n$ elements as a subset of $\mathbb{R}^{n}$, namely let
$$D(n)=\{(d_{1},\dots,d_{n})\in\mathbb{Z}_{+}^{n}:d_{1}\geq\dots\geq d_{n},\ \sum_{i=1}^{n}d_{i}\...
7
votes
1
answer
209
views
Are the primary parallelotopes classified? (equivalently, Voronoi cells of lattices)
A primary parallelohedron is a polyhedron that can fill space with infinite translated copies.
It is known (e.g., Coxeter, H. S. M. Regular Polytopes, 3rd ed. New York: Dover, pp. 29-30, 1973; or, ...
- 5,971
5
votes
0
answers
135
views
What is the maximal convex hull in $\mathbb R^3$ of a tree with fixed total length?
Denote by $\mathcal T_n$ the set of all trees on $n$ nodes. For a tree $T\in\mathcal T_n$, we assign to each edge a non-negative length such that the sum of all lengths is 1. Denote by $v(T)$ the ...
CommunityBot
- 1
4
votes
1
answer
226
views
Combinatorial description of a 120-cell
I'd like a combinatorial description of the 1-skeleton of the 120-cell (roughly) along the lines of the following description of the 1-skeleton of a dodecahedron.
(View all elements of product sets ...
- 85.6k
5
votes
1
answer
303
views
Intersection of rotating regular polygons
This question has a recreational flavor, but may not be
entirely uninteresting.
Let $P_k$ be a unit-radius regular polygon of $k$ sides,
and $P_n$ a unit-radius regular polygon of $n \ge k$ sides.
...
- 85.6k
4
votes
0
answers
94
views
Finding closest set of K disjoint hyperspheres to a point in $\mathbb{R}^n$ with uniform radius
I am interested in the following problem: in $\mathbb{R}^n$, we have $N$ overlapping hyperspheres all with the same radius. Given a point $p$ in $\mathbb{R}^n$, the objective is to find the $K$ non ...
- 161
12
votes
2
answers
518
views
Embedding Z into Z^2 with large distortion
Is it possible to find a 2-way infinite (self-avoiding) path $\{x_i\}_{i\in \mathbb Z}$ in the standard Cayley graph of $\mathbb Z^2$, i.e. the square grid, such that the distance between $x_i$ and $...
- 630
3
votes
1
answer
222
views
Number of lines of symmetry of a set of lattice points
Given some finite $S\subseteq\mathbb R^2$, it is clearly possible for $S$ to have arbitrarily many lines of symmetry. However, it is not very clear if the same is necessarily true for subsets of $\...
- 47.3k
13
votes
2
answers
572
views
The most number of points that realize only $k$ distinct distances
For $k \ge 1$, let $f_d(k)$ be the largest possible number of points $p_i$
in $\mathbb{R}^d$ that determine at most $k$ distinct (Euclidean) distances,
$\|p_i-p_j\|$.
Example. For points in the plane ...
- 105k
5
votes
0
answers
213
views
Euclidean Minimum Spanning Trees Restricted to One Vertex Per Grid Cell
Given an $n \times n$ grid with unit grid cells, and one point from the interior
of each cell, what is are best possible lower and upper bounds for lengths of minimum spanning trees? The lower bound ...
CommunityBot
- 1
2
votes
0
answers
84
views
Euclidean minimum spanning trees intersecting each unit square
The recent question "Euclidean Minimum Spanning Trees Restricted to One Vertex Per Grid Cell" can be restated in terms of "minimum spanning trees intersecting each (closed) lattice square of an $n\...
CommunityBot
- 1
2
votes
0
answers
265
views
How large can a set of nearly equidistant points be?
Suppose that $D$ is a set of points in $\mathbb{R}^{k}$ such that all pairwise distances between them belong to $[1,1+\epsilon]$.
It seems that such a set cannot be very large and that its ...
- 6,962
10
votes
1
answer
300
views
Optimal shape for stabbing balls in $\mathbb{R}^3$
I have radius $r < \frac{1}{2}$ congruent balls with centers randomly distributed uniformly within a region,
say, within a unit-radius sphere $S$.
I shoot a ray/path through $S$, hoping to ...
- 28k
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 ...
- 23.7k
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 ...
- 356
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 ...
- 6,210
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 ...
CommunityBot
- 1
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 \...
CommunityBot
- 1
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 ...
- 23.7k
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{...
CommunityBot
- 1
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 ...
- 151k
29
votes
1
answer
2k
views
High-Dimensional Analogs of Polygon Spaces
[Edit: I had a mistake in the numerology (took d=6,5 instead of d=5,4). Edit: I mistakenly identified my mistake, it is 6,5 but I got the indices shifted by one.]
Background: Polygon spaces
Given a ...
CommunityBot
- 1
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 ...
CommunityBot
- 1
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 ...
- 6,101
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 ...
- 7,276
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 $\...
- 7,276
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 - ...
- 45k
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 ...
- 148k
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 ...
CommunityBot
- 1
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 ...
- 6,101
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$. ...
- 18.9k
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
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$ ...
- 1,961
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 ...
- 141
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$ ...
- 25.7k