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.