One-inclusion hypergraph density revisited

DOI10.1016/J.IPL.2010.03.002zbMATH Open1197.68063OpenAlexW2054166359MaRDI QIDQ991799FDOQ991799

Authors: Hans Ulrich Simon, Balázs Szörényi 

Publication date: 7 September 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2010.03.002

Recommendations

• On density of subgraphs of halved cubes
• Shifting: one-inclusion mistake bounds and sample compression
• Corrigendum to ``Shifting: One-inclusion mistake bounds and sample compression
• The one-inclusion graph algorithm is near-optimal for the prediction model of learning
• Density and dimension

zbMATH Keywords

combinatorial problemspseudo-dimensionmistake boundgraph-dimensionone-inclusion hypergraph

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Computational learning theory (68Q32) Hypergraphs (05C65)

Cites Work

• On the density of families of sets
• Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension
• A generalization of Sauer's lemma
• Shifting: one-inclusion mistake bounds and sample compression

Cited In (2)

• A lower bound for families of Natarajan dimension \(d\)
• On density of subgraphs of halved cubes

This page was built for publication: One-inclusion hypergraph density revisited

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q991799)