An infinite network is partitioned with dominos. Prove there exist three other tilings with dominos, have neither common domino with the existing tiling nor with each other. Clarifications for network: It means an infinite board consisting of square cells.
Problem
Source: IRAN RMM TST 2019 p3
Tags: combinatorics, Tiling, TST, Iranian TST
11.03.2020 21:52
By "network" do you mean a graph?
11.03.2020 21:58
that was the wording I was sent (such problems are above my knowledge, therefore I do not know what it means)
12.03.2020 00:18
stroller wrote: By "network" do you mean a graph? It means an infinite board consisting of square cells.
14.03.2020 15:15
We color the infinite board in two colors as a chessboard. Consider the bipartite graph $G(B,W)$, $B$ - black cells, $W$ - white cells. Two vertices $b\in B, w\in W$ are connected iff they as cells share a same side. Note, $G$ is $4$-regular (any vertex has degree $4$). The dominoes cover can be considered as a perfect matching in $G(B,W)$. We want to find another $3$ of them not sharing a common edge. We remove the matching edges and let $G'(B,W)$ be the corresponding 3-regular bipartite graph, we obtain. The idea is to show it also has a matching. A version of Hall's marriage theorem for infinite graphs will be used. Let $B'\subset B$ is finite. We have $|N(B')|\le 3|B'|/3=|B'|$. By Hall's marriage theorem (infinite version) there exists an injection $f: B\to W$ such that $\forall b\in B, b\,f(b)$ is an edge in $G'$. In the same way there exists an injection $g:W\to B$ with the same property. Take some $b\in B$, and consider the sequence $f(b), g\circ f(b), f\circ g\circ f(b), \dots $. Two possibilities: either $b=g\circ f\circ \dots g\circ f(b)$ after finitely many steps, or this is an infinite sequence of distinct vertices. In the latter case we consider $g^{-1}(b), f^{-1}\circ g^{-1}(b),\dots$, and proceed till $g^{-1}$ or $f^{-1}$ is not defined. In this way we obtain a family of disjoint orbits (paths in $G'$) which are either cyclic or infinite in one or both directions. That family of paths covers $B\cup W$. In each infinite or cyclic path, a perfect matching can be constructed, and we are done. Removing the edges of the obtained matching, we get a bipartite 2-regular graph $G''(B,W)$ which in the same way generate two other perfect matchings. Remark. It's also commented in my blog.
14.03.2022 18:57
Color the board in a checkerboard manner. Consider the bipartite graph $(S,T)$ where $S$ is the set of black squares and $T$ is the set of white squares. Connect an edge between two vertices if and only if they are adjacent and they are NOT part of the same domino. I get an infinite bipartite graph where $\deg(v)=3$ for all vertices $v$. It suffices to show the graph can be decomposed into three matchings (which corresponds to domino tilings) First, when $\deg(v)=2$ for all vertices $v$, the graph is the union of a finite even cycle (which has a matching) or a line (which has a matching). Therefore, Hall's condition must be satisfied. Next, when $\deg(v)=3$ for all vertices $v$, since Hall's condition is satisfied when $\deg(v)=2$ it follows that Hall must be satisfied here. Therefore, delete a matching and finish the way $\deg(v)=2$ is finished.