# Tagged Questions

**5**

votes

**1**answer

171 views

### Small remarkable matroids

Working on phased matroids (a generalization of oriented matroid to the complex case) I've found an interesting formula for computing the inner Tutte group (and, hence, all the Tutte groups) ...

**2**

votes

**0**answers

38 views

### Looking for N-dimensional spheres in the configuration space of the colorful Tverberg problem

Here we use standard notation for Tverberg's theorem: Dimension $d$, number of partition blocks $r$, and $N=(r-1)(d+1)$.
The configuration space of Tverberg's theorem is the simplicial complex ...

**1**

vote

**1**answer

149 views

### Positroids and Totally Nonnegative Complex Grassmanian

Recently I begin working on matroids, in particular to a generalization of oriented matroids to the complex case.
I found on arxiv the following interesting articles:
1)Alexander Postnikov: Total ...

**5**

votes

**1**answer

285 views

### A result from Peter McMullen's thesis

The classical definition of regular polytopes is recursive. It says that a polytope is regular if its facets and vertex figures (both smaller-dimensional polytopes) are regular.
The modern definition ...

**3**

votes

**2**answers

121 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

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

**9**

votes

**2**answers

429 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

209 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

227 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

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

**5**

votes

**2**answers

144 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

500 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

400 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

265 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

337 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

111 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

214 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

150 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

194 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

338 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

1k 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

645 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

427 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

265 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

681 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

234 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

947 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

783 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

618 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

949 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

728 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

1k 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

267 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

653 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

330 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

528 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

208 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

223 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

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

**55**

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

656 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

226 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

492 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

436 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

349 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

710 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

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