Reminder: This post contains 564 words
· 2 min read
· by Xianbin
Question: Is there a graph in which each edge is in an induced matching? And the density of the graph can be very large.
Answer: There is one. Ruzsa-Szemerédi graph!
We say that a graph is an (r,t)-Ruzsa-Szemerédi graph if its edge set can be partitioned into \(t\) induced matchings, each of size \(r\).
So, every edge is in the matching! Oh, that is amazing.
\(\textbf{Lemma}\). For infinitely many integer \(N\), there are \((r,t)\)-Ruzsa-Szemerédi Graph on \(N\) vertices, where \(r = N/e^{\sqrt{\log N}}\) and \(t = N/3\).
The lower bound of maximum edges is \(n/e^{O(\sqrt{\log n})}\). This means that the average degree is \(n/e^{O(\sqrt{\log n})}\) (very large).