Nearly complete graphs decomposable into large induced matchings and their applications (Q363228)

Two constructions are presented of dense graphs which are edge-disjoint unions of large induced matchings. More specifically, the first construction exhibits a graph \(G\) on \(N\) vertices such that for any \(\epsilon > 0\) the number of missing edges is at most \(N^{2 - \delta}\) for \(\delta = e^{-O(1/\epsilon)}\) and such that the edges can be covered by \(N^{1 + \epsilon}\) pairwise disjoint induced matchings. The second construction describes for any \(\epsilon > 0\) a graph \(G\) on \(N\) vertices missing at most \(N^{3/2 + \epsilon}\) edges that can be be covered by \(N^{2-c\epsilon^3}\) induced matchings for an appropriate \(c\). In the case of each of the constructions more detailed statements are made about the constants in the statements of the theorems in the paper. Lower bounds are also proved on the number of edges that must be missing for a graph to be covered by disjoint induced matchings of a given size. Several applications of dense graphs with edges covered with pairwise disjoint induced matchings are presented -- in particular to communication networks with shared communication channels, and to linearity testing of graphs. There is a fairly extensive bibliography covering the application possibilities.