Monday, September 11 2017
11:00am - 12:15am
Discrete Mathematics Seminar
Discrete Math Seminar: AMS Sectional Talks

Eric Sullivan and Nathan Graber will present their talks for the upcoming AMS Sectional meeting in Buffalo.

The minimum Size of Induced-saturated Posets
Eric Sullivan

Given a poset \mathcal P, a family \mathcal F of points in the Boolean lattice is said to be \mathcal P-saturated if (1) \mathcal F contains no copy of \mathcal P as a subposet and (2) every strict superset of \mathcal F contains a copy of \mathcal P as a subposet. The maximum size of a \mathcal P-saturated subposet is denoted by La(n,\mathcal P), which has been studied for a number of choices of \mathcal P.  

Here, we are interested in sat(n,\mathcal P), the size of the smallest family in \mathcal B_n which is \mathcal P-saturated.  This notion was introduced by Gerbner et al. (2013), and parallels the deep literature on the saturation function for graphs.  

In particular, we introduce and study the concept of saturation for induced subposets.  As opposed to induced saturation in graphs, the above definition of saturation for posets extends naturally to the induced setting.  We give several exact results and a number of bounds on the induced saturation number for several small posets.  We also use a transformation to the biclique cover problem to prove a logarithmic lower bound for a rich infinite family of target posets.

Berge-saturated Hypergraphs of Minimum Size
Nathan Graber

Let H be a hypergraph, and G be a simple graph on the same vertex set. We say H is Berge-G if there exists a bijection, f, from E(G) to E(H) such that for each e in E(G), we have e in f(e). If there exists a subhypergraph of H that is Berge-G we say that H contains G, otherwise H is said to be G-free. A

hypergraph, H, is Berge-G-saturated if H does not contain G but H + e contains G for every edge not in
E(H). The Berge-saturation number, denoted B-sat(H,G), is the minimum number of edges in a hypergraph, H, such
that H is G-saturated.

In this talk we will discuss the Berge-saturation number for several classes of graphs and draw comparisons between Berge-saturation and saturation in the traditional graph sense.
Speaker:Nathan Graber and Eric Sullivan
Affiliation:Deaprtment of Mathematical and Statistical Sciences
Location:Student Commons 4119


Download as iCalendar

Done