ACO Seminar - Maya Sankar
— 4:00pm
Location:
In Person
-
CNA Room, Wean Hall 7218
Speaker:
MAYA SANKAR
,
Institute for Advanced Study
https://mayasankar.github.io/
The discrete fundamental group pi1(G) of a graph G is an object inspired by the fundamental group of a topological space. I will define this group and present two results that use pi1(G) in very different ways. First, we show that no Cayley graph over (Z/2Z)m x (Z/4z)n can have chromatic number 3. Our proof is purely combinatorial yet generalizes the k=1 case of a pivotal result of Lovász, which states that a graph G has chromatic number at least k+3 if an associated topological space is k-connected.
Second, I will discuss an application to the homomorphism thresholds of odd cycles. For r ≥ 2, consider a family F of C2r+1-free graphs, each having minimum degree linear in its number of vertices. Such a family is known to have bounded chromatic number; equivalently, each graph in F is homomorphic to a complete graph of bounded size. We disprove the analogous statement for homomorphic images that are themselves C2r+1-free. The counterexample arises from a family of graphs on high-dimensional spheres, and the analysis relies on the discrete fundamental group in a crucial way.
—
Maya Sankar studies extremal graph theory, with a particular focus on connections to topological combinatorics. She aims to continue developing graph-theoretic analogues of tools from algebraic topology and identifying further applications for parameters that have already been introduced.
The first result is joint with Mike Krebs.
For More Information:
rkrueger@andrew.cmu.edu