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.

  • $\begingroup$ Would you please tell me the source of the Ruzsa-Szemeredi Theorem you mentioned above? $\endgroup$ – user173856 Jun 30 '16 at 7:22
  • $\begingroup$ I don't know if you can guarantee $o(n^2)$ edges, but to me, your definition of "nearly induced" doesn't seem all that amenable to the regularity lemma. If you changed your definition of "nearly induced" to something like $|E(G[M])-M| = O(1)$ for each matching $M$ that composes $G$, then the standard proof of Ruzsa-Szemeredi that uses the regularity lemma should go through no problem. $\endgroup$ – Nathan Lindzey Jun 30 '16 at 8:37
  • $\begingroup$ @user173856 This survey has it covered pretty well: arxiv.org/pdf/1211.3487.pdf, see footnote at the bottom of page 1, or [93]. $\endgroup$ – GMB Jun 30 '16 at 8:52
  • $\begingroup$ GMB: You mean the induced matching theorem mentioned in the footnote at the bottom of page 1, right? Do you know any sourse where I can see the proof of it? Thank you! $\endgroup$ – user173856 Jul 1 '16 at 14:50
  • $\begingroup$ @user173856 yep, that's what I mean. These lecture notes have a proof: math.mit.edu/~cb_lee/18.318/lecture3.pdf (see thm 20, prior stuff is mostly a proof of the Szemeredi Regularity Lemma). An exponentially better bound was implied by Fox math.mit.edu/~fox/paper-removal.pdf; there is a simple reduction from induced matchings to dense graphs in which each edge participates in exactly one triangle, and Fox's paper implies that any such graph can't be too dense. $\endgroup$ – GMB Jul 1 '16 at 21:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.