On graphs decomposable into induced matchings of linear sizes

We call a graph G an ( r , t ) ‐Ruzsa–Szemerédi graph if its edge set can be partitioned into t edge‐disjoint induced matchings, each of size r . These graphs were introduced in 1978 and have been extensively studied since then. In this paper, we consider the case when r = c n . For c > 1 / 4 , we determine the maximum possible t , which is a constant depending only on c . On the other hand, when c = 1 / 4 , there could be as many as Ω ( log n ) induced matchings. We prove that this bound is tight up to a constant factor. Finally, when c is fixed strictly between 1 / 5 and 1 / 4 , we give a short proof that the number t of induced matchings is O ( n / log n ) . We are also able to further improve the upper bound to o ( n / log n ) for fixed c > 1 / 4 − b for some positive constant b .