All Questions
Tagged with co.combinatorics mg.metric-geometry
64 questions with no upvoted or accepted answers
17
votes
0
answers
1k
views
Almost monochromatic point sets
There are many sort of equivalent theorems about monochromatic configurations in finite colorings, such as Van der Waerden, Hales-Jewett or Gallai's theorem, the latter of which states that in a ...
- 18.8k
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
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}\...
- 794
11
votes
0
answers
488
views
Are there 100 points that are part of every half-density part of the plane?
Is there a configuration $P$ that consists of 100 points of the plane such that every $X\subset\mathbb R^2$ whose density is half contains an isometric copy of $P$?
I am deliberately being vague ...
- 18.8k
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
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
9
votes
0
answers
144
views
Which polytopes have compact realization spaces?
Let $P\subset\Bbb R^d$ be a convex polytope.
Its reduced realization space is the space of all combinatorially equivalent polytopes modulo projective transformations.
I am interested in polytopes for ...
- 13.6k
9
votes
0
answers
365
views
How to count integer lattice points close to a subspace of $\mathbb R^n$?
Consider $m$ linearly independent vectors in $n$-dimensional Euclidean space, $v_1,...,v_m \in \mathbb R^n$ where $1\leq m<n$, and let $U := {\rm span}(v_1,...,v_m)$ denote the $m$-dimensional ...
- 686
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
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-...
7
votes
0
answers
162
views
Approximating any convex shape in $\mathbb{R}^d$ with a polytope having $\mathrm{poly}(d)$ facets
We denote by $V(A)$ the $d$-volume of any convex set $A$. Furthermore, given any two convex sets $A,B\in\mathbb{R}^d$, we denote by $V_{A,B}$ the $d$-volume of the symmetric difference $V\left(A \...
- 1,677
7
votes
0
answers
254
views
Set of unit vectors such that among any three there is an orthogonal pair
I was fascinated by the solutions of Problem 8 of the IMC 2021 contest, which can be summarized as:
Theorem 1. Let $v_1,\dotsc,v_N$ be distinct unit vectors in $\mathbb{R}^n$ such that among any three ...
- 105k
7
votes
0
answers
122
views
Discrepancy of the finite approximation of the Lebesgue measure
Let $\mu$ be a probabilistic measure on the unit square $Q$ which is the average of $N$ delta-measures in some points in this square; let $\lambda$ denote the Lebesgue measure on $Q$. What is the rate ...
- 109k
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
6
votes
0
answers
247
views
An extension of Erdos' distinct distances problem based on circles of various radii
Consider a collection $C_1,C_2, \dots, C_n$ of circles in the plane and suppose that the center of $C_i$ is $o_i$ and the radius of $C_i$ is $r_i$. We will define the relative distance between the ...
- 24.7k
6
votes
0
answers
1k
views
How to pack 27 $a\times b\times c$ blocks into a cube of side $a+b+c$ with some kind of symmetry?
Recently I stumbled on the problem quoted here about a geometric proof of the AM-GM inequality $$(a_1+\cdots+a_n)^n\ge n^n a_1\cdots a_n$$ by packing $n^n$ rectangular $ n$-dimensional boxes of sides $...
- 13.4k
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
6
votes
1
answer
254
views
Triangulations of convex surfaces
Let $M$ be a smooth closed positively curved surface in Euclidean 3-space, $T$ be a geodesic triangulation of $M$, and $E$ be the edge graph of the convex hull of vertices of $T$.
It is easy to see ...
- 7,149
5
votes
0
answers
127
views
Does the permutohedron satisfy any minimal distortion property for graph metric vs Euclidean distance?
We can look on the permutohedron as a kind of "embedding" of the Cayley graph of $S_n$ to the Euclidean space. (That Cayley graph is constructed by the standard generators, i.e. ...
- 24.9k
5
votes
0
answers
235
views
Arrangement of points, lines, and planes
Is it possible to construct a finite nontrivial arrangement of points, lines, and planes in 3-dimensional Euclidean space with the following properties?
every line is incident with four points and ...
- 2,773
5
votes
0
answers
190
views
The existence of $n$-sided cells in regular $m$-gons
For any integer $n >= 3$, does there exist a regular
$m$-gon with all diagonals drawn containing a cell with $n$ sides?
See A342222 and its cross-references.
Regular polygon on the Wiki.
&...
- 251
5
votes
0
answers
313
views
Trade-off between covering number, ball radius and diameter of $d$-dimensional shapes
Given any $d$-dimensional shape $X$ in the Euclidean space, let $\ell(X)$ be the length of the longest line segment connecting two points of $X$. How can we prove the following statement?
There exists ...
- 1,677
5
votes
0
answers
199
views
Existence of a honeycomb composed by nearly-hyperspherical $d$-dimensional cells having the same shape and size
Let $\mathcal{H}$ the class of all honeycombs composed by $d$-dimensional cells $C$ having all the same shape and size in a $d$-dimensional space $\mathcal{S}$.
Let $s(C)$ and $\ell(C)$ be ...
- 1,677
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 ...
- 13.4k
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 ...
user71114
4
votes
0
answers
66
views
Convergence of graph geodesics to geodesics on metric spaces
Let $(X,d)$ be a compact length space metric space $\mathbb{X}_{\delta}$ be a $\delta$-packing on $X$ and, for every $k\in \mathbb{N}_+$, let $G_{k,\delta}=(\mathbb{X}_{\delta},\mathcal{E}_k,W_k)$ ...
- 364
4
votes
0
answers
70
views
A question about the existence of surjective contractions
A few years ago I was doing some research in origami, and was motivated to as the following questions:
Consider $\mathbb{R}^2$ with the Euclidean metric and Lebesgue measure. Does there exist a ...
- 384
4
votes
0
answers
222
views
What does it mean "parallel"?
I am thinking on a strict definition of the notion of parallel affine sets in a linear space and came to the following
Definition 1: An affine set $A$ is parallel to an affine set $B$ in a linear ...
- 41.8k
4
votes
0
answers
144
views
Approximation of a convex shape in the $d$-dimensional Euclidean space for $d\gg 1$
We are given a convex shape $C$ lying inside the hypercube $[0,1]^d$ in the $d$-dimensional Euclidean space. Let the volume of $C$ be $\tfrac12$ (I guess nothing changes for any other fixed constant ...
- 1,677
4
votes
0
answers
92
views
Possible cardinalities of spherical tiling
Suppose that we have a tiling of $n$-dimensional (I want to get answer for $n = 4$, but general result would be nice!) sphere by isometric tiles strictly contained inside the right-angled simplex. ...
- 4,600
4
votes
0
answers
246
views
Distance properties of the permutations of a set of points in a Euclidean space
We are given a set of $n$ distinct points $S=\{\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_n\}$ in a Euclidean space $\mathbb{R}^d$, where the distance between two points $\mathbf{x}_i,\mathbf{x}_j\...
- 1,677
4
votes
0
answers
81
views
Number of orders of distances between points on a line
Points $a_1, a_2, \dots, a_n$ on a line form a set from $n(n-1)/2$ distances between them. Suppose all that distances are different, numerating them from the shortest to the longest one we obtain some ...
- 1,431
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
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
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 ...
3
votes
0
answers
109
views
What Cayley graphs arise as nodes+edges from "nice" polytopes and when are these polytopes convex?
The Permutohedron is a remarkable convex polytope in $R^n$, such that its nodes are indexed by permutations and edges correspond to the Cayley graph of $S_n$ with respect to the standard generators, i....
- 24.9k
3
votes
0
answers
187
views
Approximating any $d$-dimensional convex shape that occupies a constant fraction of its bounding box with a polytope having $\mathrm{poly}(d)$ facets
Given any convex set $A\in\mathbb{R}^d$, we denote by $V(A)$ its $d$-volume. Furthermore, given any two convex sets $A_1,A_2\in\mathbb{R}^d$, we denote by $V_{A_1,A_2}$ the $d$-volume of the symmetric ...
- 1,677
3
votes
0
answers
134
views
Two questions on counterexamples to Borsuk's conjecture and ball-packings
In 1933 Karol Borsuk conjectured the following
Can every bounded subset $E$ of $\mathbb{R}^d$ be partitioned into $(d+1)$ sets, each of which has a smaller diameter than $E$?
Whilst new to this ...
- 31
3
votes
1
answer
484
views
On some infinite planar arrangements with triangles
Background: Given a convex region C. One can define a graph corresponding to a planar arrangement of non overlapping congruent copies of C - each unit C is a node and an edge connects it to another ...
- 5,979
3
votes
0
answers
137
views
Aperiodic tile with rational area
Margulis and Mozes constructed aperiodic tiling system on the hyperbolic plane consisting of a single tile(hyperbolic polygon) whose area (or each inner angle) is irrational multiple of $\pi$. Having ...
- 745
3
votes
0
answers
106
views
How many positions of a tile can occur in a periodic tiling?
In my recent question about polygonal tilings where tiles can occur in infinitely many positions, both constructions given as solutions are of self-similar nature. This means in particular that there ...
- 13.4k
3
votes
0
answers
59
views
2-complexes which are coarse-grained graphs
A polygonal complex $K$ is said to be geometrically 2-dimensional if the topological space it defines is a surface (boundaries are allowed). It is said to be $C$-quasi-1-dimensional (for some $C>0$)...
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
2
votes
0
answers
48
views
Maximum coverage of an orthogonal polygon using $k$ rectangles
I have an orthogonal polygon (all edges are horizontal or vertical) which is convex (no holes in any row of column of the polygon).
I would like to cover as much as possible of this orthogonal polygon ...
- 21
2
votes
0
answers
162
views
Root system terminology
Let $\Phi$ be a root system. In a paper I'm writing, I need to work with subsets $\Phi' \subset \Phi$ satisfying the following two conditions:
For all $\lambda_1,\lambda_2 \in \Phi'$ and $c_1,c_2 \...
- 21
2
votes
0
answers
56
views
Classification of Moufang planes of real dimension 16
Incidence geometry is not really area of expertise so I'm asking here: are all Moufang planes of 16 dimension already classified?
I'm not just interested in the compact ones. Is there already a ...
- 295
2
votes
0
answers
131
views
Maximum number of regions in a disk partitioned by pairs of parallel chords
We are given a disk $D$ in $\mathbb{R}^2$. Let $C$ be its boundary (i.e., the circle bounding $D$ on its plane). Let $P(n,d)$ be a set of $n$ pairs of chords of $C$ such that for each $\{c,c'\}\in P(n,...
- 1,677
2
votes
0
answers
131
views
Optimal way to group points in the plane into clusters
Consider a strictly decreasing sequence $d = (d_k)_{k\ge 1}$ of distances in $(0,1)$. Given a constant $C>2$, we say that $d$ has the $C$-grouping property if any finite non-empty subset $S$ (of ...
- 1,761
2
votes
0
answers
59
views
Totally distance non-preserving transformations
JL lemma (https://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma)
guarantees if you have a set of $K$ points in $\Bbb R^N$ a random transformation guarantees that the set can be projected ...
- 13.9k
2
votes
0
answers
149
views
Cardinality of compact doubling metric spaces with fast growing covering numbers
In this question it was established that if the growth of the number of branches of an at-most $k$-branching tree is $\Omega(k^n)$ (in the Knuth sense), then the tree has continuum many branches.
...
- 12.4k