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.

A matrix is homogeneous if all of its entries are equal. Let $P$ be a $2\times 2$ zero-one matrix that is not homogeneous. We prove that if an $n\times n$ zero-one matrix $A$ does not contain $P$ as a submatrix, then $A$ has a $cn\times cn$ homogeneous submatrix for a suitable constant $c>0$. We further provide an almost complete characterization of the matrices $P$ (missing only finitely many cases) such that forbidding $P$ in $A$ guarantees an $n^{1-o(1)}\times n^{1-o(1)}$ homogeneous submatrix. We apply our results to chordal bipartite graphs, totally balanced matrices, halfplane arrangements, and string graphs.

The $t$-colored rainbow saturation number ${rsat}_t(n,F)$ is the minimum size of a $t$-edge-colored graph on $n$ vertices that contains no rainbow copy of $F$, but the addition of any missing edge in any color creates such a rainbow copy. Barrus et al. conjectured that ${rsat}_t(n,K_s) = \Theta(n\log n)$ for every $s\ge 3$ and $t\ge \binom{s}{2}$. In this short note we prove the conjecture in a strong sense, asymptotically determining the rainbow saturation number for triangles. Our lower bound is probabilistic in spirit, and the upper bound is based on the Shannon capacity of a certain family of cliques.

Given a random 3-uniform hypergraph $H=H(n,p)$ on $n$ vertices where each triple independently appears with probability $p$, consider the following graph process. We start with the star $G_0$ on the same vertex set, containing all the edges incident to some vertex $v_0$, and repeatedly add an edge $xy$ if there is a vertex $z$ such that $xz$ and $zy$ are already in the graph and $xzy\in H$. We say that the process propagates if it reaches the complete graph before it terminates. In this paper we prove that the threshold probability for propagation is $p=\frac{1}{2\sqrt{n}}$. We conclude that $p=\frac{1}{2\sqrt{n}}$ is an upper bound for the threshold probability that a random 2-dimensional simplicial complex is simply connected.