All Questions
763 questions with no upvoted or accepted answers
45
votes
0
answers
921
views
Extending a line-arrangement so that the bounded components of its complement are triangles
Given a finite collection of lines $L_1,\dots,L_m$ in ${\bf{R}}^2$, let $R_1,\dots,R_n$ be the connected components of ${\bf{R}}^2 \setminus (L_1 \cup \dots \cup L_m)$, and say that $\{L_1,\dots,L_m\}...
- 19.7k
43
votes
0
answers
1k
views
Can a regular icosahedron contain a rational point on each face?
The title says it all: Is there a (regular) icosahedron containing a rational point on each of its faces?
For other Platonic solids, the affirmative answer is easy. Indeed, regular tetrahedra, cubes, ...
- 23.7k
36
votes
0
answers
2k
views
3-colorings of the unit distance graph of $\Bbb R^3$
Let $\Gamma$ be the unit distance graph of $\Bbb R^3$: points $(x,y)$ form an edge if $|x,y|=1$.
Let $(A,B,C,D)$ be a unit side rhombus in the plane, with a transcendental diagonal, e.g. $A = (\alpha,...
- 17k
32
votes
0
answers
1k
views
Minimal number of intersections in a convex $n$-gon?
For a convex polygon $P$, draw all the diagonals of $P$ and consider the intersection points made by those diagonals. Let $f(n)$ be the minimal number of such intersections where $P$ ranges over all ...
- 1,474
26
votes
0
answers
512
views
A non-self-intersecting unit side length polygon in a unit square has odd number of sides unless it is the square itself
This is the same question as here in SE.
I have a conjecture, it is like this:
Suppose there is a non-self-intersecting polygon lies inside a closed square of length $1$. The polygon has every side ...
- 843
26
votes
0
answers
359
views
Can 4-space be partitioned into Klein bottles?
It is known that $\mathbb{R}^3$ can be partitioned into disjoint circles,
or into disjoint unit circles, or into congruent copies of a real-analytic curve
(Is it possible to partition $\mathbb R^3$ ...
- 151k
24
votes
0
answers
760
views
How much of the plane is 4-colorable?
In 1981, Falconer proved that the measurable chromatic number of the plane is at least 5. That is, there are no measurable sets $A_1,A_2,A_3,A_4\subseteq\mathbb{R}^2$, each avoiding unit distances, ...
- 7,633
21
votes
0
answers
453
views
Does every 5-celled animal tile the plane?
An animal in the plane is a finite set of grid-aligned unit squares in $\mathbb{R}^2$. (The definition is the same as a polyomino, but where we relax the connectivity requirement.) One may ...
- 3,068
20
votes
0
answers
433
views
Is the dodecahedron flexible (as a polytope with fixed edge-lengths)?
Consider the (regular) dodecahedron $D\subset\Bbb R^3$. I want to continuously deform it so that throughout the deformation
it stays a convex polytope,
it stays a combinatorial dodecahedron (i.e. its ...
- 13.6k
17
votes
0
answers
488
views
Large almost equilateral sets in finite-dimensional Banach spaces
Question: Does there exist a function $C:~(0,1)\to
(0,\infty)$ such that for each $\varepsilon\in(0,1)$ every Banach space
$X$ of dimension $\ge C(\varepsilon)\log n$ contains an $n$-point
set $\{x_i\...
- 4,878
17
votes
0
answers
731
views
Does every connected set that is not a line segment cross some dyadic square?
A dyadic square is a subset of $R^2$ of the form $x + 2^{-n} [0,1]^2$ with $x \in 2^{-m} Z^2$, for integers $m,n \geq 0$. We say that a set $A$ crosses a square $S$ if there exists a connected subset ...
- 171
16
votes
0
answers
576
views
Snakes on a plane
A sleeping bag for a baby snake in $d$ dimensions (no, really) is a subset of $\mathbb{R}^d$ which can cover (via translation and rotation) every (piecewise-smooth for concreteness) curve of unit ...
- 21.1k
16
votes
0
answers
411
views
Simple disproof of Danzer — Grünbaum conjecture
I asked this question on the MSE, but I did not get an answer. I hope that one of the experienced participants will check the correctness of the proof or the truth of the statement (and, perhaps, will ...
- 269
16
votes
0
answers
851
views
Self-avoiding random walks that always turn
I am wondering if the statistics of self-avoiding random lattice-walks
on $\mathbb{Z}^2$
that turn left or right at each step (i.e., they cannot continue the
direction of the preceding step) have been ...
- 151k
16
votes
0
answers
298
views
Realization spaces of 3-dimensional polytopes with fixed face areas
It is a well-know result (Steinitz, 1922) that the realization space of 3-dimensional convex polytopes with fixed combinatorics is contractible.
A proof of this theorem can be found for instance in ...
- 31.2k
15
votes
0
answers
477
views
Expanding disks lead to what packing of the plane?
Suppose one sprinkles points uniformly at random on the infinite Euclidean plane,
with some density $\rho$ per unit area.
View the points as disks of radius zero.
Now the radii $r$ of all disks grows ...
- 151k
15
votes
0
answers
2k
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$ ...
14
votes
0
answers
270
views
Regular $n$-gon with diagonals: bounds on area of largest cell?
Consider a regular $n$-gon of side length $1$ with diagonals. Here is an example with $n=11$ (from geogebra applet).
I've been trying to find, in terms of $n$, bounds on the area of the largest cell, ...
- 3,527
14
votes
0
answers
479
views
Does every convex polyhedron have a combinatorially isomorphic counterpart whose angles between edges are rational multiples of $\pi$?
After reading these very interesting questions, I came up with another one:
Does every convex polyhedron have a combinatorially isomorphic counterpart whose angles between all pairs of edges meeting ...
- 532
14
votes
0
answers
416
views
Is the equidissection spectrum closed under addition?
If a polygon can be cut into $m$ as well as into $n$ triangular pieces of equal area, can it also be cut into $m+n$ triangles of equal area?
(I'm editing after realizing that my conjecture that a ...
- 5,492
14
votes
0
answers
4k
views
Minimum tiling of a rectangle by squares
Given the $n\times m$ rectangle, I want to compute the minimum number of integer-sided squares needed to tile it (possibly of different sizes).
Is there an efficient way to calculate this?
- 1,015
13
votes
0
answers
378
views
Is a convex polyhedron determined by its edge lengths and angular defects?
Let's consider 3-dimensional convex polyhedra $P\subset\Bbb R^3$.
The angular defect at a vertex $v$ is $2\pi$ minus the sum of the interior angles of the incident faces at $v$.
Question:
Is a ...
- 13.6k
13
votes
0
answers
573
views
What are the known convex polyhedra with congruent faces?
Note: I originally asked this question on math.SE here, where I posted a bounty on the question but received no answers after a week despite apparent interest in the problem. I'm hoping MathOverflow ...
- 3,068
12
votes
0
answers
168
views
Can the optimal packing density in $\mathbb{Z}^d$ be irrational?
For a finite $S \subset \mathbb{Z}^d$, let $d_p(S)$ be its optimal packing density. That is, the maximal lower asymptotic density of $A+S$, where $A \subset \mathbb{Z}^d$ is such that $(a_1+S)\cap (...
- 1,209
12
votes
0
answers
570
views
Computer searches for the $g$-conjecture
McMullen's $g$-conjecture aims the classify possible $f$-vectors of simplicial $d$-spheres. The $g$-conjecture has been proven for polytopal spheres and for simplicial spheres of dimension $d < 5$. ...
- 7,875
12
votes
0
answers
1k
views
Hrushovski's Construction
Zilber expressed a conjecture for $\aleph_{1}$- categorical theories (In the 80s).
Zilber's Conjecture: The geometry of any $\aleph_{1}$- categorical structure is one of the following:
(a) Trivial (...
- 1,872
12
votes
0
answers
533
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 ...
11
votes
0
answers
169
views
Worst margin when halving a hypercube with a hyperplane
Consider the $n$-cube $C_n=\lbrace-1,1\rbrace^n$ and the problem of partitioning it into halves with hyperplanes through the origin that avoid all its points. We can parameterize the hyperplanes by ...
- 1,085
11
votes
0
answers
445
views
What sequence maximizes the final distance?
This problem was created by professor Ronaldo Garcia from Universidade Federal de Goiás (UFG) and he showed it to me at an event in my university. This problem has a lot of history and he told me he ...
11
votes
0
answers
239
views
Euclidean realizations of a configuration of $27$ points and $45$ lines
Let $GQ(2,4)$ denote the abstract configuration (=incidence structure) consisting of $27$ points and $45$ lines, with $3$ points on leach line and $5$ lines through each point, which can be described ...
- 32.5k
10
votes
0
answers
177
views
Minimum reflection paths in a mirror polygon
Let $P$ be a simple, orthogonal polygon of $n$ edges, i.e., one whose edges meet at right angles,
and is non-self-intersecting;
also known as a rectilinear polygon.
Treat every edge of $P$ as a ...
- 151k
10
votes
0
answers
453
views
Fast method to verify if a point belongs to a given convex $d$-polytope
We are given a $d$-dimensional convex polytope $P\in\mathbb{R}^d$. Assume we have all the supporting hyperplanes describing $P$ and its vertices. Let $S$ be a sequence of $n\gg 1$ points $\mathbb{R}^d$...
- 1,677
10
votes
0
answers
609
views
A robust version of Harper's theorem
Let $S$ be subset of $\{0,1\}^n$ with cardinality $k$.
Denote by $\Gamma_r(S)$ the union of all Hamming balls with centers in $S$ and radius $r$.
Harpers's theorem states that $\Gamma_d(S)$ is minimal ...
- 2,576
10
votes
0
answers
2k
views
Number of rectangles in an n-by-n grid of points
I am seeking a formula for the number of rectangles with vertices belonging to an $n \times n$ square grid of points. This is sequence A085582 in the OEIS. Note that the grid in question has $n^2$ ...
- 856
10
votes
0
answers
261
views
Fundamental circuit characterization of matroid independence complexes
I have the following characterization of independence complexes of matroids, which I think is standard but I can't find a reference. Here it goes:
A pure simplicial complex $\Delta$ is the ...
10
votes
0
answers
175
views
A combinatorial proof of the Harrow--Kolla--Schulman theorem
Let $Q^n := \{0,1\}^n$ be the Hamming cube with the Hamming metric. (Recall that the Hamming is defined by the distance $d(x,y) := \# \{ i : x_i \neq y_i \}$.
For integers $0 \leq k \leq n$, define a ...
- 679
10
votes
0
answers
722
views
Fractional Matching version of Hall's Marriage theorem
Let $G=(S,T,E)$ be a bipartite graph, $|S|=|T|$. Then the following are equivalent:
1) there exist a perfect matching in $G$;
2) there exist non-negative weights on edges such that the sum of ...
- 109k
10
votes
0
answers
418
views
Determining convexity of a polygon from its Fourier coefficients
Consider an $n$-sided polygonal curve in the plane, represented by an ordered set of points $(x_0, x_1, \ldots, x_{n-1})$; line segments connect consecutive points and also $x_{n-1}$ to $x_0$. It is ...
- 553
10
votes
0
answers
493
views
Rectangology and squareology
I thought that rectangles were simple, and squares even simpler. Until my research has led me to several questions about rectangles and squares, which I can't solve.
I started by posting this question ...
- 3,549
10
votes
0
answers
1k
views
Interpolating points with minimum curvature constraint
I have $n$ points $p_i$ strictly interior to a rectangle $R$,
and I would like to connect them with a curve $C$ whose curvature is as low as possible.
Let $\kappa_\max(C)$ be the sharpest (largest ...
- 151k
9
votes
0
answers
144
views
Which polytopes have compact realization spaces?
Let $P\subset\Bbb R^d$ be a convex polytope.
Its reduced realization space is the space of all combinatorially equivalent polytopes modulo projective transformations.
I am interested in polytopes for ...
- 13.6k
9
votes
0
answers
187
views
Cubing the cube - as 'perfectly' as possible
Ref: https://en.wikipedia.org/wiki/Squaring_the_square
A perfect cubing of a cube is a partition of the cube into some finite number of smaller cubes that are pair-wise non-congruent. The above page ...
- 5,979
9
votes
0
answers
144
views
How many simplicial spheres with $n$ vertices and $N$ facets?
Let $s_d(n,N)$ be the number of different $d$-dimensional simplicial spheres on $n$ labelled vertices and $N$ facets (= $d$-simplices). I am in search for the best know upper bounds, especially for $d\...
- 13.6k
9
votes
0
answers
100
views
A characterization of root systems via their intersections with halfspaces
In a recent preprint I obtained a nice characterization of root systems as a side product.
I can imagine that this was known before, and that a source for this statement can shorten the proof of my ...
- 13.6k
9
votes
0
answers
337
views
Which tetrahedra are scissor congruent to a cube?
Question: Which Euclidean tetrahedra are scissor congruent to cubes?
Consider a Euclidean tetrahedron $T$ in $\mathbb{R}^3$ with edge lengths $l_1,\ldots, l_6$ and dihedral angles $\alpha_1,\ldots, \...
- 4,316
9
votes
0
answers
327
views
Why does Loday call the permutohedra "zylchgons"?
Today I was reading Jean-Louis Loday's classic paper, "Realization of the Stasheff polytope", in which he produces a simple and very pretty realization of the associahedra as convex polytopes. He ...
- 1,589
9
votes
0
answers
186
views
Interactions between pseudoline arrangements and braid groups?
It is common to represent
pseudoline arrangements
as wiring diagrams:
Fig. from: "Hamiltonicity and colorings of arrangement ...
- 151k
9
votes
0
answers
237
views
Herding sheep in a polygon
Imagine sheep fill a simple (simply connected) polygon $P$, except
at one vertex $x$ there is no sheep.
One convex vertex $g$ of $P$ is a gate through which the sheep should pass.
A herding dog sits ...
- 151k
9
votes
0
answers
175
views
How many components are there in the space of "generic" planar N-gons? (Mnev's revenge)
Call an ordered $N$-tuple of points in the Euclidean plane ${\mathbb R} ^2$ "in general position" if no three points of the points in the set are collinear. As a function of $N$ how many components ...
- 8,336
9
votes
0
answers
290
views
Neighborly family of coins
Here is a puzzle:
Find 5 identical coins. Can you arrange them so that every coin is touching every other coin?
The solution is here. The hint is: use the third dimension.
My questions are ...
- 2,581