# Tagged Questions

**1**

vote

**0**answers

124 views

### Spectrum of Combinatorial Laplacian

The spectrum of the combinatorial laplacian is well understood for a square lattice. What about for other lattices?
In particular:
Let $ f: \mathbb{Z}^2 \rightarrow \mathbb{R} $. The usual ...

**2**

votes

**2**answers

219 views

### Is there a combinatorial analogue of the Kazdan Warner theorem?

First let me state a result of Kazdan and Warner
Let $M$ be a compact orientable two dimensional manifold.
Let $f:M \rightarrow \mathbb{R}$ be a function that has the same
sign as the Euler ...

**25**

votes

**3**answers

1k views

### Can one recover the smooth Gauss Bonnet theorem from the combinatorial Gauss Bonnet theorem as an appropriate limit?

First let me state two known theorems.
Theorem 1 (for smooth manifolds): Let $(M,g)$ be a smooth compact two dimensional Riemannian manifold. Then
$$ \int \frac{K}{2 \pi} dA = \chi (M) $$
where $K$ ...

**23**

votes

**2**answers

816 views

### The kissing number of a square, cube, hypercube?

How many nonoverlapping unit squares can (nonoverlappingly) touch one unit square?
By "nonoverlapping" I mean: not sharing an interior point.
By "touch" I mean: sharing a boundary point.
...

**8**

votes

**2**answers

558 views

### A Problem about partitioning $S^2$

Question: Can the 2-dimensional sphere $S^2$ be partitioned into four nonempty sets such that every circle in $S^2$ passes through just three of these four sets?
Here, "just three" means "exactly ...

**21**

votes

**1**answer

716 views

### Sane bound on number of moves for Maker-Breaker game on $\mathbb R^2$ for $\{0,1,2,3,4\}$

The description below comes from
József Beck. Combinatorial games. Tic-tac-toe theory, Encyclopedia of Mathematics and its Applications, 114. Cambridge University Press, Cambridge, 2008, MR2402857 ...

**2**

votes

**2**answers

252 views

### packing disks tightly in the plane

Given a discrete point set $S$ in ${\bf R}^2$ with a specified base-point $p_0 \in S$, label the remaining points as $p_1, p_2, \dots$ in order of increasing distance from $p_0$ (with ties resolved ...

**2**

votes

**2**answers

227 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 ...

**4**

votes

**1**answer

415 views

### Combinatorial geodesics

[There has been a flaw in my definition - as Sergei and Andreas pointed out. I hope I could fix it.]
I want to understand how the concepts of directions, straight (or shortest) lines, and geodesics ...

**8**

votes

**1**answer

403 views

### Polyhedra that combinatorially shadow a sequence

Let $P$ be a polyhedron in $\mathbb{R}^3$.
Say that $P$ combinatorially shadows a sequence of natural numbers $S$ if
there is a continuous rotation of $P$ such that its orthogonal-projection
shadows ...

**0**

votes

**1**answer

215 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 ...

**9**

votes

**2**answers

344 views

### On well separated point sets in the plane

Let us say that a finite set $A$ in the plane is $1$-separated if:
1) it has an even number of points;
2) no open ball of diameter $1$ contains more than $|A|/2$ points.
For a $1$-separated set $A$ ...

**14**

votes

**1**answer

456 views

### The optimal constant in Vitali covering lemma

Let me restate Vitali covering lemma.
Let $\{B_i\}_{i\in F}$ be a finite collection of balls in the $\mathbb{R}^n$. Then there is $S\subset F$ such that the balls $\{B_i\}_{i\in S}$ are disjoint and
...

**14**

votes

**2**answers

727 views

### Particles chasing one another around a circle

Two particles start out at random positions on a unit-circumference circle.
Each has a random speed (distance per unit time) moving counterclockwise uniformly distributed
within $[0,1]$. How long ...

**1**

vote

**0**answers

169 views

### Lattice-point enumeration question involving linear combinations of matrices

