# Tiling relation on the set of partitions

Let $x\neq \emptyset$ be a set and let $\text{Part}(x)$ be the collection of all partitions of $x$. We need the following notation. Let $P \in \text{Part}(x)$ and $t\subseteq x$. We set $$P_{[t]} = \{p\in P:p\cap t \neq \emptyset\}.$$ We define the tiling relation on $\text{Part}(x)$ by $$P \triangleleft Q \textrm{ if and only if for all } S\subseteq P\textrm{ we have } \mathsf{card}(S) \leq \mathsf{card}(Q_{[\bigcup S]}).$$ In other words, the relation $P\triangleleft Q$ holds if no subset $S$ of $P$ is covered by a subset of $Q$ having a smaller cardinality than $S$.

Questions.

1. Is the relation $\triangleleft$ on $\text{Part}(x)$ transitive?
2. For $P,Q \in \text{Part}(x)$ is there $Z\in \text{Part}(x)$ such that
• $Z$ refines $P\cup Q$ and
• $Z \triangleleft P$ and $Z\triangleleft Q$?
• Thanks for accepting my answer - let me emphasise that I wasn't able to answer the second question entirely, and I would very much like to see the complete answer. – Dominic van der Zypen Jan 6 '15 at 12:30

Question 1. The answer is No. Let $x= \{1,2,3,4\}$. For $i\in \{1,2,3\}$ let $P_i$ be the partition that has $\{i, i+1\}$ as the only non-singleton partition block. Then $P_i\triangleleft P_{i+1}$ for $i = 1,2$, but it is easy to verify that $\neg(P_1 \triangleleft P_3)$.

Question 2. I can only answer this in the case that the base set $x$ is finite. Let $x$ be a set of cardinality $n\in \omega$, and let $P, Q \in \text{Part}(x)$. Consider the set

$$S = \{Y \in \text{Part}(x) : Y \textrm{ refines }P \cup Q\}$$

and set

$$m = \min \{\text{card}(Y) : Y \in S \}.$$

We have $m \leq n$ , and there is $Y_0 \in S$ with $\text{card}(Y_0) = m$. Then I claim that $Y_0 \triangleleft P$ and $Y_0 \triangleleft Q$. The reason is if $\neg(Y_0 \triangleleft P)$, say, then you can find a refinement of $Y_0 \cup P$ (which also refines $P \cup Q$) that has smaller cardinality than $Y_0$, contradicting the minimality of $\text{card}(Y_0)$.

However I would be interested to see what the answer is to Question 2 for base set $x$ infinite.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.994300127029419, "perplexity": 73.6589111776121}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2019-43/segments/1570986677230.18/warc/CC-MAIN-20191017222820-20191018010320-00005.warc.gz"}