# Tagged Questions

112 views

### General and translational Birkhoff lattices. Equational classes.

By  lattice  I'll mean  Birkhoff lattice. The two classical equational classes of lattices are modular lattices and distributive lattices. The old problem used to be: Is there an ...
120 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 ...
418 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 ...
323 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 ...
189 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 ...
276 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 ...
224 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 ...
212 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 ...
120 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$, ...
456 views

### Three half circles on the plane may not meet nicely

Let $H$ denote the union of the northen hemisphere of the unit circle $S^{1}$ with the interval $[-1,1]$ on the $x$-axis. That is, $H=\{(x,\sqrt{1-x^{2}}):-1\le x\le 1\}\cup\{(x,0):-1\le x\le 1\}$ ...
476 views

### Cylinders dividing $\mathbb{R}^{3}$

Consider $n$ affine copies of a compact cylinder, say $S^{1}\times [-3,3]$ with top and botom, sitting inside $\mathbb{R}^{3}$. For each $n$ we may ask ourselves how to arrange the $n$ cylinders so ...
329 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 ...
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 ...
115 views

### Graph implemened into the plane with segments as edges and we search for matching with no edges intersecting

There are some points in the plane and some of them are connected with segments between them. We look at this structure as a graph implemented into the plane where the points are the vertices and the ...
895 views

### High Dimensional Analogs of Polygon Spaces

[Edit: I had a mistake in the numerology (took d=6,5 instead d=5,4). Edit: I mistakingly identified my mistake, it is 6,5 but I got the indices shifted by one.] Background: Polygon spaces Given a ...
62 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 ...
760 views

### Placing points on a sphere so that no 3 lie close to the same plane

Motivation I am working with arbitrary parallelopiped tilings given by projection from a higher dimensional space. The collection of tiles, and some properties of the higher dimensional space are ...
647 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 ...
894 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 ?
605 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 ...
458 views

### Maximal disjoint Hyperplanes

Given a set of $n^{r}$ points $X_{r} = \{ x_{1}, \cdots, x_{n^{r}} \}$ occupying a codim $t^{r}$ subspace in $\mathbb{R}^{n^{r}}$. Let $M_{r}$ be the set of $t^{r}$-tuples of these points.. So ...
1k views

### Subdivision of triangles into congruent triangles

Recently some old notes of mine have gotten me to thinking about the problem of subdividing a triangle into $N$ smaller triangles, all congruent to one another. A little thought shows the following ...
350 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 ...
215 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 ...
859 views

### coloring ${\mathbb Z}^k$

This question is related to but seems to be simpler than this one, so perhaps somebody can solve it. Question. Is there $k\ge 1$ and a coloring of vertices of the lattice ${\mathbb Z}^k$ in $k$ ...
750 views

### The straightest possible path embeddable in a path of polygons

I'm studying a problem involving the sets of discrete curves that can be embedded in a non-trivial polygon, from a source to a target point, as shown below. Initially my interest was limited to ...
663 views

### Arrangements of points in the plane

Let $p_1,\ldots,p_n$ be a collection of distinct points in $\mathbb{R}^2$, no three of which lie on a line. For each $p_i$, let $\omega_i(p_1,\ldots,p_n)$ be the following ordered list (well-defined ...
325 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 ...
381 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 ...
313 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 ...
642 views

### Are Penrose tilings universal? Do aperiodic universal tilings exist?

Consider a tiling of the plane using tiles of at least two types (e.g, a Penrose tiling such as that shown at the bottom of this question, which tiles the plane with two types of tiles). List the tile ...
964 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 ...
2k views

### What upper bounds are known for the diameter of the minimum spanning tree of $n$ uniformly random points in $[0,1]^2$?

Let $P$ be a pointset consisting of $n$ uniformly random elements of $[0,1]^2$. It is known that the diameter (greatest number of edges in any shortest path between two points) of the Delaunay ...
817 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 ...
2k 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)?
561 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 ...
186 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 ...
965 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 ...
286 views

### Tetris in 3D with 5 units

Background: There are 7 "bricks" used in the game of Tetris. These are the 7 unique combinations of 4 unit squares in which every square shares at least one edge with another square. ("unique" in this ...
372 views

### Uniqueness of a polygon

Suppose I have two $n$-sided polygons A and B. Is there a non-trivial upper bound on the number of parameters (eg. area, perimeter, etc) of the two polygons, that need to be the same, for A and B to ...
475 views

### How can we count lines in an n-x-n rectangular array?

Is there a formula for the number of lines that contain exactly two points through an n x n rectangular array of points?