Evasiveness conjecture and topological methods in graph theory I

Graph Theory Working Seminar
Tuesday, February 8, 2022 - 3:45pm for 1 hour (actually 50 minutes)
Skiles 005
James Anderson – Georgia Institute of Technology – janderson338@math.gatech.eduhttps://people.math.gatech.edu/~janderson338/
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.