| 9:30 a.m. | Registration and Breakfast |
| 10:00 a.m. | Pallavi Jayawant: Discrete versions of topological theorems |
| 11:00 a.m. | Break |
| 11:30 a.m. | Martin Kochol: Counterexample to the conjecture of Grunbaum |
| 12:30 p.m. | Lunch |
| 2:00 p.m. | Joan Hutchinson: Color Extension Theorems for graphs with excluded minors. |
| 3:00 p.m. | Break |
| 3:15 p.m. | Mark Ellingham: Tricks with transition graphs |
| 4:15 p.m. | Break |
| 4:30 p.m. | Diane Souvaine: Points, Obstacles, Spanning-Trees, and Matchings |
Title: Tricks with transition graphs
Abstract: Transition graphs are an algebraic way of constructing embeddings of graphs in surfaces. They are equivalent to embedded voltage graphs but are more convenient in certain situations. We discuss how transition graphs can be used to construct embeddings of complete bipartite graphs with very specific properties. This allows us to construct minimum genus embeddings of complete tripartite graphs and other related graph families. We discuss some recent applications. (Joint work with Chris Stephens and Xiaoya Zha, Middle Tennessee State University)
Title: Color Extension Theorems for graphs with excluded minors.
Abstract: We build on a striking theorem of M.O. Albertson: Let P be a set of vertices of a graph G with chromatic number r. Then any (r+1)-coloring of P extends to an (r+1)-coloring of G provided the vertices of P are at mutual distance at least 4. In addition the parameters 4 and r+1 are best possible. There is a similar extension theorem [A, H, E.H. Moore] when bipartite subgraphs of G are each precolored with two colors, chosen from a set of r+2 colors, provided the bipartite subgraphs are suitably far apart. But more is true (meaning fewer colors are needed) when G is a planar graph or G is K5-minor-free or G is K4-minor free. By the Four Color Theorem and by proven cases of Hadwiger's Conjecture, we know that those classes of graphs can be 4-, 4-, and 3-colored respectively. Albertson's theorem gives us a color extension theorem when separated vertices are precolored, but what happens when bipartite subgraphs are precolored, each with two colors taken from a restricted set of colors? How large must the pool of colors be to allow for an extension, and how far apart must the bipartite components be? We'll survey results of A, H, M and recent work of A. Pruchnewski and M. Voigt, including results when list-colorings are considered.
Title: Discrete versions of topological theorems
Abstract: Tucker's Lemma is the discrete version of the Borsuk-Ulam theorem from topology about continuous functions on the sphere. Tucker's Lemma is a statement about labellings of triangulations of the sphere and it was proven in its full generality in 2006. Yang's theorem is a generalization of the Borsuk-Ulam theorem and Dyson's theorem is a special case of Yang's theorem about real valued functions on the sphere. I will discuss the Borsuk-Ulam theorem and Tucker's lemma and some of their applications. I will then present a combinatorial analog of Dyson's theorem and show the equivalence of the analog to Dyson's theorem. I will end with a discussion of possibilities to extend this work to obtain a discrete version of Yang's theorem. This is joint work with Peter Wong.
Title: Counterexample to the conjecture of Grunbaum
Abstract: By a classical result of Tait, the four color theorem is equivalent with the statement that each 2-edge-connected 3-regular planar graph has a 3-edge-coloring. An embedding of a graph in a surface is called polyhedral if its dual has no multiple edges and loops. A conjecture of Grunbaum, presented in 1968, states that each 3-regular graph with a polyhedral embedding in an orientable surface has a 3-edge-coloring. With respect to the result of Tait, it aims to generalize the four color theorem for any orientable surface. We present a negative solution of this conjecture, showing that for each orientable surface of genus at least 5, there exists a 3-regular non 3-edge-colorable graph with a polyhedral embedding in the surface.
Title: Points, Obstacles, Spanning-Trees, and Matchings
Abstract: Given m points (sites) and n obstacles (barriers) in the plane, what is the cost of the minimum spanning tree, where the cost is proportional to the number of intersections (crossings) between tree edges and barriers? A set of n disjoint line segments in the plane represents a matching of the m = 2n endpoints. Is there always a compatible (non-crossing) disjoint matching? We give some partial results, and discuss the role of convex partitions of the plane in tackling these and related problems.
Joint work with C. Aichholzer, N. Benbernou, S. Bereg, E. Demaine, M. Demaine, A. Dumitrescu, A. Garcia, M. Hoffmann, C. Huemer, F. Hurtado, M. Ishaque, M. Kano, D. Krumme, A. Marquez, D. Rappaport, E. Rafalin, S. Smorodinsky, C. Toth, J. Urrutia, and D. Wood.