Title: Dense clusters in hypergraphs
\nSpeaker: Yuly Billig, Carleton University
\nDate: Friday, March 17, 2023
\nTime: 3:30 – 4:30 PM (coffee starting at 3:00)
\nLocation: HP 4351 (MacPhail Room)<\/p>\n
Abstract: Hypergraphs are generalizations of graphs where each edge\u00a0 joins an arbitrary number of vertices, and not just two as in the case\u00a0 of graphs. We define the density of a hypergraph as the ratio of the\u00a0 number of edges to the number of vertices. We solve the problem of\u00a0 finding in a given large hypergraph a subhypergraph with a maximum\u00a0 possible density. We introduce a notion of a support matrix A of a\u00a0 hypergraph and prove that the maximal density of a subhypergraph is\u00a0 equal to the largest eigenvalue of A*A^T for an optimal support matrix\u00a0 A. The methods that were developed for the proof of this theorem yield\u00a0 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.<\/p>\n
<\/p>\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
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\u00a0 joins an arbitrary number of vertices, and not just two as in the case\u00a0 of graphs. We […]<\/p>\n","protected":false},"author":44,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_relevanssi_hide_post":"","_relevanssi_hide_content":"","_relevanssi_pin_for_all":"","_relevanssi_pin_keywords":"","_relevanssi_unpin_keywords":"","_relevanssi_related_keywords":"","_relevanssi_related_include_ids":"","_relevanssi_related_exclude_ids":"","_relevanssi_related_no_append":"","_relevanssi_related_not_related":"","_relevanssi_related_posts":"","_relevanssi_noindex_reason":"","_mi_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":"","_links_to":"","_links_to_target":""},"categories":[14,1],"tags":[],"yoast_head":"\n