✦ LIBER ✦

Tight bounds on the maximum size of a set of permutations with bounded VC-dimension

✍ Scribed by Josef Cibulka; Jan Kynčl

Book ID: 113698864
Publisher: Elsevier Science
Year: 2012
Tongue: English
Weight: 295 KB
Volume: 119
Category: Article
ISSN: 0097-3165
DOI: 10.1016/j.jcta.2012.04.004

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Tight Lower Bounds on the Size of a Maxi

Tight Lower Bounds on the Size of a Maximum Matching in a Regular Graph

✍ Michael A. Henning; Anders Yeo 📂 Article 📅 2007 🏛 Springer Japan 🌐 English ⚖ 106 KB

Bounding the maximum size of a minimal d

Bounding the maximum size of a minimal definitive set of quartets

✍ Max Dietrich; Catherine McCartin; Charles Semple 📂 Article 📅 2012 🏛 Elsevier Science 🌐 English ⚖ 177 KB

A Polynomial Lower Bound on the Size of

A Polynomial Lower Bound on the Size of ak-Min-Wise Independent Set of Permutations

✍ S. A. Norin 📂 Article 📅 2003 🏛 Springer US 🌐 English ⚖ 138 KB

A tight lower bound on the size of visib

A tight lower bound on the size of visibility graphs

✍ Xiaojun Shen; Herbert Edelsbrunner 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 451 KB

A tight lower bound on the maximum genus

A tight lower bound on the maximum genus of a simplicial graph

✍ Jianer Chen; Saroja P. Kanchi; Jonathan L. Gross 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 856 KB

It is proved that every connected simplicial graph with minimum valence at least three has maximum genus at least one-quarter of its cycle rank. This follows from the technical result that every 3-regular simplicial graph except K4 has a Xuong co-tree whose odd components have only one edge each. It

A Tight Bound on the Number of Geometric

A Tight Bound on the Number of Geometric Permutations of Convex Fat Objects inRd

✍ M. J. Katz; K. R. Varadarajan 📂 Article 📅 2001 🏛 Springer 🌐 English ⚖ 92 KB