A General Framework for Proving Sauer-Shelah Type Lemmas
Date
2019
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Producer
Director
Performer
Choreographer
Costume Designer
Music
Videographer
Lighting Designer
Set Designer
Crew Member
Funder
Rehearsal Director
Concert Coordinator
Advisor
Moderator
Panelist
Alternative Title
Department
Haverford College. Department of Computer Science
Type
Thesis
Original Format
Running Time
File Format
Place of Publication
Date Span
Copyright Date
Award
Language
eng
Note
Table of Contents
Terms of Use
Rights Holder
Access Restrictions
Dark Archive
Terms of Use
Tripod URL
Identifier
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.