IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Local dimension and the size of a poset

  • Nov. 17, 2017
  • 2:30 p.m.
  • LeConte 310

Abstract

The original notion of poset dimension is due to Dushnik and Miller (1941). Last year, Uerckerdt (2016) proposed a variant, called local dimension, which has garnered considerable interest. A local realizer of a poset P is a collection of partial linear extensions of P that cover the comparabilities and incomparabilities of P. The local dimension of P is the minimum frequency of a local realizer where frequency is the maximum multiplicity of an element of P.

Hiraguchi (1955) proved that any poset with n points has dimension at most n/2, which is sharp. We prove that the local dimension of a poset with n points is O(n/log n). To show that this bound is best possible, we use probabilistic methods to prove the following stronger result which extends a theorem of Chung, Erdős, and Spencer (1983): There is an n-vertex bipartite graph in which each difference graph cover of the edges will cover one of the vertices Θ(n/log n) times. (This is joint work with Jinha Kim, Ryan R. Martin, Tomáš Masařı́k, Warren Shull, Andrew Uzzell, and Zhiyu Wang)

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC