- Series
- Graph Theory Working Seminar
- Time
- Tuesday, February 8, 2022 - 3:45pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- James Anderson – Georgia Institute of Technology – janderson338@math.gatech.edu – https://people.math.gatech.edu/~janderson338/
- Organizer
- Anton Bernshteyn
In the first talk of this seminar series, we follow the manuscript of Carl Miller and introduce the concept of elusive graph properties—those properties for which any edge-querying algorithm requires all possible queries in the worst case. Karp conjectured in 1973 that all nontrivial monotonic graph properties are elusive, and a celebrated theorem by Kahn in 1984 used topological fixed-point methods to show the conjecture is true in the case of graphs with order equal to a prime power. To set the stage for the proof of this result in later talks, we introduce monotone graph properties and their connection to collapsible simplicial complexes.