Monday, September 11 2017

11:00am - 12:15am

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.

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 |

Done