Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
The authors resolve the asymptotic growth rate of the rainbow saturation number $rsat(n,F)$, establishing a sharp dichotomy governed strictly by whether the forbidden target graph $F$ contains an isolated edge. They prove that $rsat(n,F) = O(1)$ when $F$ contains an isolated edge, whereas $rsat(n,F) = \Theta(n)$ with a coefficient governed by a directed weight parameter $\eta(F)$ when no isolated edges exist. Leveraging these constructions, they establish asymptotically tight edge counts for generalized friendship graphs $F_{t,p,q}$, fixing their rainbow saturation at $(p+q-1)n + O(1)$.
A single isolated edge is all that separates linear edge complexity from constant-size collapse in rainbow graph saturation, resolving the asymptotic behavior across all target topologies.
Let $F$ be a fixed graph without isolated vertices. An edge-colored graph is $F$-rainbow saturated if it contains no rainbow copy of $F$, but the addition of any missing edge in any color creates a rainbow copy of $F$. The rainbow saturation number $rsat(n,F)$ is the minimum number of edges in such a graph on $n$ vertices. We prove a dichotomy governed by isolated edges: if $F$ contains an isolated edge, then $rsat(n,F)=O(1)$ for all sufficiently large $n$, while if $F$ has no isolated edge, then $rsat(n,F)=Θ(n)$. The linear lower bound is expressed in terms of a directed weight parameter $η(F)$ and establishes the linear half of the dichotomy; in several cases it also strengthens the Cameron--Puleo type coefficient. For the bounded half, we construct rainbow saturated graphs for targets of the form $H\cup K_2$. As an application of these constructions, we determine the asymptotically tight behavior for the rainbow saturation number of the generalized friendship graph $F_{t,p,q}=tK_p\vee K_q$, proving that $ rsat(n,F_{t,p,q})=(p+q-1)n+O(1)$ for fixed $t\geq 2$, $p\geq 2$ and $q\geq 1$ as $n\to\infty$.
Tsinghua AI