## New answers tagged discrete-geometry

2

We can consider all given points as complex numbers, points of the complex plane. Then, as far as I understood, for all integers $m\ge 1$, $1\le j\le k$ we we have $$A_{m,j}=A_m+(P_m-A_m)\xi^{j-2},$$
where $\xi=\exp\frac{2\pi i}{k}$.
Since $A_{m+1,1}= A_{m,3}$, we have
$$A_{m+1}+(P_{m+1}-A_{m+1})\xi^{-1}=A_m+(P_m-A_m)\xi.$$
It follows
$$A_{m+1}=-A_m\xi+\frac{...

9

The answer to your question is no. If you have an irrdeucible projective variety $X$ of dimension $d$ with an affine paving, then for all $i < d/2$, the number of $i$-cells is less than or equal to the number of $(d-i)$-cells. This is the main idea of this paper by Bjorner and Ekedahl:
https://arxiv.org/pdf/math/0508022.pdf
The proof is as follows: the ...

2

The notion of $\mathcal{C}_j(G)$ is natural in terms of hypergraphs where is has been studied. If you rephrase in terms of a hypergraphs, then $\mathcal{C}_j(G)$ becomes the independence complex of the hypergraph. These have been studied a lot in (combinatorial) commutative algebra.
An independent set in a hypergraph is any subset of vertices which does not ...

5

We can get a lower bound on the order of $n \log n$.
I'll describe how to arrange $4^n$ points in general position to get $n 4^{n-1}$ squares.
The arrangement is described recursively. For the base case $n=1$, we have $4^1 = 4$ points, and you can probably guess how we should arrange them to get $1 \cdot 4^{1-1} = 1$ squares. Now suppose we have an ...

1

To add to my previous answer, a paper of Szabó and Tardos from 2006 ("Extremal problems for transversals in graphs with bounded degree") has a result related to the complex you defined in 2.

4

You may easily calculate everything in complex numbers. Denote $m=2n+1$, $w=e^{2\pi i/n}$, $Q_i=A_{i,3}=A_{i+1,2}$ for $i=i,2,\ldots$. We may suppose that $P_{m+i}=P_i$ for $i=1,\ldots,m$ and we have one sequence of $2m$ polygons. Then we have to prove $Q_{2m}=O$ (let $O=0$ be the origin) and that $C_k:=A_{k+m}-A_k$ satisfy $C_{k+1}=-w C_k$. This follows ...

1

The answer is no for $n \ge 2$. Consider open cubes $Q(c,1)=\{c_i <x_i <c_i+1\}$ of side $1$. Starting from $Q(0,1)$ and moving $c$ along the diagonal joining $0$ with $(1,\dotsc,1)$ one constructs $N$ cubes $Q(c_i,1)$ such that two of them always intersect and no cube is contained in the union of the others. Take $$z_i \in Q(c_i,1) \setminus \bigcup_{...

15

An example
Yes, here is a list of rational coordinates lying on the unit sphere, the convex hull of which is combinatorially equivalent to a regular dodecahedron. This polyhedron is invariant under reflections in three orthogonal hyperplanes (having a symmetry group $C_2 \times C_2 \times C_2$ of order 8, much smaller than the order-120 symmetry group of a ...

3

It doesn't answer the question, but this is too long for a comment. I just want to point out that this is not possible with general rectangles even for Lebesgue measure on $\mathbb{R}^2$. Since in one dimension we find that balls, cubes and rectangles are all the same this seems to indicate something more than the one-dimensional argument would be needed to ...

4

The upper bound conjecture of Motzkin, made a theorem by McMullen in 1970, states that the highest number of facets among all polytopes with $m$ vertices in $\mathbb R^n$ is the number of facets of the cyclic polytope $\Delta(m,n)$.

5

Here is an answer to Question 2. The following shape (attributed to Karl Scherer on this website) tiles into similar shapes of different sizes.
Convincing myself that it is not a rep-tile took me several case distinctions - I found it easiest to start with one of the right angles and construct the tiling from there until deriving a contradiction (angles of $...

2

Another family of fractal examples is provided by Thurston's famous unpublished notes:
http://timo.jolivet.free.fr/docs/ThurstonLectNotes.pdf .
Look at Figure 9.5.

0

Dmitri's answer is definitely correct. I just want to add my geometric intuition, and a generalization, which, in hindsight, is quite obvious.
All in all, we can have the following:
If $P\subset\Bbb R^d$ is a polytope with $n$ facets, each of which is combinatorially (or projectively) equivalent to $Q\subset\smash{\Bbb R^{d-1}}\!$, then for each $k\ge 1$ ...

3

It seems you did not restrict to finitely many scaled down copies of the tile. So here is one interesting tile for which you need infinitely many scaled down copies in order to tile the plane. On the left is the tile itself, and on the right is how to use scaled copies to tile an L tromino, after which it is trivial to tile the plane.

2

I think Timothy Chow's comment is right that there is no result about planar graphs with your lemma as an explicit corollary.
I believe the following 2007 research paper by Guido Helden might be of use to you: http://publications.rwth-aachen.de/record/62349/ It is about hamiltonicity of maximal planar graphs and planar triangulations, and starts with a very ...

3

Are you willing to allow tiles with fractal boundary? (I can see that you write "polygon" throughout, so maybe not?).
If so, then another example is the so-called "Koch snowflake". See https://en.wikipedia.org/wiki/Koch_snowflake#Tessellation_of_the_plane . If you allow such tiles, then this is also a positive answer to your Question 2....

13

Non-convex solutions to Question 1
Consider the following polygon (the outward angle on the right is the same as the inward angle at the top)
Since I didn't know any better way to show it does not tile the plane, I brute-forced my way through some case distinctions.
The only non-convex corner of any tile must meet a corner of another tile. It can't be ...

3

For an answer, see discussion of the degree of the Sperner boundary labelling in the Musin (2014) article https://arxiv.org/pdf/1405.7513.pdf
If the pdf link does not work try https://arxiv.org/abs/1405.7513
Effectively, a valid Sperner boundary labelling is a piecewise linear automorphism on the boundary with odd degree.

2

I also have no solution for $n=3$, but I have solutions for every $n > 3$. The constructions are sketched below, for each of them we fold along all grid lines; folding along the red lines first has helped me understand that this really gives a uniform cover of the unit square. The number of layers is equal to the area of the polygon.
Constructions for ...

17

Let $\mathcal{U}=\{A_1,\ldots,A_k\}$. Then for any element $x\in X$ there should exist a set $I(x)\subset \{1,\ldots,k\}$ such that $\cap_{i\in I(x)} A_i=\{x\}$. Note that $I(x)$ is not contained in $I(y)$ for $x\ne y$. Therefore $|X|\leqslant \binom{k}{\lfloor k/2\rfloor}$ by Sperner's theorem. On the other hand, if $|X|\leqslant \binom{k}{\lfloor k/2\...

9

Here is a construction that is within a constant factor of optimal.
You can find such an $\cal U$ containing $2 \lceil \log_2 |X|\rceil $ sets: identify $X$ with a subset of $\{0,1\}^{\lceil \log_2 |X|\rceil}$ and take $U_i$ to be the set of all elements whose $i$-th coordinate is $0$, and $V_i$ to be the set of all elements whose $i$-th coordinate is $1$. ...

2

For every $k\ge 2$ there is a non-rectangular shape allowing a uniform folding for all $n$ that are multiplies of $k$:
The reason is that you can uniformly fold it into a rectangle with $k$ layers.
If you are looking for convex shapes, then $k=2$ above is convex.
Here is a non-rectangular convex shape admitting a uniform folding with three layers.
If you ...

Top 50 recent answers are included

#### Related Tags

discrete-geometry × 1316mg.metric-geometry × 407

co.combinatorics × 400

convex-polytopes × 153

reference-request × 134

graph-theory × 128

plane-geometry × 85

convex-geometry × 78

computational-geometry × 71

pr.probability × 66

polyhedra × 60

tiling × 58

nt.number-theory × 53

gt.geometric-topology × 51

ag.algebraic-geometry × 41

packing-and-covering × 38

algorithms × 37

euclidean-geometry × 33

linear-algebra × 32

lattices × 32

at.algebraic-topology × 28

dg.differential-geometry × 27

sphere-packing × 25

polytopes × 22

gr.group-theory × 20