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.