Institutional Scholarship

A General Framework for Proving Sauer-Shelah Type Lemmas

Show simple item record

dc.contributor.advisor Bhaskar, Siddharth Yutong, Li 2019-08-21T16:18:34Z 2019-08-21T16:18:34Z 2019
dc.description.abstract We present two versions of "shatter functions" and show that they are upper-bounded by the same polynomial, known as the Sauer-Shelah dichotomy. Then, we analyze a third setting due to Chase and Freitag [3], the $(n, k)$-banned binary sequence problems (BBSPs). Our purpose is to give an accessible exposition of their result and show that this is not only a generalization of both theorems, but also of both proofs. In particular, a new proof is obtained for the thicket case following this generalization.
dc.description.sponsorship Haverford College. Department of Computer Science
dc.language.iso eng
dc.subject.lcsh Combinatorial analysis
dc.title A General Framework for Proving Sauer-Shelah Type Lemmas
dc.type Thesis
dc.rights.access Dark Archive

Files in this item

This item appears in the following Collection(s)

Show simple item record Except where otherwise noted, this item's license is described as



My Account