𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A Lower Bound for Families of Natarajan Dimension d

✍ Scribed by Paul Fischer; Jiřı́ Matoušek

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
98 KB
Volume
95
Category
Article
ISSN
0097-3165

No coin nor oath required. For personal study only.

✦ Synopsis

A system F of functions [1, 2, ..., n] Ä [1, 2, ..., k] has Natarajan dimension at most d if no (d+1)-element subset A/X is 2-shattered. A is 2-shattered if for each x # A there is a 2-element set V x [1, 2, ..., k] such that for any choice of elements c x # V x , a function f # F exists with f (x)=c x for all x # A. We improve a lower bound of c d k d n d (due to Haussler and Long) for the maximum size of F of Natarajan dimension at most d by a factor somewhat smaller than k (e.g., byk for d=1). The problem of obtaining a tight bound is related to interesting questions in extremal graph theory.

📜 SIMILAR VOLUMES

Lower bounds for the immersion dimension
Lower bounds for the immersion dimension of homogeneous spaces
✍ Markus Walgenbach 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 165 KB

The object of the present work is to express characteristic numbers of a homogeneous space G/U which are related to the immersion dimension of G/U by Lie group invariants of G and U . New concrete nonimmersion theorems for flag manifolds and other homogeneous spaces are proved.

A lower bound for the circumference of a
A lower bound for the circumference of a graph
✍ Nathan Linial 📂 Article 📅 1976 🏛 Elsevier Science 🌐 English ⚖ 423 KB

Lrzt G = (V, 0 be a ttlock :.>f order n, different from Kn. Let ~FI = min {d(x) + d(y): n then G contains a cycle of length at least m. 1. Introductlion and notatio e discuss only finite undirected graphs withsLc loops and multiple edges. We p:rosye the main theorem d show how Qre's th -orem [ 3.1 o