Skip to content
Texas A&M University
Mathematics

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.