T1: A Simple Question on Ruzsa-Szemerédi Graphs

September 06, 2024

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).