On the density of families of sets
From MaRDI portal
Publication:2556406
DOI10.1016/0097-3165(72)90019-2zbMath0248.05005OpenAlexW1971361630MaRDI 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
Related Items
Structured Codes of Graphs, Restricted invertibility of continuous matrix functions, An extension of Elton’s ℓ₁ⁿ theorem to complex Banach spaces, Ramsey properties of algebraic graphs and hypergraphs, Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension, Identifying Codes in Hereditary Classes of Graphs and VC-Dimension, On approximating Lebesgue integrals by Riemann sums, On the Number of Distinct Rows of a Matrix with Bounded Subdeterminants, Ample Completions of Oriented Matroids and Complexes of Uniform Oriented Matroids, Parameter selection in modified histogram estimates, Vertex isoperimetry and independent set stability for tensor powers of cliques, Analysis of the generalization ability of a full decision tree, On the VC-Dimension of Binary Codes, Rates of the strong uniform consistency for the kernel-type regression function estimators with general kernels on manifolds, Purity and Separation for Oriented Matroids, Edge Multiplicity and Other Trace Functions, A story of diameter, radius, and (almost) Helly property, Exploring implications of trace (inversion) formula and Artin algebras in extremal combinatorics, Four-vertex traces of finite sets, Approximating length-restricted means under dynamic time warping, Relative uniformly positive entropy of induced amenable group actions, Inapproximability of Truthful Mechanisms via Generalizations of the Vapnik--Chervonenkis Dimension, Max-norm Ramsey theory, Improved incidence bounds over arbitrary finite fields via the VC-dimension theory, A theoretical framework for deep transfer learning, Near-Optimal Lower Bounds for ε-Nets for Half-Spaces and Low Complexity Set Systems, Teaching and Compressing for Low VC-Dimension, Restricted Invertibility Revisited, On the Chromatic Thresholds of Hypergraphs, Sign rank versus Vapnik-Chervonenkis dimension, A proportional Dvoretzky-Rogers factorization result, McCulloch-Pitts Brains and Pseudorandom Functions, Unnamed Item, MULTIVALUED GENERALIZATIONS OF THE FRANKL–PACH THEOREM, Weakly Radon–Nikodým Boolean algebras and independent sequences, RAMSEY GROWTH IN SOME NIP STRUCTURES, Bounding the Order of a Graph Using Its Diameter and Metric Dimension: A Study Through Tree Decompositions and VC Dimension, Sampling Conditionally on a Rare Event via Generalized Splitting, Turánnical hypergraphs, Algebraic Properties of ModuloqComplete ℓ-Wide Families, Sample Complexity of Classifiers Taking Values in ℝQ, Application to Multi-Class SVMs, Some Combinatorial Applications of Gröbner Bases, Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond, Family Complexity and VC-Dimension, A lower bound for families of Natarajan dimension \(d\), On the unique shortest lattice vector problem, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, The communication complexity of enumeration, elimination, and selection, Order compression schemes, Lossy Kernels for Connected Dominating Set on Sparse Graphs, Theory of Classification: a Survey of Some Recent Advances, Local entropy theory, Entropy dimension of topological dynamical systems, Traces of hypergraphs, On the VC-dimension and boolean functions with long runs, Shatter Functions with Polynomial Growth Rates, Verifiable Stream Computation and Arthur--Merlin Communication, Lossy Kernels for Connected Dominating Set on Sparse Graphs, Exponential multivalued forbidden configurations, Combinatorial independence and naive entropy, Family independence for topological and measurable dynamics, Unnamed Item, Digraphs of Bounded Width, The legacy of Jean Bourgain in geometric functional analysis, Unnamed Item, Unnamed Item, Fast Diameter Computation within Split Graphs, 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, Embeddings and the trace of finite sets, Some best possible bounds concerning the traces of finite sets, General forbidden configuration theorems, \(\epsilon\)-nets and simplex range queries, A theory for memory-based learning, On the density of sets of divisors, Donsker classes of sets, Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension, Invertibility of ``large submatrices with applications to the geometry of Banach spaces and harmonic analysis, Bounding the expectation of the supremum of an empirical process over a (weak) VC-major class, On the convexified Sauer-Shelah theorem, Pairwise intersections and forbidden configurations, Spaces of operators, the \(\psi\)-Daugavet property, and numerical indices, Short cocircuits in binary matroids, Forbidden submatrices, Small forbidden configurations, On the VC-dimension of uniform hypergraphs, The Banach-Mazur distance to the cube and the Dvoretzky-Rogers factorization, A sufficient condition for polynomial distribution-dependent learnability, Bounding one-way differences, A forbidden configuration theorem of Alon, On minimum saturated matrices, On the complexity of learning from drifting distributions, Sperner families of bounded VC-dimension, Vapnik-Chervonenkis density in some theories without the independence property. II, Covering numbers, Vapnik-Červonenkis classes and bounds for the star-discrepancy, Combinatorial independence and sofic entropy, Some recent results on Ramsey-type numbers, Supervised learning and co-training, Shattering, graph orientations, and connectivity, Repeated columns and an old chestnut, Connecting deterministic and stochastic metapopulation models, Vapnik-Chervonenkis density on indiscernible sequences, stability, and the maximum property, The thin set theorem for pairs implies DNR, VC bounds on the cardinality of nearly orthogonal function classes, The structure of almost all graphs in a hereditary property, Generalization error bounds for the logical analysis of data, Lower bounds for comparison based evolution strategies using VC-dimension and sign patterns, Learning with stochastic inputs and adversarial outputs, Forbidden configurations and repeated induction, ``Dart calculus of induced subsets, A statistical learning theory approach for uncertain linear and bilinear matrix inequalities, Algebraic methods proving Sauer's bound for teaching complexity, Linear algebra methods for Forbidden configurations, Shattering-extremal set systems of VC dimension at most 2, Equivalence of models for polynomial learnability, Set families with forbidden subposets, Almost tight bounds for \(\epsilon\)-nets, Type, infratype and the Elton-Pajor theorem, On intersecting a point set with Euclidean balls, Constrained versions of Sauer's Lemma, The Glivenko-Cantelli problem, ten years later, Decision theoretic generalizations of the PAC model for neural net and other learning applications, A polynomial Turing-kernel for weighted independent set in bull-free graphs, Trade-offs between communication and space, Forbidden configurations and Steiner designs, On \(k\)-partite hypergraphs with the induced \(\epsilon \)-density property, Banach spaces and Ramsey theory: some open problems, Two refinements of the bound of Sauer, Perles and Shelah, and of Vapnik and Chervonenkis, Maximal pattern complexity, dual system and pattern recognition, Uniform convergence of Vapnik-Chervonenkis classes under ergodic sampling, Testing conditional independence in supervised learning algorithms, One-inclusion hypergraph density revisited, Existence of submatrices with all possible columns, On the learnability of majority rule, Two proofs for shallow packings, Coordinate density of sets of vectors, Active sampling for multiple output identification, Combinatorial lemmas and applications to dynamics, Combinatorial independence in measurable dynamics, 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, A deterministic view of random sampling and its use in geometry, General bounds on statistical query learning and PAC learning with noise via hypothesis boosting, \(l\)-trace \(k\)-Sperner families of sets, Sample size lower bounds in PAC learning by Algorithmic Complexity Theory, New bounds on classical and quantum one-way communication complexity, On the complexity of binary samples, Selecting a proportion of characters, Separable partitions, Toward better depth lower bounds: two results on the multiplexor relation, Uniform sets and complexity, Two-dimensional partial cubes, The VC-dimension of Sperner systems, On the density of sets of vectors, On disjointly representable sets, Embedding of \(\ell^ k_{\infty}\) in finite dimensional Banach spaces, Matrices with forbidden subconfigurations, Hypergraphs without a large star, An extremal problem for Graham-Rothschild parameter words, Combinatorics and connectionism, A result of Vapnik with applications, Discrepancy and approximations for bounded VC-dimension, On families in finite lattices, Two results on entropy, chaos and independence in symbolic dynamics, Density results for uniform families, Generalization error of combined classifiers., On the complexity of approximating the VC dimension., Unlabeled sample compression schemes and corner peelings for ample and maximum classes, Multicoloured extremal problems, A Sauer-Shelah-Perles lemma for sumsets, VC-saturated set systems, Shattering and more: Extending the complete object, A counterexample concerning uniform ergodic theorems for a class of functions, Forbidden configurations: Induction and linear algebra, A generalization of Sauer's lemma, Model selection by bootstrap penalization for classification, A new PAC bound for intersection-closed concept classes, Independence in topological and \(C^*\)-dynamics, Quadratic boosting, On the complexity of function learning, Defect Sauer results, Almost optimal set covers in finite VC-dimension, Uniform approximation rates and metric entropy of shallow neural networks, Disjointness through the lens of Vapnik-Chervonenkis dimension: sparsity and beyond, Improved upper bounds for probabilities of uniform deviations, On the maximal number of columns of a \(\varDelta \)-modular matrix, A uniform version of a theorem by Dvir and Moran, Nondegenerate spheres in four dimensions, The \(\varepsilon\)-\(t\)-net problem, What convex geometries tell about shattering-extremal systems, Independence number and the complexity of families of sets, Two results about the hypercube, Guarding galleries where every point sees a large area, Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs, The VC dimension of metric balls under Fréchet and Hausdorff distances, Counterexample to the Frankl-Pach conjecture for uniform, dense families, Well-known bound for the VC-dimension made easy, A width parameter useful for chordal and co-comparability graphs, Shallow packings, semialgebraic set systems, macbeath regions, and polynomial partitioning, Erdős-Hajnal conjecture for graphs with bounded VC-dimension, PAC-learning from general examples, dp-rank and forbidden configurations, Time and space complexity of deterministic and nondeterministic decision trees, Coverings: variations on a result of Rogers and on the epsilon-net theorem of Haussler and Welzl, On partial cubes, well-graded families and their duals with some applications in graphs, Query complexity of membership comparable sets., An elementary proof of a lower bound for the inverse of the star discrepancy, Shattering-extremal set systems of small VC-dimension, A Sauer-Shelah-Perles lemma for lattices, Relative deviation learning bounds and generalization with unbounded loss functions, On membership comparable sets, Accuracy of techniques for the logical analysis of data, Some new maximum VC classes, Discrepancy and numerical integration on metric measure spaces, Learning privately with labeled and unlabeled examples, Classes of graphs with low complexity: the case of classes with bounded linear rankwidth, Approximating a convex body by a polytope using the epsilon-net theorem, Parameterized and approximation complexity of \textsc{Partial VC Dimension}, Shattered matchings in intersecting hypergraphs, \(P\)-sufficient statistics for PAC learning \(k\)-term-DNF formulas through enumeration, Domination in tournaments, Forbidding complete hypergraphs as traces, Aspects of discrete mathematics and probability in the theory of machine learning, On the complexity of constrained VC-classes, Sequential complexities and uniform martingale laws of large numbers, On forbidden submatrices, On the reducibility of sets inside NP to sets with low information content, Separation by convex pseudo-circles, Research on probabilistic methods for control system design, Ramsey numbers of Berge-hypergraphs and related structures, Forbidden subposet problems for traces of set families, Vapnik-Chervonenkis density in some theories without the independence property, I, A local Vapnik-Chervonenkis complexity, On Hamiltonian Berge cycles in [3-uniform hypergraphs], Choosing between incompatible ideals, On extremal problems concerning the traces of sets, The complexity of exact learning of acyclic conditional preference networks from swap examples, VC-dimension and Erdős-Pósa property, A polynomial kernel for trivially perfect editing, Estimating a density, a hazard rate, and a transition intensity via the \(\rho\)-estimation method, Sketched History: VC Combinatorics, 1826 up to 1975, Shifting: one-inclusion mistake bounds and sample compression, Projective geometries in dense matroids, Boosting the margin: a new explanation for the effectiveness of voting methods, Traces of antichains, Forbidden configurations, discrepancy and determinants, Multi-symbol forbidden configurations, Shattering-extremal set systems from Sperner families, On density of subgraphs of halved cubes, VC-density for trees, Labeled Compression Schemes for Extremal Classes, VC dimension and a union theorem for set systems, Quasi-optimal range searching in spaces of finite VC-dimension, VC-dimensions of nondeterministic finite automata for words of equal length, On the trace of finite sets, Density and dimension, On the number of sets in a null t-design, Disjoint representability of sets and their complements, Some remarks about embeddings of \(l_1^k\) in finite-dimensional spaces, General lower bounds on the query complexity within the exact learning model, Integer cells in convex sets, Bounding the trace function of a hypergraph with applications, The enumerability of P collapses P to NC, PAC learning with nasty noise., Which problems have strongly exponential complexity?
Cites Work
