All Questions
Tagged with reference-request discrete-geometry
174 questions
2
votes
2
answers
163
views
References for geometric properties of optimal Euclidean traveling salesman tour
Consider a finite set of points $V \subseteq \mathbb{R}^2 $ as a TSP-instance under the standard $\| \cdot \|_2$ norm. (TSP stands for traveling salesman tour.) We know that every optimal TSP tour $T$ ...
CommunityBot
- 1
1
vote
0
answers
76
views
Shellable non-pseudomanifolds with dimension greater than 2
Shellability of simplicial balls and spheres (simplicial complexes whose geometric realizations are homeomorphic to balls and spheres) has been studied quite extensively. There are many explicit ...
3
votes
0
answers
208
views
Reference request: Carathéodory-type theorem for convex hulls of closed sets
I'm looking for a reference for the following theorem.
Theorem Let $X$ be a closed subset of $\mathbb{R}^N$, and let $a$ be a point of its convex hull $\operatorname{conv}(X)$. Then there exist ...
- 27.7k
3
votes
1
answer
108
views
Has this random process been studied on grid graphs?
As an offshoot of a different discussion I got curious about (uniform) random spanning trees on grid graphs (torus graphs in particular, to avoid having to think about edge effects) and what their ...
- 8,992
4
votes
1
answer
493
views
Counting number of points on a lattice in a hypercube
Suppose I have a lattice $\Lambda \in \mathbb{R}^n$. Let $X_i >0$ for $i=1,..,n$. I am interested in some references regarding counting number of points of $\Lambda$ inside $[-X_1, X_1] \times \...
- 105k
22
votes
2
answers
900
views
Is every 1-million-connected graph rigid in 3D?
It is an old result that every $6$-connected graph is rigid in $\mathbb{R}^2$:
Lovász, László, and Yechiam Yemini. "On generic rigidity in the plane." SIAM Journal on Algebraic Discrete ...
- 32.1k
3
votes
0
answers
93
views
Minkowski problem for polytopes: the origin of necessary condition
Minkowski's uniqueness theorem for polytopes concerns the specification of the shape of a polytope by the directions and measures of its facets.
Theorem (Minkowski). Let $A_i$ be positive faces areas ...
- 12.3k
21
votes
0
answers
453
views
Does every 5-celled animal tile the plane?
An animal in the plane is a finite set of grid-aligned unit squares in $\mathbb{R}^2$. (The definition is the same as a polyomino, but where we relax the connectivity requirement.) One may ...
- 3,068
9
votes
4
answers
474
views
Minimum number of common edges of triangulations
Let $S$ and $T$ be two triangulations.
We define
$c(S,T)$ as the number of edges shared by $S$ and $T$.
With this, we can define
$f(n) = \min_{P} \min_{S,T} c(S,T)$.
Here the first minimum goes over ...
- 5,409
6
votes
0
answers
132
views
Have the affine simplicial line arrangments been enumerated?
I am looking for a classification (or attempt at enumeration) of affine simplicial line arrangements.
A line arrangment is a family of straight lines in $\Bbb R^2$. It is simplicial if all regions are ...
- 13.6k
0
votes
1
answer
173
views
Which simplicial complexes are completely determined by the 1-skeleton of their dual polyhedral complexes?
Consider the following line of reasoning that shows certain simplicial complexes (of arbitrary dimension) are completely determined by corresponding graphs:
The facet complex of any simplicial ...
- 50.8k
1
vote
2
answers
232
views
What does the extension theorem for tilings state?
I have seen several references to the so-called Extension Theorem in the context of tilings of Euclidean space.
E.g. in "The Local Theorem for Monotypic Tilings" one reads
The Extension Theorem [......
- 35.5k
1
vote
0
answers
145
views
Lower bound $|\sum_{x \in X} \phi(x) - \int_{\mathbb{R^2}} \phi(x) \, dx | \geq C f(\phi)$
I asked this question on math.stackexchange before, but with a bad formulation. I think the problem is quite complicated, so I decided to ask it here. Tell me if I shouldn't.
Very recently, I ...
- 183
4
votes
1
answer
282
views
A combinatorial problem about sequences of numbers
In this math.stackexchange question Adam Rubinson asked (I paraphrase):
Given a natural number $r$, what is the least number $n$ such that every strictly increasing sequence of $n$ real numbers has a ...
- 13.4k
2
votes
0
answers
65
views
Structure Theory for Tree Decompositions
I that $G=(V,E,W)$ is a weighted graph with positive edge weights and a finite set of vertices $K$. Let $0\le k,M\le K$ be a fixed integer.
Is is known when $G$ admits the following type of ...
- 21
2
votes
0
answers
77
views
Flexagons and noncrossing partitions
Turns out a couple of series related to the faces of flexagons
popped up in my explorations of combinatorial reciprocities in a group algebra for sets of partition polynomial (ParPs) related to the ...
- 10.5k
3
votes
0
answers
116
views
A theory of refined h- and f-polynomials for the permutahedra, associahedra, noncrossing partitions, and tropical Grassmannians (references)
Looking for references (insights) on a theory encompassing a notion of refined face polynomials and their associated refined h-polynomials that are generalizations of the relation between ordinary f-...
- 10.5k
29
votes
3
answers
2k
views
Growing random trees on a lattice $\rightarrow$ Voronoi diagrams
Imagine growing trees from $k$ seeds on a square $n \times n$ region
of $\mathbb{Z}^2$.
At each step, a unit-length edge $e$ between two points of
$\mathbb{Z}^2$ is added.
The edge $e$ is chosen ...
- 2,821
2
votes
1
answer
157
views
Bound for a sequence of vertices in a graph
I have come across the following problem. Let $d\in\mathbb{N}$. Let $G$ be any $k$-regular connected directed graph with $n$ vertices, no parallel edges and no 2-cycles. For a vertex $v\in G$, let $...
- 167
3
votes
0
answers
135
views
Intersecting the unit n-cube and (n-1)-planes
(Is this a known problem?)
Question Let $\ 1<n\in\mathbb N.\ $ What is the greatest $(n-1)$-area
$\ S(n)\ $ of $\ L\cap I^n\ $ where $\ I^n\subseteq\mathbb R^n\ $ is the unit cube, and $\ L\ $ ...
- 6,337
2
votes
0
answers
233
views
Do you know this formula for the scalar product in barycentric coordinates?
I've found a formula for a scalar product in barycentric coordinates which I think is pretty cool. I hope that it's new. Is it?
Suppose that you have points $x_1,\dots,x_n$ sitting in general position ...
- 1,048
21
votes
2
answers
1k
views
Forbidden mirror sequences
Let $\cal{M}$ be a finite collection of two-sided mirrors,
each an open unit-length segment in $\mathbb{R^2}$,
and such that the segments when closed are disjoint.
A ray of light that reflects off the ...
- 2,821
11
votes
1
answer
534
views
How much smaller is the Čech complex than the Vietoris-Rips complex?
The Čech complex
is a subcomplex of the
Vietoris-Rips complex.
The V-R complex
includes as a simplex a set of points with pairwise
distances at most $\epsilon$,
whereas the Č complex
includes as a ...
- 1,611
3
votes
0
answers
86
views
Sums over lattice points in homogeneously expanding domains
In his book Algebraic Number Theory (2nd ed., Thm 2 in p.128), Lang proves the following (well-known) auxiliary result. Let $D\subset\mathbb{R}^N$ with $(N-1)$-Lipschitz parametrizable boundary. Let $...
- 3,107
0
votes
1
answer
86
views
Lattice-point-free body diameter
The following interesting problem was asked at Aops and I wonder if it was based on some research paper:
Let $K$ be a convex body in $\mathbb R^2$, such that the diameter of $K$ is less than $\sqrt2$....
- 109k
4
votes
0
answers
234
views
To whom is the classification of atomic, modular finite lattices due?
Here lattice means a poset with meets and joins. A lattice is called atomic if every element is a join of atoms. There are a few different ways to define modular for finite lattices: one is that the ...
- 24.2k
16
votes
4
answers
2k
views
Point sets in Euclidean space with a small number of distinct distances
It is well known and not hard to prove that the regular simplex in n-dimensions is the only way to place n+1 points so that the distance between distinct pairs of points is always the same. My general ...
- 2,821
34
votes
6
answers
8k
views
Covering a unit ball with balls half the radius
This is a direct (and obvious) generalization of the recent MO question, "Covering disks with smaller disks":
How many balls of radius $\frac{1}{2}$ are needed to cover completely a ball of ...
- 2,821
23
votes
1
answer
714
views
Covering the unit sphere in $\mathbf{R}^n$ with $2n$ congruent disks
Let $v_i$ be $2n$ points in $\mathbf{R}^n$, with equal distance $|v_i|$ from the origin. Suppose that the convex hull of these points contains the unit ball. Is it known that $|v_i|\geq\sqrt{n}$? ...
- 7,194
1
vote
1
answer
378
views
Bridges between geometry and combinatorics
Geometry and combinatorics are two different branches of mathematics. Does there exist any connection between them? In many cases, mathematicians solve some geometric problems by reducing them to a ...
- 8,435
3
votes
0
answers
144
views
Counting homologically non-trivial and trivial cycles in $n \times n$ square lattice torus of a given length $l \geq n$
This should be a fairly standard question but I can't really seem to find a reference.
Consider an $n \times n$ square lattice torus $\mathbb T$. Given a length $l \geq n$, what is the number of ...
- 269
6
votes
2
answers
544
views
On circles and ellipses drawn on an infinite planar square lattice
Consider a plane with a square lattice formed by all points with both coordinates as integers. As can be easily seen, a simple parabola can be found that passes through infinitely many of the square ...
- 5,979
21
votes
5
answers
1k
views
Is a rhombus rigid on a sphere or torus? And generalizations
If a rectangle is formed from rigid bars for edges and joints
at vertices, then it is flexible in the plane: it can flex
to a parallelogram.
On any smooth surface with a metric, one can define a ...
- 4,713
11
votes
2
answers
1k
views
Which (semi)regular polyhedra are combinations of two others?
The convex combination of convex polytopes is a convex polytope.
An example in $\mathbb{R}^2$ is that a regular octagon
can be obtained as $\frac{1}{2} S + \frac{1}{2} S'$,
where $S$ is a square and $...
- 4,713
22
votes
1
answer
970
views
Grothendieck on polyhedra over finite fields
In Grothendieck's Sketch of a Programme he spends a few pages discussing polyhedra over arbitrary rings and concludes with some intriguing remarks on specializing polyhedra over their "most ...
- 12.9k
1
vote
2
answers
100
views
Name for the weight function defined as the integer sum of coordinate entries from ${\mathbf F}_p$
In ${\mathbb F}_p^n$, $p$ prime one may define a weight function on vectors in various ways such as Hamming, or Lee weight. (These two weights correspond nicely to the respective distances from $\bar ...
- 47.4k
5
votes
1
answer
266
views
Contracting a set to a ball
$\newcommand\R{\mathbb R}\newcommand\S{\mathbb S}$
Question 1: Let $S$ be a nonempty measurable subset of $\R^n$. Let $B$ be a closed ball in $\R^n$ such that $m(B)=m(S)$, where $m$ is the Lebesgue ...
- 128k
2
votes
2
answers
164
views
Angle between a point in a convex polytope and the nearest point of a face
Let $P \subset \mathbb{R}^d$ be a convex polytope, and let $F$ be a face of $P$ (of co-dimension 1, let's say). Now let $x \in P \setminus F$ and let $y \in F$ be the nearest point of $F$ to $x$. Then ...
- 11
26
votes
7
answers
3k
views
What's that shape? Inferring a 3D shape from random shadows
Let $P$ be a bounded, simply connected region of $\mathbb{R}^3$.
$P$ could be a polyhedron, or a smooth shape, or an arbitrary shape;
I'll assume below that $P$ is a (non-degenerate, perhaps non-...
- 1,446
15
votes
2
answers
737
views
Tiling survey that updates "Tilings and patterns"?
Can anyone suggest a survey (or surveys) that provides an update to Tilings and patterns by Grunbaum and Shepard? If there's a more recent book, that would be fantastic, but I don't see one.
I am ...
- 63.9k
7
votes
1
answer
299
views
Lipschitz-continuity of convex polytopes under the Hausdorff metric
Recently, I proved the following Lipschitz-continuity like result for convex polytopes:
Let $A\in\mathbb R^{m\times n}$ and $b,b'\in\mathbb R^m$ be given such that $\{x\,:\,Ax\leq 0\}=\{0\}$ (which ...
- 695
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 ...
- 32.1k
5
votes
2
answers
307
views
Tiling a Jordan polygon
I saw this problem some years ago, don't remember the source:
Let $P$ be a Jordan polygon (i.e. the only points of the plane belonging to two edges are the polygon vertices) that can be tiled with ...
- 18.6k
15
votes
2
answers
863
views
Three squares in a rectangle
One of my colleagues gave me the following problem about 15 years ago:
Given three squares inside a 1 by 2 rectangle, with no two squares overlapping, prove that the sum of side lengths is at most 2. (...
CommunityBot
- 1
25
votes
1
answer
3k
views
Number of hypercube unfoldings
While writing the code for this answer, I noticed that I not only could calculate the number of unfoldings of the $4$-cube, but also the number of the $n$-cube for more values of $n$. Basically, we ...
- 61
2
votes
1
answer
143
views
Triangles and convex hulls in high dimensions
Given a set $S_n$ of $n$ points $\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_n\in\mathbb{R}^d$, such that every $(d+1)$-tuple in $S_n$ is affinely independent, and let $C(S_n)$ be the convex hull ...
- 151k
2
votes
1
answer
127
views
The density of a tripartite 1-planar graph
1-planar graphs are those can be drawn in the plane so that there is at most one crossing per edge. We know that the maximum number of edges of an $n$-vertex 1-planar graph is at most $4n-8$, and the ...
- 1,190
2
votes
1
answer
106
views
Are zonotopes determined by their edge-graph?
General polytopes are not determined by their edge-graph (up to combinatorial equivalence). But I came accross the statement that zonotopes are determined in this way.
Question: Is this true? And ...
9
votes
2
answers
505
views
Moore graphs and finite projective geometry
In a comment on a blog post from 2009 about the hypothetical Moore graph(s) of degree 57 and girth 5, Gordon Royle offered the following observation (reproduced here in full for the sake of ...
- 9,501
7
votes
1
answer
1k
views
Elementary precise estimate of the covering number of euclidean balls by hypercubes
I am looking for a straightforward way to upper bound the covering number of a $d$-dimensional euclidean ball by $\ell_\infty$-balls of radius $\varepsilon$, which I will call cubes of sidelength $2\...
- 61.9k