Please join the Department of Mathematics and Statistics on Monday, September 13th at 4:40pm in Votey Hall 209 for a fascinating combinatorics seminar featuring Mathematics Graduate Student, Calum Buchanan.
Graphs and Symmetric Differences of Edge Sets
Calum Buchanan, University of Vermont
Monday, September 13th, 4:40 PM, Votey Hall 209
Abstract: A graph is a finite set of points, or vertices, along with a set of edges joining some pairs of distinct vertices. Graphs can be used to model a wide variety of problems, leading to many questions about the graphs themselves. One common question is: how can we efficiently express a graph G? This talk will focus on a combinatorial way of doing so, using cliques, or sets of vertices with edges between each pair, to express G. In particular, we would like to minimize the size of a collection of cliques on subsets of the vertices of G in which two vertices are contained in an odd number of cliques together if and only if they are joined by an edge in G. In other words, the edge set of G is the symmetric difference of the edge sets of the cliques in our collection. This problem is closely related to an algebraic optimization problem involving graphs, called the minimum rank problem. We will explore this relationship via examples and show that certain properties of such a minimum collection of cliques provide information about the minimum rank of G, and vice-versa.