The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
1answer
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
2answers
183 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 ...
10
votes
3answers
619 views

Combinatorial analogues of curvature

There appear to be many "combinatorial" definitions of curvature as applied to finite simplicial (or regular CW) complexes. For instance, we have the ideas of Cheeger, Muller and Schrader, of Forman ...
13
votes
1answer
486 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 ...
3
votes
1answer
258 views

Grading a non-graded poset as squeezed as possible

Here is a curiosity question (motivated by the recent revamp of ranked-poset routines in Sage). Let $P$ be a finite poset. We look for a family $\left(a_p\right)_{p\in P}$ of real numbers summing up ...
2
votes
0answers
129 views

A relation on triplets of points in the plane

This question is a follow up of my previous one (Planar sets closed under intersection of circles, Planar sets closed under intersection of circles) and is motivated by G. Zaimi's answer ...
1
vote
1answer
108 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 ...
4
votes
1answer
287 views

Planar sets closed under intersection of circles

Let $P$ be the plane with a point at infinity. By plane, I mean the Euclidian plane, and therefore it has circles. A line is also a circle, though its center is at infinity. If $A\subset P$ has ...
45
votes
2answers
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 ...
3
votes
1answer
316 views

from affine matroid to measures

Let $S$ be an arbitrary finite spanning subset of $\mathbb{R}^d$ of cardinality $N$. Let $W(S)$ be the formal $\mathbb{R}$-vector space generated by all $d$-dimensional simplices (i.e. bases of the ...
0
votes
1answer
339 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 ...
9
votes
2answers
295 views

The area of the intersection of convex sets with prescribed pairwise intersections

Consider two numbers $a>b>0$. Let $A_1,A_2,A_3$ be three convex sets in ${\mathbb R}^2$ such that $\mu(A_i)=a$, $\mu(A_i\cap A_j)=b$ ($\mu$ is the usual measure on ${\mathbb R}^2$). What is the ...
15
votes
3answers
989 views

Is Euler characteristic of a simplicial complex upper bounded by a polynomial in the number of its facets ?

What is the best upper bound known on the (absolute value of) the Euler characteristic of a simplicial complex in terms of the number of its facets ? In particular, I am interested in proving or ...
4
votes
2answers
478 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, ...
26
votes
2answers
615 views

Careless packing

The sequence $\frac{1}{2}, \frac{1}{2\cdot 2}, \frac{1}{3\cdot 4}, \frac{1}{4\cdot 6}, \frac{1}{5\cdot 8}, \frac{1}{6\cdot 10},\ldots$ has a curious property, as follows: a) the series with these ...
2
votes
0answers
235 views

Erdős-Szekeres empty pseudoconvex $k$-gons

I am wondering if the Erdős-Szekeres empty convex $k$-gon question has a different answer if convexity is replaced by a pseudoline-version of convexity. The empty convex $k$-gon question is a variant ...
26
votes
2answers
871 views

Bodies of constant width?

In two-dimensional case one can generalize figures of constant width as figures which can rotate in a covex polygon. Here is one example which can be used to drill triangular holes: I would like to ...
6
votes
2answers
213 views

convex polytopes with many faces and edges but few cells and vertices

For a convex polytope $P$ in $\mathbb R^4$, denote by $N_0,N_1,N_2,N_3$ respectively the number of vertices, edges, faces, cells. By Euler's formula, we know $N_0+N_2=N_1+N_3$, which means there is a ...
7
votes
1answer
204 views

Integer points in dilations of a disk of volume one

The following question is related to When are Ehrhart polynomials polynomials?. For a positive integer $n$, let $i(D,n)$ be the number of integer points in the disk $x^2+y^2\leq n^2/\pi$, so $i(D,n) ...
13
votes
2answers
2k views

How many vertices/edges/faces at most for a convex polyhedron that tiles space?

I wonder if this problem has already been examined before: Consider a convex polyhedron that tiles $\mathbb R^3$. What is the maximum of vertices/edges/faces that such a polyhedron can have? ...
1
vote
1answer
383 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
0answers
100 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
0answers
137 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
0answers
139 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 ...
2
votes
2answers
362 views

the minimal diameter of a quadrilateral

