Skip to main content

All Questions

Filter by
Sorted by
Tagged with
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$ ...
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 ...
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 ...
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 \...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 [......
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 ...
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 ...
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 ...
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 ...
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-...
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 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 $...
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\ $ ...
3 votes
0 answers
234 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 ...
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 ...
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 ...
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 $...
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$....
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 ...
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 ...
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 ...
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}$? ...
1 vote
1 answer
379 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 ...
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 ...
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 ...
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 ...
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 $...
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 ...
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 ...
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 ...
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 ...
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-...
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 ...
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 ...
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 ...
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 ...
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. (...
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 ...
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 ...
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 ...
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 ...
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\...