# Tagged Questions

**2**

votes

**1**answer

78 views

### Computational complexity of deciding isomorphism of rational polyhedral cones

Let $C,C'$ be rational polyhedral cones in $\mathbb R^n$ both with non-empty interior. Rational means they are generated by vectors with rational entries. One says that $C,C'$ are isomorphic if there ...

**3**

votes

**1**answer

126 views

### Partition All $n$-bit Binaries into $n$ Parts

For what values of $n$, it is possible to partition $\mathbb{Z}_2^n$ into $n$ disjoint parts, say $A_1, ..., A_n$ such that every element in $\mathbb{Z}_2^n$ is at most one-edit away from each part, ...

**8**

votes

**2**answers

360 views

### Finite field Szemeredi-Trotter theorem with unequal number of points and lines

My question concerns the Szemerédi-Trotter theorem in $\mathbb{F}_q^2$. If we have $m$ points and $n$ lines in $\mathbb{F}_q^2$, then by Cauchy-Schwartz the number of point-line incidences is as most ...

**4**

votes

**0**answers

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

**1**

vote

**2**answers

208 views

### Discrete Laplace operator and its eigenvalues

I wonder is there any geometric interpretation of the eigenvalues of the discrete Laplace operator on graphs? Maybe there is a relationship between the eigenvalues and combinatorial properties of ...

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

**12**

votes

**2**answers

399 views

### Sets of evenly distributed points in the Euclidean plane

Is there a set $P \subset \mathbb{R}^2$ of points in the Euclidean plane whose intersection
with every convex subset of $\mathbb{R}^2$ of area $1$ is nonempty but finite?
If the answer is yes, can ...

**0**

votes

**0**answers

29 views

### Bounds on number of linear top-$k$ orderings of lattice point sets

Given a set of $n$ lattice points $A = \{a_i\} \subset {\mathbb Z}^d$ I call a $k$-tuple $(a_{i_1},\ldots,a_{i_k})$ from $A$ a (linear) top-$k$ ordering if there is a vector $c$ such that
$$c\cdot ...

**5**

votes

**2**answers

134 views

### Functionals on oriented matroids

Oriented matroids are abstractions of hyperplane arrangements, or equivalently vector configurations. Let me recall the definition in terms of covectors.
Let $R=\lbrace 0,+,-\rbrace$ with the monoid ...

**11**

votes

**1**answer

487 views

### Tiling the square with rectangles of small diagonals

For a given integer $k\ge3$, tile the unit square with $k$ rectangles so that the longest of the rectangles' diagonals be as short as possible. Call such a tiling optimal. The solutions are obvious in ...

**5**

votes

**1**answer

382 views

### Interesting behaviour of Brion's formula under a degenerate change of variables

This is, probably, a question for those knowledgeable on the subject of Brion's theorem and its applications.
Lately, I've been dealing with situations of the following sort. Suppose we are given a ...

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

**11**

votes

**0**answers

317 views

### Drawings of complete graphs with $Z(n)$ crossings

Hill conjectured that the minimum number of crossings in a drawing of the complete graph $K_n$ in the plane is exactly
$$Z(n) = \frac{1}{4} \bigg\lfloor\frac{n}{2}\bigg\rfloor ...

**8**

votes

**0**answers

102 views

### Diameter of simplicial complex mirrored in property of Stanley-Reisner ring?

Consider a pure finite abstract simplicial complex $\Delta$. Define its diameter as the maximal distance between any two facets, i.e., between any two faces of maximal dimension $d-1$. The distance ...

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

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

**4**

votes

**1**answer

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

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

**17**

votes

**2**answers

964 views

### Erdős-Szekeres for first differences

The classical Erdős-Szekeres theorem says that any sequence of $n^2+1$
real numbers contains a monotonic $(n+1)$-term subsequence. Suppose, however,
that we want to find a subsequence which is not ...

**17**

votes

**3**answers

541 views

### Sperner Lemma Applications

I was always fascinated with this result. Sperner's lemma is a combinatorial result which can prove some pretty strong facts, as Brouwer fixed point theorem. I know at least another application of ...

**3**

votes

**1**answer

411 views

### Tverberg partitions with less than (r-1)(d+1)+1 points

The Tverberg Theorem states the following: Let $x_1,x_2,\dots, x_m$ be points in $R^d$ with $m \ge (r-1)(d+1)+1$. Then there is a partition $S_1,S_2,\dots, S_r$ of $\{1,2,\dots,m\}$ such that $\cap ...

**7**

votes

**1**answer

264 views

### Does the Hirsch conjecture hold for $n < 2d$?

The Hirsch conjecture asserts that the graph (i.e. $1$-skeleton) of a $d$-dimensional convex polytope with $n$ facets has diameter at most $n - d$.
After being open for decades, Francisco Santos has ...

**24**

votes

**2**answers

637 views

### chromatic number of the hyperbolic plane

A notorious problem in combinatorics is the following:
If we color $\mathbb{R}^2$ so that no pair of points at unit distance get the same color, what is the fewest number of colors required?
This ...

**3**

votes

**0**answers

231 views

### Coloring $\mathbb{Z}^k$ and a fixed point theorem

This is potentially another approach to this question. I put it as an update there, but perhaps it would be better to post it separately. If we color $\mathbb{Z}^k$ with the $\ell_\infty$ metric in ...

**9**

votes

**1**answer

876 views

### Numbers of intersection points and lines

Hello,
I don't know if this question has already been posted, I have made a little search with keywords and did not found it, sorry if I missed anything.
Is it possible to characterize the set of ...

**17**

votes

**2**answers

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

**1**

