Independence number and the complexity of families of sets

DOI10.1016/0012-365X(94)00318-DzbMATH Open0852.05076MaRDI QIDQ1918552FDOQ1918552

Authors: Daniel Q. Naiman, Henry P. Wynn 

Publication date: 25 November 1996

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

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

zbMATH Keywords

complexityindependence numberVapnik-Chervonenkis dimensioninclusion-exclusionset systemqualitative independence

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

• Time and space complexity of deterministic and nondeterministic decision trees
• Independence number and the complexity of families of sets
• Title not available (Why is that?)
• Learning half-spaces on general infinite spaces equipped with a distance function

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)