Mathematics and Statistics Colloquium
Dense clusters in hypergraphs
Date: Friday, Jan. 12
Time: 3:30 pm
Location: Arts Building Room 206, 9 Campus Dr., Saskatoon
Free and open to the public
About this event
A talk by professor Yuly Billig, of Carleton University, hosted by the USask Department of Mathematics and Statistics
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 advance the density theory for hypergraphs, establishing new results on maximum density subhypergraphs. We introduce the 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 algorithm for finding a maximum density subhypergraph. 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.
Info: colloquium@math.usask.ca
Related Articles
USask student challenging perception of dinosaurs with ‘paleoart’
USask geological sciences graduate student Kaitlin “KT” Lindblad reimagines some of the world’s best-known dinosaurs with artwork