Wednesday, April 04, 2012
- 06:00 pm
Topology Seminar and PhD Qualifying Exam, Brett Smith, Wes: Poset Dimension and Graph Coloring
Abstract: This talk will focus on work by Stefan Felsner and William T. Trotter characterizing the problem of finding the dimension of a poset. We will show this problem is is equivalent to a finding the chromatic number of a hypergraph associated to our poset. We then get a lower bound on dimension by looking at a subgraph (the graph of critical pairs) of this hypergraph. We hope to gain some insight into poset dimension by considering the question: Does there exist some function of the chromatic number of the graph of critical pairs that gives an upper bound on the dimension of a poset? We give a construction to show dimension can be large when the chromatic number is small; however, it is not known whether such a function exists.
Wednesday, May 11, 2011
- 03:00 pm
An introduction to model-theoretic forcing
Speaker: Brett Townsend, Wesleyan<br/><br/>Abstract: Starting in 1969, Abraham Robinson developed a technique of model-theoretic forcing inspired by the work of Paul Cohen in set theory. I will introduce the basics of Robinson9s forcing and explain some of its connections with more traditional model-theoretic topics like omitting types, model completeness, and categoricity.
Wednesday, November 17, 2010
- 06:00 pm
Graph Coloring and Immersions of Complete Graphs
Speaker: Megan Heenehan, Wesleyan University<br/><br/>Abstract: One of the interesting open questions in graph coloring is: if a graph is t-chromatic does it contain (in some way) a complete graph on t vertices? Attempts to solve this problem have included looking for subdivisions of complete graphs, minors of complete graphs, and immersions of complete graphs. This talk will focus on graph immersion. We say a graph H is immersed in a graph G if and only if there exists an injection from the vertices of H to the vertices of G for which the images of adjacent elements in H are connected in G by edge disjoint paths. In 2003 Abu-Khzam and Langston conjectured that if a graph G has chromatic number greater than or equal to t, then there is a complete graph on t vertices immersed in G. We will look at the progress that has been made towards proving this conjecture by considering the connectivity of t-immersion-critical graphs. We will also discuss why immersions may be the right approach to this problem.