***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Maya Sankar (IAS)

Thursday 23rd October, 3:00 in Fine Hall 224.

Title: The Discrete Fundamental Group

The discrete fundamental group pi_1(G) of a graph G is an object inspired 
by the fundamental group of a topological space. I will present two results 
that use pi_1(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 C_{2r+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 $C_{2r+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.

The first result is joint with Mike Krebs.

		----------------------------------

Anyone wishing to be added to or removed from the mailing list should
contact Paul Seymour (pds@math.princeton.edu)