On the density of families of sets
From MaRDI portal
Publication:2556406
DOI10.1016/0097-3165(72)90019-2zbMath0248.05005MaRDI QIDQ2556406
Publication date: 1972
Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0097-3165(72)90019-2
05D05: Extremal set theory
Related Items
On intersecting a point set with Euclidean balls, The Glivenko-Cantelli problem, ten years later, A deterministic view of random sampling and its use in geometry, On disjointly representable sets, Embedding of \(\ell^ k_{\infty}\) in finite dimensional Banach spaces, An extremal problem for Graham-Rothschild parameter words, On families in finite lattices, Pairwise intersections and forbidden configurations, Spaces of operators, the \(\psi\)-Daugavet property, and numerical indices, On the VC-dimension of uniform hypergraphs, Covering numbers, Vapnik-Červonenkis classes and bounds for the star-discrepancy, Constrained versions of Sauer's Lemma, On the learnability of majority rule, Active sampling for multiple output identification, Combinatorial lemmas and applications to dynamics, Combinatorial independence in measurable dynamics, \(l\)-trace \(k\)-Sperner families of sets, On the density of sets of vectors, Matrices with forbidden subconfigurations, Hypergraphs without a large star, General forbidden configuration theorems, \(\epsilon\)-nets and simplex range queries, Donsker classes of sets, Invertibility of ``large submatrices with applications to the geometry of Banach spaces and harmonic analysis, Short cocircuits in binary matroids, Forbidden submatrices, The Banach-Mazur distance to the cube and the Dvoretzky-Rogers factorization, Bounding one-way differences, A forbidden configuration theorem of Alon, ``Dart calculus of induced subsets, Equivalence of models for polynomial learnability, Almost tight bounds for \(\epsilon\)-nets, Type, infratype and the Elton-Pajor theorem, Decision theoretic generalizations of the PAC model for neural net and other learning applications, Trade-offs between communication and space, Existence of submatrices with all possible columns, Coordinate density of sets of vectors, Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes, A graph-theoretic generalization of the Sauer-Shelah lemma, Scale-sensitive dimensions and skeleton estimates for classification, General bounds on statistical query learning and PAC learning with noise via hypothesis boosting, Sample size lower bounds in PAC learning by Algorithmic Complexity Theory, Selecting a proportion of characters, Separable partitions, The VC-dimension of Sperner systems, Combinatorics and connectionism, A result of Vapnik with applications, Discrepancy and approximations for bounded VC-dimension, Density results for uniform families, A review of combinatorial problems arising in feedforward neural network design, Halfspace learning, linear programming, and nonmalicious distributions, Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements, Some best possible bounds concerning the traces of finite sets, A theory for memory-based learning, On the density of sets of divisors, Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension, On the convexified Sauer-Shelah theorem, Small forbidden configurations, A sufficient condition for polynomial distribution-dependent learnability, On the complexity of learning from drifting distributions, Sperner families of bounded VC-dimension, Guarding galleries where every point sees a large area, Counterexample to the Frankl-Pach conjecture for uniform, dense families, Well-known bound for the VC-dimension made easy, PAC-learning from general examples, Query complexity of membership comparable sets., Which problems have strongly exponential complexity?, On the reducibility of sets inside NP to sets with low information content, Boosting the margin: a new explanation for the effectiveness of voting methods, Traces of antichains, Forbidden configurations, discrepancy and determinants, Quasi-optimal range searching in spaces of finite VC-dimension, On the trace of finite sets, Density and dimension, On the number of sets in a null t-design, Some remarks about embeddings of \(l_1^k\) in finite-dimensional spaces, General lower bounds on the query complexity within the exact learning model, PAC learning with nasty noise., Generalization error of combined classifiers., On the complexity of approximating the VC dimension., Multicoloured extremal problems, A counterexample concerning uniform ergodic theorems for a class of functions, Forbidden configurations: Induction and linear algebra, A generalization of Sauer's lemma, On the complexity of function learning, Defect Sauer results, Almost optimal set covers in finite VC-dimension, Improved upper bounds for probabilities of uniform deviations, Independence number and the complexity of families of sets, On membership comparable sets, Accuracy of techniques for the logical analysis of data, \(P\)-sufficient statistics for PAC learning \(k\)-term-DNF formulas through enumeration, Model selection by bootstrap penalization for classification, A new PAC bound for intersection-closed concept classes, Independence in topological and \(C^*\)-dynamics, Quadratic boosting, Forbidding complete hypergraphs as traces, Aspects of discrete mathematics and probability in the theory of machine learning, On the complexity of constrained VC-classes, Shifting: one-inclusion mistake bounds and sample compression, An extension of Elton’s ℓ₁ⁿ theorem to complex Banach spaces, A proportional Dvoretzky-Rogers factorization result, Parameter selection in modified histogram estimates, A lower bound for families of Natarajan dimension \(d\), On the unique shortest lattice vector problem, The communication complexity of enumeration, elimination, and selection, Projective geometries in dense matroids, Disjoint representability of sets and their complements, Integer cells in convex sets, The enumerability of P collapses P to NC, Theory of Classification: a Survey of Some Recent Advances, Edge Multiplicity and Other Trace Functions, Local entropy theory, On approximating Lebesgue integrals by Riemann sums
Cites Work
