# Tagged Questions

**4**

votes

**5**answers

389 views

### Lattice points in dilated polytopes and sumsets

Let $P$ be an integral polytope, that is, the convex hull of some points in $\mathbb{N}^d$.
Let $p_1,\dots,p_m$ be all lattice points in $P$.
Question: What is the condition on $P$ that guarantees ...

**1**

vote

**0**answers

64 views

### Separating unit disks by circles

This is inspired by the recent question about separating unit disks by lines, which I will refer to as the "line case". Replacing "line" by "circle" adds one degree of freedom, and I'm wondering if ...

**7**

votes

**1**answer

215 views

### Separating unit disks by lines

Given $n\ge 2$. For a real $d>2$, consider a constellation $C$ of $2n$ disks of radius $1$ in the plane such that $h(C)$, the minimal distance between any two of their centers, is equal to $d$. Let ...

**3**

votes

**0**answers

198 views

### How many combinations does Android pattern have? [closed]

Rules-
1) At-least 4 and at-max 9 dots must be connected.
2) There can be no jumps
3) Once a dot is crossed, you can jump over it.

**6**

votes

**1**answer

95 views

### How “accidental” are equalities between parts of Ehrhart quasi-polynomials? When do they persist to Euler-Maclaurin?

Background
What I think of Ehrhart theory (http://en.wikipedia.org/wiki/Ehrhart_polynomial) asserts that if we take a lattice polytope $P$, and count the number of lattice points in the $t$th ...

**4**

votes

**0**answers

144 views

### Unique Domino Tiling

Question: how does one enumerate all star-convex $2n$-vertex sublattices of the plane that have the unique domino-tiling property?
Definitions:
A subset S of the xy-plane is star-convex if there is ...

**3**

votes

**1**answer

265 views

### Number of 3-tuple partitions of a multiple of three which follow the triangle inequality

Given n=3t, t$\in \mathbb N$; let $\mathbb L_3$ be set of all distinct integer partitions of n having 3 parts; say $\lambda_1,\lambda_2,\lambda_3$ .
If I chose any one partition randomly from ...

**1**

vote

**0**answers

74 views

### Group actions on polytopes in indefinite integer lattices

Is anything at all known about polytopes in indefinite integer lattices? I'm interested in lattice automorphisms which preserve certain polytopes of "high regularity" (e.g. cones). As a first step, ...

**2**

votes

**1**answer

79 views

### Estimates on the number of vertices of reflexive polytopes

Suppose $M \cong \mathbb{Z}^n$ is a rank $n$ lattice, with dual lattice $N$. Suppose $\Delta$ is a full dimensional lattice polytope (i.e. convex hull of finite lattice points) in $M$. Then $\Delta$ ...

**1**

vote

**0**answers

217 views

### A problem in Galois Geometry

Given a prime $p$, out of $N$ vectors of length $p^k$ over $\Bbb F_2$ of Hamming weight $w^{k}$ that are chosen, how many vectors can there be with pairwise Hamming distance at least $2w^{k}$ given ...

**3**

votes

**2**answers

227 views

### Problems similar to Borsuk’s Theorem in the plane

Consider a 2-dimensional Borsuk's theorem:
Every bounded set $S$ in the plane can be partitioned into three parts with diameter smaller than the diameter of $S$.
I wonder if there are any ...

**2**

votes

**2**answers

137 views

### Proving non-convexity of a set of lattice points

I have a set of lattice points S in R^n (listed in memory in a computer for n=8 say). I want to computationally certify that they do not form the lattice points of a convex polytope P in R^n. (Ex. ...

**5**

votes

**1**answer

435 views

### Difference Sets

Suppose
$$
P \subseteq \{1,2,\dots,N\},\quad |P| = K
$$
We calculate the differences as: $$d=p_i-p_j\mod N,\quad i\ne j$$
Now let $a_d$ denote the number of occurrence of $d$ (for $d = 1, 2, \dots , N ...

**3**

votes

**0**answers

100 views

### What are the Voronoi cones in 4 variables?

Question: What are the top dimensional cones of the 2nd Voronoi decomposition of the space of positive definite forms in $4$ variables?
The 2nd Voronoi decomposition of the cone of positive definite ...

**9**

votes

**1**answer

251 views

### Maximum number of Vertices of Hypercube covered by Ball of radius R

Let $R>0$ be given and let $H^n$ be the unit hypercube in $\mathbb{R}^n$. The problem I am facing is to find the maximum number of vertices of $H^n$ which can be covered by a closed $n$-dimensional ...

**2**

votes

**1**answer

117 views

### Realizability of extensions of a free oriented matroid by an independent set

Question:
I am searching for a non-realizable matroid with few dependencies relative to the number of points. Precisely, I would like to find a non-realizable (over $\mathbb{R}$) oriented matroid $M$ ...

**4**

votes

**3**answers

217 views

### Perimeter/Neighborhood of a graph on grid

Hello,
I have a $\sqrt{n}\times\sqrt{n}$ lattice graph $G=(V,E)$ i.e. vertices on said 2-dim integer lattice, and two vertices have an edge if their $L_1$ distance is one.
Now I want to claim ...

**11**

votes

**2**answers

696 views

### Access to a preprint by D. N. Verma

Some work I am doing is connected with a sequence 1, 3, 40, 1225, 67956, $\dots$ which agrees with http://oeis.org/A012250 for all eight terms. The only useful information in OEIS on this sequence is ...

**8**

votes

**2**answers

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

**20**

votes

**1**answer

603 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

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

**0**

votes

**1**answer

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

**9**

votes

**2**answers

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

**1**

vote

**0**answers

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

**5**

votes

**0**answers

297 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

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

**4**

votes

**0**answers

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

**15**

votes

**0**answers

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

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

**12**

votes

**1**answer

451 views

### Partitioning the vertices of an n-cube with random hyperplane cuts

An evolutionary biologist asked me a question which boils down, at least in part, to what seems to me an interesting question of combinatorial/probabilistic geometry.
It is an old chestnut of a ...

**1**

vote

**1**answer

107 views

### Generalizing the internal angle of a graph in $\mathbb{E}^2$ to $\mathbb{S}^2$

I am currently working on research involving packing problems and am finding myself needing the tools from Combinatorial Geometry (in particular, I've been reading Pach and Agarwal's book on the ...

**45**

votes

**2**answers

2k views

### vector balancing problem

I believe the solution posted to the arXiv on June 17 by Marcus, Spielman, and Srivastava is correct.
This problem may be hard, so I don't expect an off-the-cuff solution. But can anyone suggest ...

**0**

votes

**1**answer

334 views

### On the number of lines of given points

Hi all, I have a question Concerning Beck's theorem. I have read it from http://en.wikipedia.org/wiki/Beck%27s_theorem and I have two questions :
I suppose Beck's theorem doesn't hold when instead ...

**4**

votes

**2**answers

415 views

### On the joints problem in finite fields

The original version of the so-called "joints problem" consists of the following:
Let $L$ be a set of lines in $\mathbb{R}^{3}$. Determine the maximum number of "joints" determined by these lines, ...

**1**

vote

**1**answer

371 views

### Combinatorial optimization and graph coloring

I am considering the following problem:
(i) Fix $n$ and color the edges of $K_n$ red and blue arbitrarily.
(ii) Let $M$ be the set of monochromatic triangles in $K_n$ and define $g:M\rightarrow ...

**0**

votes

**0**answers

97 views

### Question regarding contiguous forms

I read about contiguous forms in Achill Scürmann's thesis on positive quadratic forms. I am wondering about one aspect of the Voronoi algorithm presented in there, that enumerates all arithmetically ...

**1**

vote

**0**answers

136 views

### Traversing perfect quadratic forms

I am wondering whether there is an efficient algorithm to traverse all the $N\times N$ perfect quadratic forms $Q$ inside the polyhedron $e_j^T Q e_j \geq 1$, $j = 1\ldots m$, where $e_j$ are some ...

**4**

votes

**0**answers

137 views

### Slices of Simplices that are Simplices, Reference?

I am trying to find a reference for the following fact. It is elementary and not hard to prove, but I haven't been able to find the question treated anywhere.
Let $A$ be an $l\times n$ matrix with ...

**1**

vote

**3**answers

275 views

### Enumerating Perfect Lattices

I have a question regarding enumeration of perfect lattices/quadratic forms. In the thesis of Achill Schürmann http://fma2.math.uni-magdeburg.de/~achill/public/habil.pdf there is an algorithm called ...

**4**

votes

**1**answer

506 views

### Why is the Street nerve of the Gray tensor product $[1]\otimes [1]$ isomorphic to $[1]\times [1]$

Recall that given two strict ω-categories $A$ and $B$, their lax Gray tensor product $A\otimes B$ is sent to the Verity-Gray tensor product of their associated complicial sets ...

**19**

votes

**8**answers

1k views

### Higher-dimensional Catalan numbers?

One could imagine defining various notions of higher-dimensional Catalan numbers,
by generalizing objects they count.
For example, because the Catalan numbers count the triangulations of convex ...

**1**

vote

**1**answer

462 views

### On lattice points “far inside” convex lattice polygons

Let $\mathcal{P}$ be a convex lattice polygon with $n$ vertices and let $\mathcal{L}$ be the set of all lattice points inside $\mathcal{P}$. For every $n \geq 5$, does there exist a point in ...

**9**

votes

**3**answers

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

**7**

votes

**3**answers

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

**9**

votes

**3**answers

688 views

### Polytopes with few vertices.

Suppose I have a convex polytope in $\mathbb{R}^d$ which I know has few vertices (in the case which prompted this question, I seem to have a polytope in $\mathbb{R}^9$ which has sixteen vertices). Is ...

**6**

votes

**1**answer

235 views

### Simplices in convex polytopes

This question is a direct generalization of:
Counting the (additive) decompositions of a quadratic, symmetric, empty-diagonal and constant-line matrix into permutation matrices
Given a convex ...

**4**

votes

**0**answers

402 views

### Intersection of pencils in $\mathcal{R}^2$

Consider $9n$ pencils through non-collinear points $p_1, \ldots , p_{9n}$ in $R^2$ each consisting of at most $n$ concurrent lines. Define the intersection $S$ of these pencils to be the set of points ...

**6**

votes

**2**answers

499 views

### Maximal number of edges and triangular cells for n points in a triangular lattice

Consider a subset of $n$ points in an equilateral triangular lattice. Draw all the edges between nearest-neighbor points.
What is the maximum, over all such subsets, of the number of edges? This ...

**10**

votes

**2**answers

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

**0**

votes

**1**answer

249 views

### [Matrices over Z] - An algorithm for calculating the diagonal with elementary operations

Dear mathoverflow,
Let
$
\left(
\begin{array}{cc}
a & b \newline
c & d
\end{array}
\right)
$
be a matrix with $a, b, c, d \in \mathbb{Z}$, $\gcd(a,b,c,d) = 1$ and $ad - bc = \pm N$, with $N ...