Do you know anything about computing VC-dimension? Or about the Sauer-Shelah lemma?
Both Wikipedia and the CC blog state the lemma in a way that I do not understand. Namely, they define the VC-dimension as, at some point, determined by the cardinality of the intersection of the set {x1,…,xk} with some other set. And both sources upper bound this number by 2k, which seems absurd: how can it possibly be more than k? We have indexed the set; it has exactly k elements; set intersection is a strictly nonincreasing function in terms of set size.
It also seems unlikely to me that both these sources would have typos. So I must be misunderstanding something.
If you know something about VC-dimension, the Sauer-Shelah lemma, or related combinatorics, please send me an email and I shall grill you with my questions (seasoned with confusion... and paprika, if you like).
Update: I figured it out with the help of these lecture notes. It was an issue of misunderstood notation. (My bad, as usual.)
This post's theme word: curtilage, "an area of land encompassing a dwelling and its surrounding yard, considered as enclosed whether fenced or not." In my present frame of mind, it relates to set theory.
No comments:
Post a Comment