All Questions
Tagged with co.combinatorics mg.metric-geometry
246 questions
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}\...
- 18.9k
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) ...
CommunityBot
- 1
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 ...
- 1,411
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 ...
CommunityBot
- 1
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 ...
- 50.8k
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$, ...
- 5,492
11
votes
1
answer
506
views
"minimal" embedding of bipartite graphs on a sphere
Here is an easy to pose problem I've encountered (but haven't been able to solve or disprove):
Let (V,E) be a bipartite graph with the following property –
the girth of the graph (i.e. the length of ...
- 45k
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 ...
CommunityBot
- 1
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 ...
CommunityBot
- 1
3
votes
2
answers
1k
views
3D Venn diagrams
Are there higher-dimensional versions of the concept of rotationally symmetric Venn diagrams, with closed curves replaced by closed surfaces or higher manifolds ?
CommunityBot
- 1
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 ...
CommunityBot
- 1
5
votes
4
answers
1k
views
Coloring Points in the Plane
Suppose one wants to color the points in the plane so any two points at distance one apart are different colors. How many colors are needed?
I heard this problem when I was a kid. Back then the most ...
- 14k
12
votes
3
answers
2k
views
To what extent is convexity a local property?
A polyhedron is the intersection of a finite collection of halfspaces. These halfspaces are not assumed to be linear, i.e. their bounding hyperplanes are not assumed to contain the origin. The ...
- 265
4
votes
0
answers
84
views
Node-Weighted Euclidean Steiner Trees
I would like to know whether the following problem, including algorithms to solve it (exact or approximations) has been studied.
A finite set of positive-weighted points are given in the n-...
- 111
7
votes
3
answers
866
views
Not quite regular polyhedra
Take a naive interpretation of regular polyhedra:
All vertices (including epsilon ball) congruent
All edges congruent
All faces congruent
We can now find interesting families by removing one ...
- 3,532
7
votes
2
answers
337
views
non-rigidity of interior points in polyhedral triangulations?
It's well-known that any compact polyhedron $P$ in $\mathbb{R}^n$ (we talk about piecewise-linear setting there, i.e. $P$ is a finite union of compact convex polytopes) can be triangulated into (...
- 14k
9
votes
1
answer
523
views
The volume of the “unit ball” in $\mathbb{R}^{m\times n}$ with respect to the cut norm
This question is inspired by the question “ε-nets with respect to the cut norm” by the user Aaron, which had been reposted to cstheory.stackexchange.com.
The cut norm ||A||C of a matrix A=(aij)∈ℝm×n ...
CommunityBot
- 1
14
votes
1
answer
837
views
Applications of the GCD metric
In the pre-MO era, I once realized that on the integers, the function
$$
d(m, n) := \sqrt{\log \frac{\sqrt{mn}} {\text{gcd}(m,n)}}\ ,
$$
is a metric (all properties are easily verified; in fact ...
- 28.6k
4
votes
0
answers
443
views
Intersection of pencils in $\mathcal{R}^2$
Consider $9n$ pencils through non-collinear points $p_1, \ldots , p_{9n}$ in $R^2$ each consisting of at most $n$ concurrent lines. Define the intersection $S$ of these pencils to be the set of points ...
- 85.6k
4
votes
1
answer
451
views
When can a 3-dimensional triangulation be isometricaly embedded in R^n?
Consider a triangulation of some bounded region of $R^3$ with a (finite) set of tetrahedra (like in Regge calculus). It can be thought of as a simplicial 3-complex with specified lengths of edges. The ...
- 45k
3
votes
3
answers
390
views
Can we uniquely define a graph to have the topology of a polytope via proper edge length selection?
I'll ask you to consider a situation wherein one has a series of edges for a graph, $(e_1, e_2, ..., e_N) \in E$, each with a specifiable length $(l_1, l_2, ..., l_N) \in L$, and the goal is to insure ...
- 17.9k
2
votes
1
answer
370
views
Large subgroups of the Hamming cube
Let's consider the abelian group $\mathbb{Z}^N_2$ equipped with the Hamming metric (the hypercube).
Suppose I have a subgroup of this hypercube (not necessarily a subcube) which is generated by a set ...
- 6,342
12
votes
3
answers
707
views
A "round" lattice with low kissing number?
Historically, the lattices with high density were studied intensively, e.g. E_8 lattice or Leech Lattice. However, there are situations that lattices with low kissing number are required. Specifically,...
CommunityBot
- 1
8
votes
0
answers
358
views
Coloring toroidal polyhedra with convex faces?
Consider a toroidal polyhedron, which is a topological torus, in which all faces are planar, two faces meet in at most an edge, and adjacent faces are not coplanar. The Szilassi polyhedron has 7 non-...
13
votes
0
answers
751
views
$\epsilon$-nets with respect to the cut norm
The cut norm $||A||\_C$ of a real matrix $A = (a_{i,j}) \in \mathcal{R}^{n\times n}$ is the maximum over all $I \subseteq [n], J \subseteq [n]$ of the quantity $\left|\sum_{i \in I, j \in J}a_{i,j}\...
CommunityBot
- 1
3
votes
0
answers
233
views
How many set partitions on a big cube’s boundary arise from cubomino decompositions of the solid cube?
Introduction. This is a counting question about configurations that can appear on the outside of assembled Soma cube-like puzzles. More specifically, it’s about the ways in which the pieces of an ...
- 588
8
votes
2
answers
383
views
Do singular values of a point set determine its shape?
Suppose I have $k$ points in $d$ dimensions. Let A be a $k\times d$ matrix with $i$th row giving the coordinates of $i$th point. Do singular values of this matrix have an interpretation as some kind ...
CommunityBot
- 1
15
votes
3
answers
1k
views
Representation of vectors in $\mathbb{R}^2$ via differences of small vectors.
Is the following fact true?
Let $v_1,\ldots, v_k \in \mathbb{R}^2$, $\|v_i\|\leq 1$, be vectors that add up to zero. Does there exist a permutation $\sigma\in S_k$ and vectors $w_1,\ldots, w_k \...
- 43.2k
7
votes
1
answer
1k
views
Burnside's Lemma and Geometry
I think one of the most interesting results in Elementary Group Theory is the so-called "Burnside's Lemma", counting the numbers of orbits of a (finite) group action.
I wonder if there is any (...
- 14.4k
6
votes
3
answers
1k
views
How can I embed an N-points metric space to a hypercube with low distortion?
I have a N-point metric space defined by the pairwise distance matrix. I want to encode these N points with binary strings, i.e. each point will be mapped to a vertex in a hypercube. The lengths of ...
- 2,401
2
votes
4
answers
222
views
How to compare finite point sets in normed spaces?
I want to define a "distance" between two subsets $A, B$ of a normed space $(V, \|\cdot\|)$ both with (at most) $n$ elements. A straightforward way for me to do this would be to define
$$ d(A, B) := \...
- 60.5k
8
votes
1
answer
2k
views
Expected number of steps for a discrete random walk to visit every point on an N-dimensional rectangular lattice
Please imagine a discrete random walk on an N-dimensional rectangular lattice with dimensional lengths $(l_1, ..., l_N) \in L$ and total lattice points $P = \prod{l_i}$, for $i = 1, ..., N$. At each ...
- 4,014
15
votes
1
answer
11k
views
Maximum number of mutually equidistant points in an n-dimensional Euclidean space is (n+1). Proof? [closed]
How to prove that the maximum number of mutually equidistant points in an n-dimensional Euclidean space is (n+1)?
- 7,105
4
votes
1
answer
1k
views
Finding integer points on an N-d convex hull
Suppose we have a convex hull computed as the solution to a linear programming problem (via whatever method you want). Given this convex hull (and the inequalities that formed the convex hull) is ...
- 151k
5
votes
2
answers
523
views
Maximal area coverable by $k$ disjoint isosceles triangles contained in a triangle of area 1.
Given a triangle $\Delta$ of unit area, how much area can always be covered by $k$ isosceles triangles contained in $\Delta$ and intersecting at most at their boundaries?
The answer is easy for $k=1$....
- 6,523
2
votes
1
answer
247
views
Are combinatorial configurations whose Levi graphs may be represented as covering graphs over voltage graphs realizable with pseudolines?
This question is related to this previous question. Many combinatorial configurations have Levi graphs which may be represented as derived graphs obtained from voltage graphs over a cyclic group; in a ...
CommunityBot
- 1
9
votes
1
answer
604
views
Which changes of metric fix all open balls of a metric space?
In an earlier question, I was interested in counting the number of metric spaces on N points, where I considered two metric spaces to be the same if they had the same collection of open balls. Two ...
CommunityBot
- 1
12
votes
3
answers
1k
views
distance regular metric spaces
A metric space (V,d) will be called distance regular if for every distances a>0, b, c a nonnegative integer p(a,b,c) is defined, so that whenever d(B,C)=a, there are precisely p(a,b,c) points A ...