vote

**1**answer

596 views

### Applications of ham sandwich type results. References? A general principle?

Lately there has been a lot of interest on applications of the ham sandwich theorem and related results. There is a bunch of lecture notes and surveys that touch upon the subject. I dont know of any ...

**10**

votes

**3**answers

936 views

### A curious generalization of Helly's theorem

Here is a curious conjectural extension of Helly's theorem.
It may follow (if true) from a useful theorem of the kind asked in this MO question:
Conjecture: Let ${\cal F}=P_1,P_2,\dots,P_m$ be a ...

**8**

votes

**1**answer

694 views

### A Desirable Extension of the Nerve Theorem

Backgroud
The Nerve Theorem (see nLab;) asserts that given a finite collection $\cal K$ of compact sets with the property that all non empty intersections of sets in the family are homotopically ...

**8**

votes

**3**answers

988 views

### Undecidable problems in geometry

Are there any (many) algorithmically undecidable problems in computational (combinatorial/discrete) geometry?
Update: the Wang tiles answer the question with "any". (I have somewhat overlooked to ...

**3**

votes

**1**answer

259 views

### Enumerating Connected Circle Graphs

Hi
A circle graph is defined as the intersection graph of a set of chords of a circle.
I'm interested in any information which might help to enumerate connected circle graphs.
Thanks
Andy

**8**

votes

**3**answers

630 views

### Erdos-Szekeres in high dimensions

All the point sets in this post are in general position. A set of points in $R^d$ is in general position if every $k+1$ points are affinely independent for $k \le d$. If the set contains at least ...

**4**

votes

**1**answer

317 views

### Intersection of boundary facets of a simplicial complex

Suppose you have an equidimensional $n$-dimensional simplicial complex $\Delta \subseteq \mathbb Q^n$; i.e., $\Delta$ is the union of finitely many $n$-simplices that intersect only along proper ...

**13**

votes

**1**answer

524 views

### Which sets of lattice points have rational generating functions?

Let $P$ be a subset of $\mathbb N^d$ (or of some normal pointed affine semigroup), and suppose that $f:=\sum_{p\in P}\ t^p\in\mathbb Z[[t_1,\ldots,t_d]]$ is a rational function. What can be said ...

**6**

votes

**0**answers

203 views

### balls in arrangements of hyperplanes

The following theorem is from Aronov, Naiman, Pach and Sharir's
An invariant property of balls in arrangements of hyperplanes. I would like to state them and then ask if any related problem/theorem ...

**7**

votes

**0**answers

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

**7**

votes

**2**answers

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

**53**

votes

**5**answers

2k views

### Does every polyomino tile R^n for some n?

This is a question posed by Adam Chalcraft. I am posting it here because I think it deserves wider circulation, and because maybe someone already knows the answer.
A polyomino is usually defined to ...

**8**

votes

**2**answers

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

**4**

votes

**2**answers

225 views

### Finding the Boundary Faces of the Zonohedron

A zonotope is a linear combination of m vectors with coefficients in [0,1]: $Z = \{ \sum \lambda_i v_i : 0 \leq \lambda _i \leq 1 \}$. The fancy way is to say it's the Minkowski sum of line segments ...

**2**

votes

**1**answer

487 views

### Gluing Polygons

Consider all polygons whose vertices are lattice points and edges are parallel to the axes such that no more than two edges meet at a vertex. For two polygons A and B, define A+B be to the set of ...

**7**

votes

**3**answers

428 views

### “incidental” intersections of a complete graph in the plane

Given a complete graph of n vertices (no three of which are no collinear) in the plane and straight edges, what is the maximal possible number of "incidental intersections" of edges, i.e., number of ...

**18**

votes

**3**answers

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

**5**

votes

**3**answers

347 views

### Path connected coloured sets on the squared paper

Colour small squares on the standard squared paper in two colors A, B. Name two small squares with common side as "neighbor".
Let every colored set be "path connected": for any two small squares of ...

**15**

votes

**0**answers

1k views

### Covers of $Z^k$

This is a question related to covers of $Z^\infty$. Is it possible to cover $Z^k$, $k>1$, with the $l_1$-metric by a constant (not depending on $k$) number of collections of subsets $U^0,...,U^c$ ...

**11**

votes

**2**answers

707 views

### covers of $Z^\infty$

Is it possible to cover $Z^\infty$ (the infinite direct sum of $Z$'s with the $l_1$-metric) by a finite set of collections of subsets $U^0,...,U^n$ such that each collection $U^i$ consists of ...

**5**

votes

**2**answers

327 views

### Up to projectivities, which configurations of four lines in $\mathbb{P}^3$ can one distinguish?

Background
I am interested in the projective classification of reduced curves of degree four in $\mathbb{P}^3(\mathbb{R})$ (and more generally of degree $n+1$ in $\mathbb{P}^n(\mathbb{R})$). More ...

**10**

votes

**2**answers

1k views

### Discrete Hairy Ball Theorem

This question is inspired by
Math puzzles for dinner
The arrow compatibility conditions in that problem can be considered an attempt to discretize the notion of a continuous vector field.
The ...

**10**

votes

**1**answer

464 views

### Largest pair of homometric Golomb rulers?

A Golomb ruler is a set of $n$ integers that determines $\binom{n}{2}$ distinct differences.
Two sets are homometric if they determine the same (multiset) of differences.
For example,
...

**16**

votes

**3**answers

1k views

### Cutting convex sets

Any bounded convex set of the Euclidean plane can be cut into two convex pieces of equal area and circumference.
Can one cut every bounded convex set of the Euclidean plane into an arbitrary number ...