Coverings of Complete Graphs by Small Cliques and Applications

Abstract: When solving partial differential equations by fast Boundary Element Methods, one is naturally led to large dense matrices whose computation must be split into many smaller pieces for parallel execution on multiple cores. This motivates a combinatorial load-balancing problem that can be modelled by covering the edges of a complete graph with small cliques, each representing a computational task. In this talk, I will discuss recent results on such coverings of complete graphs by cliques of small order. The problem is closely related to classical questions in design theory, but is also driven by applications. If several clique sizes are permitted, then minimising the number of blocks alone does not adequately describe the quality of a covering. We therefore study a refined criterion involving both the block count and the excess, namely the number of edges covered more than once. I will present sharp results for coverings with 3- and 4-cliques, and then turn to the more difficult setting where 5-cliques are also allowed, including some open cases. More broadly, the talk illustrates how abstract combinatorial structures can arise from concrete computational challenges, and how their study can feed back into the design of efficient parallel algorithms.

numerical analysisoptimization and control

Audience: researchers in the topic

( paper )

CAM seminar

Series comments: Online streaming via zoom on exceptional cases if requested. Please contact the organizers at the latest Monday 11:45.