𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A graph-theoretic generalization of the Sauer-Shelah lemma

✍ Scribed by Nicolò Cesa-Bianchi; David Haussler

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
622 KB
Volume
86
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

We show a natural graph-theoretic generalization of the Sauer-Shelah lemma. This result is applied to bound the & and L1 packing numbers of classes of functions whose range is an arbitrary, totally bounded metric space.

📜 SIMILAR VOLUMES

Remarks on the cofinality of a partially
Remarks on the cofinality of a partially ordered set, and a generalization of König's lemma
✍ E.C. Milner; N. Sauer 📂 Article 📅 1981 🏛 Elsevier Science 🌐 English ⚖ 694 KB

A problem concerning the cardinality of the cofinal subsets of a partially ordered set is reduced to an open problem irr graph tteory. Let A be an in&it: wdinal, V = Ui,, Vi, I Uiii VJC IVJ (i CA). J\_et G be a graph on V with the proper?y that whenever i <A, x=u ie,cA Vi and IXICIVil, then there is

On a Lemma of Gromov and the Entropy of
On a Lemma of Gromov and the Entropy of a Graph
✍ Fabio Scarabotti 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 42 KB

If G is a finite, directed, simple and irreducible graph, deletion of an edge makes the entropy decrease. We give a proof of this fact that avoids the Perron-Frobenius theorem and makes use of a technique developed by Gromov.