Independence number and the complexity of families of sets

DOI10.1016/0012-365X(94)00318-DzbMath0852.05076MaRDI QIDQ1918552

Daniel Q. Naiman, Henry P. Wynn

Publication date: 25 November 1996

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

complexityindependence numberset systemVapnik-Chervonenkis dimensioninclusion-exclusionqualitative independence

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Extremal set theory (05D05)

Related Items (3)

Independence number and the complexity of families of sets ⋮ Time and space complexity of deterministic and nondeterministic decision trees ⋮ Learning half-spaces on general infinite spaces equipped with a distance function

Cites Work

• Unnamed Item
• Unnamed Item
• A theorem on independence
• \(\epsilon\)-nets and simplex range queries
• Inclusion-exclusion-Bonferroni identities and inequalities for discrete tube-like problems via Euler characteristics
• Independent collections of translates of boxes and a conjecture due to Grünbaum
• Asymptotics via empirical processes. With comments and a rejoinder by the author
• Independence number and the complexity of families of sets
• On the density of families of sets
• A Note on Venn Diagrams
• Venn Diagrams and Independent Families of Sets
• Probability Inequalities for Sums of Bounded Random Variables
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Sur l'indépendance de domaines simples dans l'espace euclidien à n dimensions
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations

This page was built for publication: Independence number and the complexity of families of sets