One-inclusion hypergraph density revisited

DOI10.1016/J.IPL.2010.03.002MaRDI QIDQ991799zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

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)