The well-known Ruzsa-Szemeredi Theorem states that a graph whose edges can be partitioned into $n$ induced matchings has at most $\frac{n^2}{RS(n)}$ edges, for some slow-growing function $RS(n)$.

Now, suppose we have a graph $G$ whose edges can be partitioned into *nearly* induced matchings: in particular, for any distinct edges $(u, v), (x, y)$ in a partition, at most one of the edges $(u, x), (u, y), (v, x), (v, y)$ may exist in $G$.

Can we still say that $G$ contains only $O(\frac{n^2}{RS(n)})$ edges? If so, is it possible to show this using the Ruzsa-Szemeredi Theorem in a black box manner, or is it necessary to appeal to the Szemeredi Regularity Lemma or the other usual machinery for these problems?

(response to a comment below)

Yes, the Induced Matching Lemma was first proved by R+S in the paper "Triple systems with no six points carrying three triangles." They proved something equivalent to the Induced Matching Lemma stated in very different language.

Basically, there's an equivalence between dense graphs that can be partitioned into $n$ induced matchings, and dense graphs in which every edge belongs to exactly one triangle (which is the problem studied in the R+S paper). To see this, take a (bipartite) graph whose edges can be partitioned into $M_1, \dots, M_n$ induced matchings, and add a new node $m_1, \dots, m_n$ for each matching. Connect the node $m_i$ to all endpoints of edges in $M_i$. You can now verify that any edge $(u, v)$ in matching $M_i$ participates in exactly one triangle, with endpoints $(u, v, m_i)$. The reduction in the other direction is very morally similar.

So the Induced Matching Lemma is equivalent to the claim that any graph in which all edges participate in exactly one triangle has $o(n^2)$ edges. Modern proofs of this fact typically use the Triangle Removal Lemma. It's easy to prove this statement from the Triangle Removal Lemma, although the TRL itself is very nontrivial. So if you're interested in a proof of the Induced Matching Lemma, I'd suggest googling around for Triangle Removal rather than looking for the original R+S paper.

Finally, to answer your last question: no, the $o(n^2)$ in the induced matching lemma can't be improved to $o(n^{2 - \varepsilon})$. One can construct graphs on $n^{2} / 2^{c \sqrt{\log n}}$ edges that can be decomposed into $n$ induced matchings, using constructions of very dense progression-free sets of integers (see Behrend). If $A \subseteq [n]$ is a set of integers with no three-term arithmetic progression, then we build a tripartite graph with vertex sets $X, Y, Z$, with the nodes in each part labelled from $1$ to $3n$. Then we add an edge from $x \in X$ to $(x+a) \in Y$ for each $x \in X, a \in A$. Similarly, we add an edge from $y \in Y$ to $(y+a) \in Z$ for each $y \in Y, a \in A$. Finally, we add an edge from $x \in X$ to $(x+2a) \in Z$ for each $x \in X, a \in A$. You can now check that each edge $(x, x+a)$ participates in the unique triangle $(x, x+a, x+2a)$, due to the condition that $A$ is a progression-free set.

Hope that helps! Feel free to keep asking, I'm just learning this stuff myself and I find it really interesting.