Given a finite simple graph \(G\), a set of vertices \(I\) is independent if every pair of vertices in \(I\) is non-adjacent in \(G\). The vector \((f_0,f_1,\ldots,f_n)\), where \(f_i\) is the number of independent sets in \(G\) with \(i+1\) vertices, is called the face vector of the independence complex of \(G\). Inspired by differential and algebraic topology, in the 1990's Robin Forman created discrete Morse theory, a purely combinatorial process that for independent sets in \(G\) involves matching pairs of independent sets according to certain rules. Discrete Morse theory has been used extensively in the study of complexes of independent sets in graphs, and this project will build on existing work. Specifically, we will be studying a different way to measure the number of independent sets in \(G\), using an average of vectors that are obtained using special classes of discrete Morse functions.
This project will have a strong experimental component, and we will use SageMath/Python to create and carry out computations. This project will also have a theoretical component, as we hope to prove theorems about our new ``face vector'' measurements for graphs such as paths, cycles, banana trees, caterpillars, and lobsters. (That's right! You read correctly! We will be doing research on banana trees, caterpillars, and lobsters!)
This project will have a strong experimental component, and we will use SageMath/Python to create and carry out computations. This project will also have a theoretical component, as we hope to prove theorems about our new ``face vector'' measurements for graphs such as paths, cycles, banana trees, caterpillars, and lobsters. (That's right! You read correctly! We will be doing research on banana trees, caterpillars, and lobsters!)
Comments
Post a Comment