IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Saturation for Induced Subsets

  • Nov. 4, 2016
  • 2:30 p.m.
  • LeConte 312

Abstract

Graph saturation was first introduced in 1964 by Erdos, Hajnal, and Moon. The notion of saturation can be extended to posets as follows: Fix a target poset P. A family F of points in the Boolean lattice is called (induced)-P-saturated if (1) F contains no copy of P as an (induced) subposet and (2) every strict superset of F contains a copy of P as an (induced) subposet. For each n, the (induced) saturation number for P is the size of the smallest family in B_n which is (induced)-P-saturated.

Gerbner et. al. (2013) first studied the notion of saturation for the chain being the target poset where the saturation number and the induced saturation number are identical. We turn our attention to induced saturation, determining bounds on this value for several small posets in addition to proving a logarithmic lower bound for target posets from an infinite family. This is joint work with Michael Ferrara, Bill Kay, Lucas Kramer, Ryan Martin, Benjamin Reiniger, and Eric Sullivan.

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