Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Finite or discrete collections of geometric objects. Packings, tilings, polyhedra, polytopes, intersection, arrangements, rigidity.

1
vote
0answers
49 views

On Topological Tverberg Theorem

Let $r$ be a prime power. The Topological Tverberg Theorem says that any continuous map from a $(r-1)(d+1)$-simplex to $\mathbb{R}^d$ identifies points from $r$ disjoint faces. It is not hard to see ...
9
votes
0answers
235 views

Why does Loday call the permutohedra “zylchgons”?

Today I was reading Jean-Louis Loday's classic paper, "Realization of the Stasheff polytope", in which he produces a simple and very pretty realization of the associahedra as convex polytopes. He ...
4
votes
3answers
174 views

Lattice points in a square pairwise-separated by integer distances

Let $S_n$ be an $n \times n$ square of lattice points in $\mathbb{Z}^2$. Q1. What is the largest subset $A(n)$ of lattice points in $S_n$ that have the property that every pair of points in $A(n)$...
7
votes
0answers
24 views

Inefficient covering by translates

While trying to answer this question, I arrived at another question: How many translates of $\{0,1\}^n$ does it take to cover $\mathbb F_3^n$? The broader context is: consider a set $S$ and a ...
2
votes
0answers
22 views

condition on rational polyhedral cone to guarantee dual cone is homogeneous

Let $\sigma\subseteq \Bbb R^d$ be a full-dimensional rational polyhedral cone which is strongly convex (i.e. $\sigma\cap-\sigma=0$). Definition. The cone $\sigma$ is homogeneous if there are ...
5
votes
0answers
67 views

Random walks in arrangements of lines in the plane

Let $\cal{A}_n$ be a simple arrangement of $n$ lines in $\mathbb{R}^2$. (Simple: each pair of lines meet in a distinct point, i.e., no three lines pass through the same point.) Start a random walk at ...
5
votes
0answers
139 views

Can we represent partitions by mutually parallel lines in the plane?

Lately I have become interested in the following idea: Suppose $n$ is a positive integer and $[n]=\{1,2,3,...,n\}$. Suppose we have 3 distinct partitions $b$, $g$, and $r$ of $[n]$. Assume that the ...
13
votes
1answer
261 views

Can the graph of a symmetric polytope have more symmetries than the polytope itself?