I would like to know some references to learn more about an answer to this question, if there are any references:
Let $A_1, \dots , A_m$ and $B$ be $n\times n$ symmetric matrices. Let $$S = \{(x_1, ...

**9**

votes

**3**answers

384 views

### Mutually tangent ellipsoids in 3 space

I recently heard a claim that for any n, it is possible to arrange n ellipsoids in 3 space such that each pair of ellipsoids is kissing. Is this true, and if so, how?
Edit: By kissing, I mean that I ...

**2**

votes

**0**answers

98 views

### Rational viewing points in a polygon

We refer to the question posed in Seeing the vertices of a polygon with rational angles, but now ask for constructions or for the existence of rational viewing points. We'll call a point $p$ inside ...

**6**

votes

**1**answer

196 views

### Seeing the vertices of a polygon with rational angles

Given any convex polygon in the plane, is it always possible to find a point $p$ in its interior such that when we draw the line segments from $p$ to each of its vertices, the angles formed at $p$ are ...

**13**

votes

**1**answer

341 views

### The sparsest planar net that captures every unit segment

Let $\cal C = \lbrace C_i \rbrace$ be a collection
of rectifiable curves in the plane with the property that
every unit-length segment meets at least one curve
in at least one point.
Call such a ...

**11**

votes

**0**answers

385 views

### Reciprocity (Ehrhart-style) for real polytopes?

Is there some sense in which the well-known Ehrhart reciprocity law for rational, convex, polytopes can be extended to any convex polytope with arbitrary real vertices?
In other words, given any ...

**12**

votes

**1**answer

579 views

### The geometry of crinkled aluminum foil

I wonder if the geometry of crinkled aluminum foil has been studied?
The above is a photo of foil I flattened to reuse.
It might be ...

**4**

votes

**1**answer

264 views

### Best upper bound on rate for q-ary codes

Among the many upper bounds for families of codes in $\mathbb F _2 ^n$, the best known bound is the one by McEliece, Rodemich, Rumsey and Welch which states that the rate $R(\delta)$ corresponding to ...

**1**

vote

**2**answers

137 views

### Disks Packing Variant

Usually disk packing problems require that no two disks of the packing intersect.
Does anybody know if the problem has been studied when disks may intersect but they are not allowed to contain the ...

**37**

votes

**8**answers

3k views

### A sudden smiley? :-)

This is a vague question, and I will no doubt be (properly!) chastised for posing it.
I would like to generate a set $S$ of points in $\mathbb{R}^3$—$|S|$ finite or infinite—which
has the ...

**2**

votes

**2**answers

194 views

### Is there a simple test to determine whether a polytope is integral?

It is known that any rational convex polytope expressed as $\{ x\in\mathbb{R}^d : Ax \ge b \}$, where $A\in\mathbb{Z}^{k\times d}$ and $b\in\mathbb{Z}^k$, can be written as the convex hull of finitely ...

**11**

votes

**2**answers

566 views

### Discrete Morse function from smooth one

Suppose I have a smooth manifold $M$ and a smooth Morse function $f$ on $M$. Is there a standard way to replace $M$ with a cell complex and $f$ with a discrete Morse function such the resulting ...

**0**

votes

**3**answers

277 views

### The symmetry group of $\mathbb Z^d$

Let $d \ge 1$, and consider the integer lattice $\mathbb Z^d$. This is a homogeneous space, in the manner of the Erlangan Programm.
I would like to write $\mathbb Z^d = G / H$, where $G$ is the ...

**9**

votes

**2**answers

892 views

### The Gauss circle problem on a hexagonal lattice

Take an infinite hexagonal lattice (or equivalently, an equilateral triangular lattice), with unit spacing between the closest lattice point pairs, and draw a disc of radius $r$ centered on a lattice ...

**5**

votes

**0**answers

479 views

### Optimal Gear Trains

Suppose you need to slow down a turning motor so that a gear turns at
an angular velocity $\frac{a}{b}$ of that of the motor shaft, where $a$ and
$b$ are natural numbers. For example, this set of ...

**6**

votes

**3**answers

347 views

### Herringbone partitions of regions and surfaces

Let $R \subset \mathbb{R}^2$ be a region of the plane bounded
by a Jordan curve. The boundary $\partial R$ could be a polygon,
or a smooth curve—there are variations depending upon boundary ...

**3**

votes

**1**answer

230 views

### Empty convex polytopes for random point sets

I know of the famous results on the Erdős-Szekeres empty convex polygon problem in the plane
(the Happy-Ending Problem), and I know that there are higher-dimensional extensions.
A great source ...

**4**

votes

**2**answers

308 views

### Realization spaces for regular convex polytopes

Q1.
Are there convex polytopes combinatorially equivalent to each of the regular polytopes
that are realized with integer vertex coordinates?
...

**11**

votes

**1**answer

336 views

### Detecting a hidden convex body with line probes

Imagine that, somewhere inside an origin-centered, unit-radius sphere
$S$ in $\mathbb{R}^3$,
sits a convex body $K$ of volume vol$(K)=\alpha (\frac{4}{3} \pi)$,
with $\alpha < 1$ the fraction of ...

**7**

votes

**1**answer

2k views

### Get Largest Inscribed Rectangle of a Concave Polygon

I'm looking for an algorithm to find a set of largest inscribed rectangles of a concave polygon where each rectangle must be collinear with one of the edges of the polygon.
In other words, I want to ...

**8**

votes

**2**answers

2k views

### Covering a Polygon with Rectangles

I am tyring to cover a simple concave polygon with a minimum rectangles. My rectangles can be any length, but they have maximum widths, and the polygon will never have an acute angle.
I thought about ...

**1**

vote

**2**answers

197 views

### Triangular grid with 4 edges per vertex

I am trying to create a triangular grid/mesh for a rectangular domain in $\mathbb{R}^2$ with the property that each vertex is shared by (at most) four edges. Is this possible to accomplish?

**5**

votes

**0**answers

318 views

### $n$ lines in a general position and the number of empty triangles

Question. Consider $n \geq 5$ lines in a general position (i.e. no two lines are parallel and no triple intersections are allowed) in $\mathbb{R}^2$. Let $T(n)$ denote the maximal number of empty ...

**3**

votes

**2**answers

361 views

### What collections of convex sets result in non-trivial uses of Helly's theorem?

Consider Helly Theorem, taken from notes by Igor Pak:
Let $X_1, \dots, X_n \in {\mathbb{R}}^2$ be convex regions in the plane such that any triple interesects $X_i \cap X_j \cap X_k \neq 0$. Then ...

**9**

votes

**1**answer

514 views

### Minimizing the excursion of a sum of unit vectors

I have $n$ unit-length vectors $v_i$ in $\mathbb{R}^3$, whose
sum is zero:
$$ v_1 + v_2 + \cdots + v_n = 0 \; .$$
Now I form the closed polygon $P$ in space by placing them head to tail.
So the ...

**8**

votes

**4**answers

576 views

### Knot diagrams, sets of moves and equivalence relations

Short version: Does anyone study equivalence classes generated by a given set of "moves" (in the sense of, but not limited to, Reidemeister moves) on the set of knot diagrams?
Yes, I understand that ...

**9**

votes

**5**answers

513 views

### Minimal blocking objects with shadows like a cube

This is a more geometric version of the previous question,
"Lattice-cube minimal blocking sets". I will first specialize to $\mathbb{R}^3$, $d=3$.
View an $n \times n \times n$ cube $C_3(n)$ as ...

**5**

votes

**2**answers

265 views

### Lattice-cube minimal blocking sets

Let $C_d(n)$ be the lattice cube consisting of the $n^d$ points with
each of its $d$ coorindates in $\lbrace 1,2,\ldots,n \rbrace$.
Define a blocking set for a lattice cube to be a set of points
in ...

**4**

votes

**0**answers

183 views

### Mean number of $n$-simplices per $(n-2)$-simplex in a triangulated $n$-manifold

Work by Tamura (extending results by Luo and Stong) shows the following.
Theorem: For any closed 3-manifold $M$ and any rational number $4.5 < r < 6$ there is a triangulation $T$ of $M$ for ...

**19**

votes

**1**answer

685 views

### Monomer-Dimer tatami tilings need better relationships with other math. Summary of results.

A monomer-dimer tiling of a rectangular grid with $r$ rows and $c$ columns satisfies the \emph{tatami} condition if no four tiles meet at any point. (or you can think of it as the removal of a ...

**0**

votes

**1**answer

81 views

### When do there exist locally regular embeddings of regular graphs?

I don't know how one can tackle the following kind of question, so any hint is welcome. I formulate a precise question in order to fix ideas, but it is to be considered as an example out of a more ...

**12**

votes

**6**answers

901 views

### Optimal pebble-packing shape

Suppose you throw many ($n$) congruent convex bodies (in $\mathbb{R}^3$) of unit volume (or of unit area in $\mathbb{R}^2$) into a large container, and shake it until little else changes.
Q. ...

**35**

votes

**6**answers

1k views

### Tetris-like falling sticky disks

Suppose unit-radius disks fall vertically from $y=+\infty$,
one by one, and create a random jumble of disks above the $x$-axis.
When a falling disk hits another, it stops and sticks there.
Otherwise, ...

**2**

votes

**2**answers

517 views

### Midpoint lattice polygons

Midpoint polygons (a.k.a Kasner polygons) have been studied, and their behavior is well understood.
I am considering a variant, which I call midpoint lattice polygons.
Start with a sequence of ...

**2**

votes

**1**answer

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 ...

**4**

votes

**2**answers

188 views

### Generators of a 2D lattice

Dear MO_World,
I'm hoping someone can point me towards a reference for something. I have an invertible $2\times 2$ matrix, $A$, with real entries such that for both of the rows, the entries are ...