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.

We investigate adaptive sublinear algorithms for detecting monotone patterns in an array. Given fixed $2 \leq k \in \mathbb{N}$ and $\varepsilon > 0$, consider the problem of finding a length-$k$ increasing subsequence in an array $f \colon [n] \to \mathbb{R}$, provided that $f$ is $\varepsilon$-far from free of such subsequences. Recently, it was shown that the non-adaptive query complexity of the above task is $Θ((\log n)^{\lfloor \log_2 k \rfloor})$. In this work, we break the non-adaptive lower bound, presenting an adaptive algorithm for this problem which makes $O(\log n)$ queries. This is optimal, matching the classical $Ω(\log n)$ adaptive lower bound by Fischer [2004] for monotonicity testing (which corresponds to the case $k=2$), and implying in particular that the query complexity of testing whether the longest increasing subsequence (LIS) has constant length is $Θ(\log n)$.

For two graphs $G$ and $H$, write $G \stackrel{\mathrm{rbw}}{\longrightarrow} H$ if $G$ has the property that every proper coloring of its edges yields a rainbow copy of $H$. We study the thresholds for such so-called anti-Ramsey properties in randomly perturbed dense graphs, which are unions of the form $G \cup \mathbb{G}(n,p)$, where $G$ is an $n$-vertex graph with edge-density at least $d$, and $d$ is a constant that does not depend on $n$. Our results in this paper, combined with our results in a companion paper, determine the threshold for the property $G \cup \mathbb{G}(n,p) \stackrel{\mathrm{rbw}}{\longrightarrow} K_s$ for every $s$. In this paper, we show that for $s \geq 9$ the threshold is $n^{-1/m_2(K_{\left\lceil s/2 \right\rceil})}$; in fact, our $1$-statement is a supersaturation result. This turns out to (almost) be the threshold for $s=8$ as well, but for every $4 \leq s \leq 7$, the threshold is lower; see our companion paper for more details. Also in this paper, we determine that the threshold for the property $G \cup \mathbb{G}(n,p) \stackrel{\mathrm{rbw}}{\longrightarrow} C_{2\ell - 1}$ is $n^{-2}$ for every $\ell \geq 2$; in particular, the threshold does not depend on the length of the cycle $C_{2\ell - 1}$. For even cycles, and in fact any fixed bipartite graph, no random edges are needed at all; that is, $G \stackrel{\mathrm{rbw}}{\longrightarrow} H$ always holds, whenever $G$ is as above and $H$ is bipartite.

We study the problem of finding monotone subsequences in an array from the viewpoint of sublinear algorithms. For fixed k ϵ N and ε > 0, we show that the non-adaptive query complexity of finding a length-k monotone subsequence of f : [n] → R, assuming that f is ε-far from free of such subsequences, is Θ((log n)⌊log_2k⌋). Prior to our work, the best algorithm for this problem, due to Newman, Rabinovich, Rajendraprasad, and Sohler (2017), made (log n)O(k2)non-adaptive queries; and the only lower bound known, of Ω(log n) queries for the case k = 2, followed from that on testing monotonicity due to Ergün, Kannan, Kumar, Rubinfeld, and Viswanathan (2000) and Fischer (2004).

For graphs $H$ and $F$, let ${ex}(n, H, F)$ be the maximum possible number of copies of $H$ in an $F$-free graph on $n$ vertices. The study of this function, which generalizes the well-studied Turán numbers of graphs, was initiated recently by Alon and Shikhelman. We show that if $F$ is a tree, then ${ex}(n, H, F) = \Theta(n^r)$ for an (explicit) integer $r = r(H, F)$, thus answering one of their questions.