## Algebra and Combinatorics Seminar

**Date:** November 8, 2019

**Time:** 3:00PM - 3:50PM

**Location:** BLOC 628

**Speaker:** Peter Stiller, Texas A&M University

**Title:** *Edge Erasures and Chordal Graphs with Applications to Data Clustering*

**Abstract:** We prove several results about chordal graphs and weighted chordal graphs by focusing on exposed edges. These are edges that are properly contained in a single maximal complete subgraph. This leads to a characterization of chordal graphs via deletions of a sequence of exposed edges from a complete graph. Most interesting is that in this context the connected components of the edge-induced subgraph of exposed edges are 2-edge connected. We use this latter fact in the weighted case to give a modified version of Kruskalâ€™s second algorithm for finding a minimum spanning tree in a weighted chordal graph. This modified algorithm benefits from being local in an important sense. In recent work with Culbertson, Dochtermann and Guralnik these results have been generalized, leading to a new result on Simon's conjecture concerning the extendable shellability of certain complexes.