Independence number and the complexity of families of sets

DOI10.1016/0012-365X(94)00318-DMaRDI QIDQ1918552zbMATH OpenFDO

Authors Daniel Q. Naiman, Henry P. Wynn

Publication date 25 November 1996

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(94)00318-D

zbMATH Keywords

complexityinclusion-exclusionindependence numberqualitative independenceset systemVapnik-Chervonenkis dimension

Mathematics Subject Classification ID

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

Review text

The independence number \(m({\mathcal C})\) of a set system \(\mathcal C\) is the cardinality of its maximum qualitative independent subsystem. This notion is in close connection to the well-known Vapnik-Chervonenkis dimension. The authors dedicated several research articles to this topic. This particular paper delivers general upper bounds on \(m({\mathcal C})\) and proves inequalities between the independence number and the Vapnik-Chervonenkis dimension, in both directions. It also turns out that for special cases the two quantities are equal.

Recommendations

• Some results on the complexity of families of sets
• A generalization of the independence number
• On the number of independent sets in expanders
• Independent families and some notions of finiteness
• On the number of independent sets in simple hypergraphs
• On the complexity of approximating the independent set problem
• Counting and enumerating independent sets with applications to combinatorial optimization problems
• The number of independent sets in graphs
• Counting independent sets in cocomparability graphs
• Parameterized extension complexity of independent set and related problems

Cites work

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

Cited in

(4)

• 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
• scientific article; zbMATH DE number 59574 (Why is no real title available?)

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

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