Theory Seminar

Nearly complete graphs decomposable into large induced matchings and their applications

Shang-En Huang

We describe two constructions of (very) dense graphs which are edge disjoint unions of large induced matchings. The first construction exhibits graphs on N vertices with (N choose 2) - o(N^2) edges, which can be decomposed into pairwise disjoint induced matchings, each of size N^{1Â^’o(1)}. The second construction provides a covering of all edges of the complete graph K_N by two graphs, each being the edge disjoint union of at most N^{2Â^’Î&rquo;} induced matchings, where Î&rquo; > 0.076.

Sponsored by

Theory Group

Faculty Host

Seth Pettie