Topics in Combinatorics
MATH 507
Spring 2025
| Section:
01
|
| This course may be repeated for credit. |
A graph is a set of vertices with an accompanying set of pairs of vertices, called edges. Given a set of searchers, a vertex search is a series of steps in which a searcher is either placed on or removed from a vertex in the graph. When both incident vertices of an edge simultaneously contain a searcher, then the edge is said to be cleared. The question of what is the minimum number of searchers needed to clear a graph is related to deep theorems of the structure of graphs, such as theorems about the pathwidth and treewidth of graphs. Graph searching and its variants are related to the game of Cops and Robbers (also called the pursuit-and-evasion game) which has applications in many areas, including robot movements and network security. A partially ordered set (poset) is a set with an order relation that is reflexive and transitive. Finite posets are used as finite models for topological spaces, which can describe large data sets. We will study both their topological and algebraic properties, including the Moebius and zeta functions, R-labelings, shellable labelings, lexicographically shellable labelings, and their homology. Special cases of posets such as Cohen-Macaulay posets, lattices, and modular and distributive lattices will be important examples. These topics are being used in current work in topological data science. |
|
| Credit: 1 |
Gen Ed Area Dept:
None |
| Course Format: Lecture | Grading Mode: Graded |
| Level: GRAD |
Prerequisites: None |
|
Fulfills a Requirement for: None |
|
Past Enrollment Probability: 90% or above |
|
|
|