Title: Dense clusters in hypergraphs
Speaker: Yuly Billig, Carleton University
Date: Friday, March 17, 2023
Time: 3:30 – 4:30 PM (coffee starting at 3:00)
Location: HP 4351 (MacPhail Room)
Abstract: Hypergraphs are generalizations of graphs where each edge joins an arbitrary number of vertices, and not just two as in the case of graphs. We define the density of a hypergraph as the ratio of the number of edges to the number of vertices. We solve the problem of finding in a given large hypergraph a subhypergraph with a maximum possible density. We introduce a notion of a support matrix A of a hypergraph and prove that the maximal density of a subhypergraph is equal to the largest eigenvalue of A*A^T for an optimal support matrix A. The methods that were developed for the proof of this theorem yield an efficient algorithmic solution of this problem. This topic is rather cross-disciplinary – in addition to graph theory, our results have applications in data science. The proofs, however, are based on linear algebra and linear optimization.