Let a convex quadrilateral ABCD with perimeter 1,d is the maximum of AB,AC,AD,BC,BD,CD,prove that d is not less than 1/3 we can prove that parallelogram ABCD with perimeter 1,than one of AC,BD is ...
1
vote
3answers
284 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
1answer
558 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 ...
23
votes
3answers
653 views

Largest possible volume of the convex hull of a curve of unit length

What is the largest possible volume of the convex hull of an open/closed curve of unit length in $\mathbb{R}^3$?
7
votes
1answer
346 views

Building a polyhedron from areas of its faces

Is there a known algorithm which, given a finite multiset (unordered list) of integers $A$, returns a yes/no answer for ...
12
votes
2answers
222 views

Smallest containing simplex

Let $V_n$ be the least real number such that for every convex subset of $\mathbb{R}^n$ with hypervolume $1$ there is a containing simplex with hypervolume $V_n$. What is known about $V_n$? Is there a ...
7
votes
2answers
237 views

$\kappa$-coloring of $\mathbb{R}^2$ and triangle with area 1

What is the largest cardinal number integer $\kappa$ such that every $\kappa$-coloring of $\mathbb{R}^2$ contains a triangle with area 1 and all vertices of the same color?
19
votes
8answers
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
1answer
473 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 ...
8
votes
7answers
766 views

Omniscient bots gathering on $\mathbb{Z}^2$

There are $N=n^2$ "bots" on distinct integer lattice points in the plane. Each knows the positions $p_i$ of all bots, and each has unlimited (private) memory. Each executes the same algorithm ...
1
vote
0answers
142 views

When is the conical hull of a finite set of vectors a subset of the space? (and tilings)

Consider a hypercube in n-dimensions, and take some projection down to an m-dimensional subspace. Now take all vertices and m-1 dimensional facets visible from some direction outside the projection. ...
9
votes
3answers
721 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 ...
4
votes
2answers
252 views

Isostatic graphs and the Henneberg conjecture

I have been reading "Combinatorial Rigidity" by Graver, Servatius and Servatius and I am interested in their chapter on rigidity in dimension $\geq$ 3. I have two questions. What is the current ...
2
votes
0answers
138 views

Minimally 6-connected 3D discrete lines that are convex lattice sets

There are several definitions of 3D discrete lines, e.g. http://diwww.epfl.ch/w3lsp/publications/discretegeo/nratddl.html , http://dx.doi.org/10.1007/978-3-642-19867-0_4 . However, I know of none that ...
1
vote
4answers
483 views

Decomposition of inner horns

Hi guys, I have a question. Prove or disproof the statement: Any inner horn $\Lambda[n,k],0< k< n $ admits a filtration $\mathbf{n}<\cdots<\Lambda[n,k]$, such that each step is filling an ...
5
votes
1answer
327 views

Convex tilings of the plane

For convex polyhedra you have Steinitz's theorem characterizing them as the 3-connected planar graphs. My question is not about spheric tilings, but about periodic tilings of the euclidean plane. Is ...
7
votes
3answers
631 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 ...
3
votes
0answers
229 views

Polygon illumination with perturbed reflections

Here is a variation on the classical polygon illumination problem. For $c \geq 0$ we say that a mirror has reflection index $c$ if whenever a ray hits the mirror with angle of incidence $\alpha$ then ...
9
votes
3answers
726 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
1answer
238 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
0answers
412 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 ...
7
votes
2answers
517 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 ...
4
votes
1answer
335 views

A “join” of ω-categorical simplices

Recall that the category of level trees $\mathcal{T}$ is defined to be the category $[\mathbb{N}^{op},\Delta_a]$, where $\Delta_a$ is the skeleton of the category of finite possibly empty linearly ...
10
votes
2answers
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 ...
20
votes
1answer
469 views

Voronoi cell of lattices with the same profile

Definition 1. Given a body $V$ in $\mathbb R^n$, the function $p_V\colon \mathbb R_+\to \mathbb R_+$ $$p_V(r)=\mathop{\rm vol} [V\cap B_r(0)]$$ will be called profile of $V$. Definition 2. Define ...
0
votes
1answer
256 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 ...