Mathematics & Computer Science

Seminars and Colloquia

Ph.D. Qualifying Exam

Wednesday, April 04, 2012

04:15 pm - 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.

ESC 638