tag:blogger.com,1999:blog-3722233.post113931870357382037..comments2019-11-13T19:17:31.866-05:00Comments on Computational Complexity: Sauer's LemmaLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-1141878345775386032006-03-08T23:25:00.000-05:002006-03-08T23:25:00.000-05:00The following work by Pollard has an unconventiona...The following work by Pollard has an unconventional proof of Sauer's lemma. It is highly informal. I am not sure it is correct.<BR/><BR/>www.stat.yale.edu/~pollard/Asymptopia/Combinatorics.pdfsevenfactorialhttps://www.blogger.com/profile/15282594159814479813noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1139389035901002582006-02-08T03:57:00.000-05:002006-02-08T03:57:00.000-05:00The lemma can also be elegantly proven using shift...The lemma can also be elegantly proven using shifting. See the proof of Lemma 2 of Haussler's 1995 paper <A HREF="ftp://ftp.cse.ucsc.edu/pub/ml/sphere.pkg.ps" REL="nofollow">Sphere packing numbers for subsets of the boolean n-cube with bounded Vapnik-Chervonenkis dimension</A>.Ben Rubinsteinhttp://www.cs.berkeley.edu/~benrnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1139338552746808292006-02-07T13:55:00.000-05:002006-02-07T13:55:00.000-05:00A non inductive proof is contained in the book "Co...A non inductive proof is contained in the book "Combinatorics", by Bollobas (along with several other proofs).<BR/><BR/>BTW, I am not completely sure that Vapnik and Chervonenkis proved exactly the same result. According to the book by Alon and Spencer "The Probabilistic Method", they proved a slightly weaker result. In the combinatorics literature, the result is generally credited to Sauer and Perles and Shelah.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1139332527941346032006-02-07T12:15:00.000-05:002006-02-07T12:15:00.000-05:00I think the proper additional reference from the f...I think the proper additional reference from the first comment is to Perles & Shelah. That is the first reference I saw to it.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1139330429210221732006-02-07T11:40:00.000-05:002006-02-07T11:40:00.000-05:00Its also known as the primal shatter lemma.I disli...Its also known as the primal shatter lemma.<BR/><BR/>I dislike the inductive proof given in all the books though. It seems there should be a more direct "charging" proof: sets smaller than k are ok, while the larger sets could be charged to the smaller sets not present.<BR/><BR/>Does anyone know of a more revealing proof, than the one by induction? I recall the excellent book "combinatorial geometry" (agarwal&pach) had a linear-algebra method proof of this as well.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1139322150947837982006-02-07T09:22:00.000-05:002006-02-07T09:22:00.000-05:00It was also rediscovered by Selach, at least accor...It was also rediscovered by Selach, at least according to the book "The probablistic method". The proof is short and elegant, BTW.Anonymousnoreply@blogger.com