I consider convex polytopes $P\subseteq\Bbb R^d$ (convex hull of finitely many points) which are arc-transitive, i.e. where the automorphism group acts transitively on the 1-flags (incident vertex-...
19
votes
2answers
928 views

Is it possible that both a graph and its complement have small connectivity?

Let $G=(V,E)$ be a simple graph with $n$ vertices. The isoperimetric constant of $G$ is defined as $$ i(G) := \min_{A \subset V,|A| \leq \frac n2} \frac{|\partial A|}{|A|} $$ where $\partial A$ is ...
1
vote
0answers
41 views

Upper bounds on $\epsilon$-covers of arbitrary compact manifolds

Let $M \subset \mathbb{R}^d$ be a compact $k$-dimensional manifold embedded in $\mathbb{R}^d$. Let $\mathcal{N}(\epsilon)$ denote the size of the minimum $\epsilon$-cover $P$ of $M$, that is for every ...
8
votes
3answers
206 views

monochromatic subset

Suppose we have $n^2$ red points and $n(n-1)$ blue points in the plane in general position. Is it possible to find a subset $S$ of red points such that the convex hull of $S$ does not contain any blue ...
2
votes
1answer
75 views

Combinatorial problem about binary arrays with certain mutual distinctions

If there are m binary arrays (with 0 and 1) of length n, and between any two of these m arrays, there are k and only k same numbers (with the same site index in two different arrays). For example, if ...
2
votes
0answers
53 views

8-partition of a planar convex body by 4 concurrent lines

It is known1 that any convex body $K$ in the plane can be partitioned into $6$ equal-area pieces by $3$ concurrent lines which meet at a point in $K$. Call this a $6$-partition. This result cannot be ...
1
vote
1answer
145 views

A possible characterization of the cube?

Let $P$ be the $1$-skeleton of a convex polyhedron fixed in $\mathbb{R}^3$, and $|P|$ the sum of the Euclidean lengths of the edges of $P$. Let $P_1, P_2, P_3$ be the perpendicular projections of $P$ ...
3
votes
0answers
81 views

Generating a Penrose tessellation around a given tile

Given a starting Penrose tile, I need to build a "spiraling" tessellation around it. The following picture illustrates the request: In this example, the starting tile is a "thin rhombus" (the pink ...
3
votes
2answers
209 views

Minimum weight triangulation of lattice points in a circle

Let $r$ be a natural number, and consider the $\mathbb{Z}^2$ lattice points $S$ inside or on the circle $C$ of radius $r$ centered on the origin. Let $P$ be the convex hull of $S$; so $P$ is inscribed ...
0
votes
0answers
24 views

Integer Distances in Pointsets Generated from Simplices with Integer Sidelengths

Let $\mathbb{S}_\mathbb{N}^n$ denote the set of all $n$-simplices in $n$-dimensional euclidean space $E^n$. Call an $n$-simplex aligned, if the set $C$ of its corners satisfies $\exists c_k=\left(x^...
1
vote
0answers
43 views

Can projecting a simplex onto orthogonal subspaces exposes the same vertices and edges?

Given the regular $n$-dimensional simplex $S\subset\Bbb R^n$ with $n\ge 4$, as well as two orthogonal subspaces $V,W\subset\Bbb R^n$ of dimension $\ge2$ (not necessarily of same dimension, not ...
5
votes
1answer
187 views

Can two non-equivalent polytopes of same dimension have the same graph?

By a polytope I mean the convex hull of finitely many points. The graph of a polytope is the graph isomorphic to its 1-skeleton. By equivalence of polytopes I mean combinatorial equivalence, i.e. ...
11
votes
0answers
239 views

Simple disproof of Danzer — Grünbaum conjecture

I asked this question on the MSE, but I did not get an answer. I hope that one of the experienced participants will check the correctness of the proof or the truth of the statement (and, perhaps, will ...
3
votes
0answers
61 views

Reconstructing plane graphs from degree- and face-sequences

Let $G$ be a plane $3$-connected graph; so it partitions the plane into regions bounded by faces. Let $\mathrm{deg}_v$ be the sequence of vertex degrees of $G$, and $\mathrm{deg}_f$ be the sequence of ...
5
votes
2answers
209 views

Is every polytope combinatorially equivalent to the intersection of a simplex and a linear subspace?

I wonder whether such a result is known, and if so, whether the proof is trivial. By polytope I mean the convex hull of finitely many points in $\Bbb R^n$. Assume the simplex to be symmetric and ...
1
vote
0answers
55 views

Can sufficiently symmetric polytopes be uniquely reconstructed from their 1-skeleton?

General convex polytopes can not be uniquely reconstructed from their 1-skeleton1, as explained here. Not even the dimension is known from the skeleton, as e.g. the complete graph $K_n,n\ge 5$ is the ...
0
votes
0answers
29 views

How many points are still contained in a common (hyper-)ellipsoid?

It is known that $${d+2\choose 2}-1$$ points uniquely determine a quadric in $\Bbb R^d$. However, I want my points not on an arbitrary quadric, but on a centered hyperellipsoid in $\Bbb R^d$, or ...
5
votes
0answers
113 views

Polychromatic number of plane

Let $\chi$ be the least size of a partition of plane into pieces each of which omits unit distance. Let $\chi_p$ be the least size of a partition of plane into pieces each of which omits some distance....
2
votes
1answer
180 views

Name and Algorithms for a Sparsest Circle Packing

The ordinary circle packing problem in the variant with equal radii asks for the largest radius $r_{max}$ that allows placing $n$ non-overlapping circles with radius $r_{max}$ e.g. in the unit square, ...
5
votes
0answers
126 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 $...
7
votes
2answers
224 views

Visual proof of convergence for Steiner's symmetrization

I want to find a visual proof of the following fact: For any convex figure in the plane there is a sequence of Steiner's symmetrizations that makes it arbitrary close to a circular disc. All ...
6
votes
0answers
101 views

Tiling with incommensurate triangles

Say that two triangles are incommensurate if they do not share an edge length or a vertex angle, and their areas differ. Suppose you'd like to tile the plane with pairwise incommensurate triangles. I ...
9
votes
2answers
238 views

Counting Hamiltonian cycles in $n \times n$ square grid

I wonder if anyone has counted these curves, either exactly or asymptotically? Let $S_n$ be an $n \times n$ subset of $\mathbb{Z}^2$ consisting of $n^2$ lattice points: a lattice square. Define a ...
3
votes
0answers
182 views

Shapes defined by points

Can shapes determined by number of points? From an amazing theorem in plane curves geometry we know that vertices of triangles similar to arbitrary triangle $T$ is dense on every closed jordan curve ...
4
votes
2answers
127 views

Counting points and lines in a plane

Let $P_1$ be a set of 4 points in the Euclidean plane. Formally, $P_1$ determines a set $L_1$ of 6 lines, which then determine only 3 points not already in $P_1.$ Let $P_2$ be the set of 7 points ...
1
vote
3answers
204 views

Repeatedly halve and twist a planar shape: Limiting shape?

Consider the following iterative process. Start with a planar region $R=R_0$ of $\mathbb{R}^2$. I am thinking of $R$ as connected, but it may become disconnected. In the example below, $R$ starts as ...
15
votes
1answer
248 views

Chromatic numbers of infinite abelian Cayley graphs

The recent striking progress on the chromatic number of the plane by de Grey arises from the interesting fact that certain Cayley graphs have large chromatic number; namely, the graph whose vertices ...
5
votes
2answers
168 views

The number of co-circular four tuples

Let $A,B ⊂ \mathbb{R}$ such that $|A| = |B| = n$. What is the best-known upper bound on the number of four-tuples in $A \times B$ where the four points are co-circular, they lie on the same circle?
1
vote
1answer
78 views

Coloring lines in plane

We assume that all the lines in the plane are each colored with one of two colors: red or blue. Given angle $\alpha.$ My question 1. Is there possible to get two lines with the same color and angle ...
7
votes
0answers
85 views

Counting symmetric convex bodies with no nonzero lattice point in the interior

In order to estimate the size of the torsion in the algebraic $K$-groups of $\mathbb Q$ one needs to understand the homology of $\mathrm{GL}_n(\mathbb Z)$, or alternatively, the homology of the space ...
0
votes
1answer
99 views

Positioning a member of an interval partition

Let $\ 0<\Lambda_1\le\ldots\le\Lambda_n\ $ be a finite non-decreasing sequence of positive reals, of length $\ n>0.\ $ Let $$ D:=\sum_{k=1}^n \Lambda_k $$ The question is about the conditions ...
10
votes
0answers
103 views

A combinatorial proof of the Harrow--Kolla--Schulman theorem

Let $Q^n := \{0,1\}^n$ be the Hamming cube with the Hamming metric. (Recall that the Hamming is defined by the distance $d(x,y) := \# \{ i : x_i \neq y_i \}$. For integers $0 \leq k \leq n$, define a ...
0
votes
0answers
30 views

Realisation of a Polytope as a convex set [duplicate]

Suppose I have ALL the combinatorial data of an abstract Polytope: a list of all facets and incidence relations. Is there a way to produce linear functions, in a suitable $R^d$, so that the region ...
37
votes
1answer
842 views

Four circles on the sphere

Consider configurations consisting of 4 distinct circles on the sphere. Two configurations are equivalent if they can be mapped onto each other by a homeomorphism of the sphere. How to enumerate/...
6
votes
2answers
158 views

Sliding through a curvature-bounded tube: Maximum volume?

My 1st question has a straightforward answer but I'd appreciate hints on a proof. My 2nd question is open from my point of view. Q1. Is it the case that the maximum convex volume body inside a ...
3
votes
1answer
191 views

Density of a somewhat random set

The density of a set $X\subseteq\omega$ refers to: $\limsup\limits_{n\rightarrow\infty}\dfrac{C\cap n}{n}$. Given a set of positive integers $F= \{m_0<\cdots<m_{k-1}\}$, let $C\subseteq \omega$...
22
votes
1answer
411 views

Tying knots via gravity-assisted spaceship trajectories

Q. Can every knot be realized as the trajectory of a spaceship weaving among a finite number of fixed planets, subject to gravity alone?           To make this more ...
3
votes
0answers
668 views

Puzzle in 3D grid with black and white boxes, related to shelling

Consider a $n$ by $n$ by $n$ grid represented by the set of $3$-uples $S=\{1,2,\dots, n\}^3$. A line (resp. slice) of $S$ is a subset of cardinal $n$ (resp. $n^2$) where two components (resp. one ...
4
votes
0answers
49 views

Separating stars and large intersections of cycles

Let $\Gamma$ be a finite simplicial graph. For every $k \geq 0$, let $C_k(\Gamma)$ denote the graph whose vertices are the induced cycles of $\Gamma$ and whose edges link two cycles if their ...
1
vote
1answer
88 views

Number of distinct points in an n-dimensional tetrahedron

Consider an n-dimensional tetrahedron with $n+1$ vertices $\langle v_0, v_1, \dots,v_n\rangle$. $v_0$ is the origin while $v_i$ lies on $e_i$ (the $i^{th}$ coordinate axis) at a distance $D$ from the ...
7
votes
2answers
139 views

How different can the constituents of an Ehrhart quasi-polynomial be?

Consider a $d$-dimensional convex rational polytope $P\subset\mathbb{Q}^d\subset\mathbb{R}^d$. Then, it's a standard fact that in general the function counting the number of lattice points inside the ...
3
votes
0answers
86 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 ...
5
votes
0answers
199 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 ...