All Questions
Tagged with tiling co.combinatorics
94 questions
9
votes
0
answers
291
views
Tilings in finite (not necessarily Abelian) groups
Let $G$ be a finite (not necessarily abelian) group. We call $A \subseteq G$ a right-tiling (for simplicity, a tiling) of $G$ if there exists a $B \subseteq G$ so that
$$ G = \bigsqcup_{b\in B} bA.$$
...
- 1,354
0
votes
1
answer
98
views
Chromatic tiling complexity and the chromatic number conjecture
Let $T$ be a finite set of tiles in $\mathbb{R}^d$. A tiling of $\mathbb{R}^d$ by $T$ is a collection of disjoint translates of tiles in $T$ whose union is $\mathbb{R}^d$. A tiling is $k$-chromatic if ...
2
votes
0
answers
62
views
On convex polygons that can be cut into convex and mutually congruent pieces in exactly one way
Observations: any thin isosceles triangle has exactly 1 partition into 2 congruent pieces - only 1 line, bisector of its apex, does it.
By attaching a right triangle with base 1 and altitude 2 to an ...
- 5,979
2
votes
2
answers
226
views
On cutting tetrahedrons into mutually congruent pieces
Simple observations: A regular tetrahedron can be cut into 2 mutually congruent pieces (in 3 obvious ways which are all basically the same way, giving one and same pair of congruent pieces). The ...
- 5,979
0
votes
0
answers
78
views
Are there triangles that can be cut into 7 mutually congruent connected polygons?
First question below had appeared in a note at Triangles that can be cut into mutually congruent and non-convex polygons
Following the results of Beeson quoted in the answer at Subdivision of ...
- 5,979
4
votes
0
answers
138
views
Hyponontiling Wang tiles
Call a finite collection of tiles that can tile the plane if we have to use each tile at least once tiling.
Is there a collection of at least 3 tiles that is not tiling, but such that after removing ...
- 18.7k
4
votes
0
answers
175
views
Can a square be partitioned into mutually non-congruent triangles all of same area and perimeter?
It is known that the plane cannot be tiled by pair-wise non-congruent triangles all having same area and same perimeter (https://arxiv.org/abs/1711.04504).
Question: Can a square be partitioned into ...
- 5,979
1
vote
1
answer
138
views
Recognizability/unique composition property for substitution tiling
This may be a very basic question, but I have not found an answer to it so far in my search. The question is whether there is an "algorithmic" way to check unique-composition/recognizability ...
- 633
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
0
votes
1
answer
212
views
Does $\mathbb{Z}\times\mathbb{Z}$ have an aperiodic monotile?
For any set $S\subseteq \mathbb{Z}\times\mathbb{Z}= \mathbb{Z}^2$ and $a\in \mathbb{Z}^2$, we set $a+S = \{a+s: s\in S\}$, where $+$ is the componentwise addition in $\mathbb{Z}^2$. Moreover, for any ...
- 48.8k
2
votes
1
answer
107
views
Counting problem, tiling rectangle with two types right isosceles triangle
How many ways are there to tile a rectangle of size $m\times n$ with two types of isosceles triangle, type 1 having area $\frac{1}{2}$ and type 2 having area 1?
I know with only type 1 there are $2^{...
- 31
3
votes
2
answers
397
views
An "incomplete" tiling?
Given an $m\times n$ chess board, we place $p$ $2\times 1$ dominoes on the board so that they don't overlap. How many ways can we place them?
When each square of the board is covered by a domino this ...
- 380
8
votes
1
answer
248
views
For which $n$ does a y-formed $n$-polyomino tile a $n \times n \times n$-cube?
I got from my children as a gift a puzzle consisting of 25 y-shaped 5-polyominoes that form a $5 \times 5 \times 5$-cube (see picture).
I'm wondering for which $n$ does a y-formed $n$-polyomino tile a ...
- 4,014
6
votes
5
answers
542
views
Tiling with ten-fold symmetry and (unoriented) Penrose tiles?
Consider tilings of the plane made out of rhombi of side 1 and either angles $\pi/10$ and $2\pi/5$ or angles $\pi/5$ and $3\pi/10$. If we give a certain orientation to the edges and respect that ...
- 20.1k
5
votes
1
answer
397
views
How much of an aperiodic tiling is needed to force aperiodicity?
Consider an aperiodic tiling. By definition, there is a $C$ such that, for any box of side $C$, the part of the tiling contained in the box can be continued to the whole plane only in a non-periodic ...
- 20.1k
3
votes
1
answer
230
views
Tiling planar integer lattice by finite point sets
I am interested in the following question.
Are there nice characterizations of the finite sets $S\subseteq \mathbb{Z}\times\mathbb{Z}$ that tile $ \mathbb{Z}\times\mathbb{Z}$ by translations (i.e. $\...
- 1,305
1
vote
2
answers
329
views
Sufficient conditions for periodic tiling by Wang tiles
I'm recently interested in whether a sub-shift of finite type contains a doubly-periodic problem, when the set of configurations is of the sort $\mathcal{A}^{\mathbb{Z}^2}$. When $Q_2=\{0,1\}^2$, and ...
- 633
2
votes
0
answers
208
views
Aperiodic tilings of the plane by squares and rhombi
Consider tilings of the plane by unit squares and by rhombi of unit side length and angles $\pi/3$, $2\pi/3$. It is easy to come up with periodic tilings of the plane - consider the following:
(from ...
- 20.1k
2
votes
0
answers
171
views
Square-and-equilateral-triangle aperiodic tiling with $\leq 4$ prototiles?
There exist aperiodic tilings composed of square and equilateral-triangle tiles of unit side length: see https://tilings.math.uni-bielefeld.de/substitution/square-triangle/ and https://hal.archives-...
- 20.1k
25
votes
1
answer
2k
views
Polyomino that can tile itself
Find all polyomino $P$ such that we can tile $nP$ with $n^2$ copies of $P$ for all $n\in \mathbb{N}$. ($nP$ is a polynomino similar to $P$ with scale factor $n$)
I conjecture that there are only $4$ ...
- 1,462
2
votes
0
answers
108
views
number of ways to cover an $m × n$ rectangle
Given a positive integer $k\ge2$, let be $f_k(m,n)$ the number of ways to cover an $m × n$ rectangle with $mn/k$ tiles ( $1×k$ or $k×1$)
$f_2(m,n)$ is kasteleyn formula
$f_k(m,n)$?
- 683
42
votes
2
answers
2k
views
Does any set of dominoes tile some common figure?
Let $D_1,\dots,D_n \subset \mathbb{Z}^2$ be two-point sets, i.e. 'dominoes' (unlike common dominoes, these are not necessarily connected, but I couldn't come up with a better name).
Does there always ...
- 1,209
2
votes
0
answers
104
views
Three dimensional Cairo Pentagonal Tiling
The Cairo pentagonal tiling is an interesting tessellation of the two-dimensional plane by irregular pentagons, which is given by taking two irregular hexagonal tilings, congruent but perpendicular to ...
- 121
3
votes
1
answer
307
views
Is there a formula for a number of one-sided N-ominoes?
As we all know, Polyominoes are shapes which consist of certain number of squares connected together. A famous videogame - Tetris - has a gameplay based around tetraminoes - polyominoes with 4 squares ...
- 31
2
votes
1
answer
84
views
What is the average component size of a coloring?
Supose each cell of a big (or infinite) grid is colored at random by one of $k$ colors. Then the connected monochromatic components (here components are not supposed to contain "wasp waists",...
- 13.4k
20
votes
4
answers
2k
views
Non-enumerative proof that, in average, less than 50% of tiles in domino tiling of 2-by-n rectangle are vertical?
Is there a non-enumerative proof that, in average, less than 50% of tiles in domino tiling of 2-by-n rectangle are vertical?
It is a nice exercise with rational generating functions (or equivalently, ...
- 24.2k
1
vote
1
answer
216
views
Maximum number of colors for an optimal tiling which guarantees infinite paths
This question is a more applicable version of the question I've asked in mathexchange recently:
What is the maximum number of colors we can use to color $N^2$ square sub-tiles of $N×N$ square
block ...
- 289
15
votes
4
answers
887
views
Tiling a rectangle with all simply connected polyominoes of fixed size
For which values of $n$ can we tile some rectangle with one copy of each free simply-connected $n$-omino (that is, each polyomino with $n$ squares that has no holes)?
It appears that it is possible ...
- 421
4
votes
0
answers
92
views
Possible cardinalities of spherical tiling
Suppose that we have a tiling of $n$-dimensional (I want to get answer for $n = 4$, but general result would be nice!) sphere by isometric tiles strictly contained inside the right-angled simplex. ...
- 4,600
3
votes
2
answers
308
views
For what n and t can a square be partitioned into n similar rectangles in t congruence classes?
It is known that a square can be partitioned into three similar rectangles, all mutually non-congruent. I don't think it's possible with four. With what numbers of rectangles can this be achieved? And ...
user159323
3
votes
0
answers
83
views
Distance spectra of uniform tilings
Let a uniform tiling be defined by a vertex configuration $(n_1.n_2.\cdots.n_k)^m$, which is either spherical, Euclidean or hyperbolic. Assume that the tiling is vertex-transitive, especially that ...
- 9,720
21
votes
1
answer
1k
views
Tiling rectangle with trominoes — an invariant
There are two types of trominoes, straight shapes and L-shaped. Suppose a rectangle $R$ admits at least one tiling using trominoes, with an even number of L-trominoes.
EDIT: we do not admit ALL ...
- 15.8k
1
vote
1
answer
444
views
Looking for an efficient way of maximising 'pair scores' for subset of 30 selected from 50 to 10 000 objects
Context: I have a tiling program that uses a directed breadth first search algorithm. It is 'directed' by what I call 'pair scoring'. There are $N$ polyforms (pieces) used in the tiling. I have an $N\...
- 613
4
votes
1
answer
340
views
Triangling the triangle
Is it possible to tile an equilateral integer-sided triangle with smaller equilateral integer-sided triangles, with no congruent triangles touching? This has been answered in the negative for the case ...
- 613
2
votes
0
answers
142
views
Tradeoffs in translation-invariant tilings of $\mathbb{R}^3$
Suppose I tile $\mathbb{R}^3$ in a ($\mathbb{Z}^3$-)translation-invariant manner. If we insist on the tiling being regular, then we are left with only the cubic tiling. However, suppose that we ...
- 238
7
votes
1
answer
354
views
Changing tiles by swapping squares
In an $n\times n$ table, initially there is a $1\times n$ tile in each row. A swap is an operation that involves choosing two tiles, move one square from the first to the second tile, and ...
- 1,209
3
votes
0
answers
137
views
Aperiodic tile with rational area
Margulis and Mozes constructed aperiodic tiling system on the hyperbolic plane consisting of a single tile(hyperbolic polygon) whose area (or each inner angle) is irrational multiple of $\pi$. Having ...
- 745
12
votes
2
answers
454
views
Random Walk on Pentagonal Tiling
I’ve recently been looking at closed walks on tilings of the plane in which the “player” can move from one tile to any of its edge-adjacent neighbors. In particular, I’m trying to find asymptotic ...
5
votes
0
answers
157
views
Tiling rectangles using all squares of sides 1, 2, 3, ..., n
Do integers n greater than 2 exist such that all the squares of sides 1, 2, 3, ..., n can be partitioned into two or more sets (none a singleton) each of whose squares can be used to tile a rectangle?
- 3,707
5
votes
0
answers
105
views
Hooks, monomers, dimers and Young diagrams: Part II
As promised, I've upgraded my last question.
Consider the $k$-by-$n$ partition $\lambda_n=(n,\dots,n)$ and its corresponding Young diagram $Y_{n,k}$, which is a $k\times n$ rectangle of cells. Now, ...
- 43.1k
4
votes
0
answers
154
views
Hooks, monomers, dimers and Young diagrams: Part I
Following Richard Stanley's pointers regarding my earlier MO question, I decided to "scale-down" the problem and add a slight "twist" to it.
Consider the one-line partition $\lambda_n=(n)$ and its ...
- 43.1k
5
votes
0
answers
150
views
monomer-dimer tiling of a Young diagram
As a modest start, I propose the below problem for a special set of partitions. Perhaps it is known.
Let $\lambda_n=(n,n-1,\dots,2,1)$ be the staircase partition and its corresponding Young diagram $...
- 43.1k
7
votes
3
answers
981
views
Tiling a square with rectangles whose areas or perimeters are 1, 2, 3, ..., N
For which positive integers N does there exist a square that can be completely tiled with N rectangles of integer sides whose areas or perimeters are precisely 1, 2, 3, ..., N?
- 3,707
4
votes
0
answers
146
views
Tiling squares with oblongs
An oblong is a rectangle whose width and length are consecutive integers: 1x2, 2x3, 3x4, etc. Does N exist such that it is possible to split the first N oblongs into 2 or more non-intersecting sets so ...
- 3,707
3
votes
0
answers
109
views
chromatic number of plane using Cairo pentagonal tiling
Scale the Cairo pentagonal tiling so the short side is of length 1. Then it is easy to colour the tiling with 8 colours, two parallel ribbons of four colours each, to establish that the chromatic ...
2
votes
0
answers
111
views
dividing a square into unique rectangles with the same perimeter
There's a solution for dividing a square into unique rectangles with the same area which is the blanche dissection.
There's also a solution for dividing a square into unique rectangles with the same ...
- 21
4
votes
0
answers
164
views
Tileability and computabilty
Let $n>2$ be an integer. We consider $n$ pairs $(x_1,y_1),\dotsc,(x_n,y_n)$ in $\mathbb{N}^2$, and the polygon defined by drawing a straight line from $(x_k, y_k)$ to $(x_{k+1},y_{k+1})$ and from $(...
- 48.8k
1
vote
0
answers
125
views
Minimal period for a bounded Langton's ant moving on a tessellation
We consider Langton's ant on the 2D plane, but we replace the square lattice by a Voronoi tessellation obtained from a finite set of points (it could be another tessellation, however directions such ...
- 111
3
votes
0
answers
106
views
How many positions of a tile can occur in a periodic tiling?
In my recent question about polygonal tilings where tiles can occur in infinitely many positions, both constructions given as solutions are of self-similar nature. This means in particular that there ...
- 13.4k
1
vote
1
answer
163
views
Are there polygonal tilings with infinitely many positions, each (or at least one) occurring infinitely often?
My recent question about polygonal tilings where tiles can occur in infinitely many positions has been answered by two nice constructions (besides Jan Kyncl's answer, there is the Conway tessellation ...
- 13.4k