Abstract. Two permutations [Formula: see text] and [Formula: see text] are [Formula: see text]-similar if they can be decomposed into subpermutations [Formula: see text] and [Formula: see text] such that [Formula: see text] is order-isomorphic to [Formula: see text] for all [Formula: see text]. Recently, Dudek, Grytczuk, and Ruciński Variations on twins in permutations, Electron. J. Combin., 28 (2021), P3.19. posed the problem of determining the minimum [Formula: see text] for which two permutations chosen independently and uniformly at random are [Formula: see text]-similar. We show that two such permutations are [Formula: see text]-similar with high probability, which is tight up to a polylogarithmic factor. Our result also generalizes to simultaneous decompositions of multiple permutations.

Two boxes in $\mathbb{R}^d$ are comparable if one of them is a subset of a translation of the other one. The comparable box dimension of a graph $G$ is the minimum integer $d$ such that $G$ can be represented as a touching graph of comparable axis-aligned boxes in $\mathbb{R}^d$. We show that proper minor-closed classes have bounded comparable box dimensions and explore further properties of this notion.

Let $\mathcal F$ be an antichain of finite subsets of $\mathbb N$. How quickly can the quantities $|\mathcal{F}\cap 2^{[n]}|$ grow as $n\to\infty$? We show that for any sequence $(f_n)_{n\ge n_0}$ of positive integers satisfying $\sum_{n=n_0}^\infty f_n/2^n \le 1/4$ and $f_n\le f_{n+1}\le 2f_n$, there exists an infinite antichain $\mathcal{F}$ of finite subsets of $\mathbb{N}$ such that $|\F\cap 2^{[n]}| \geq f_n$ for all $n\ge n_0$. It follows that for any $\varepsilon>0$ there exists an antichain $\mathcal{F}\subseteq 2^{\mathbb{N}}$ such that $\liminf_{n \to \infty} |\mathcal{F}\cap 2^{[n]}| \cdot \big(\frac{2^n}{n\log^{1+\varepsilon} n}\big)^{-1} > 0.$ This resolves a problem of Sudakov, Tomon, and Wagner in a strong form and is essentially tight.