Abstract. Given a graph [Formula: see text], we say that an edge-colored graph [Formula: see text] is [Formula: see text]-rainbow saturated if it does not contain a rainbow copy of [Formula: see text], but the addition of any nonedge in any color creates a rainbow copy of [Formula: see text]. The rainbow saturation number [Formula: see text] is the minimum number of edges among all [Formula: see text]-rainbow saturated edge-colored graphs on [Formula: see text] vertices. We prove that for any nonempty graph [Formula: see text], the rainbow saturation number is linear in [Formula: see text], thus proving a conjecture of Girão, Lewis, and Popielarz. In addition, we give an improved upper bound on the rainbow saturation number of the complete graph, disproving a second conjecture of Girão, Lewis, and Popielarz.

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.