A combinatorial problem; stability and order for models and theories in infinitary languages

DOI10.2140/pjm.1972.41.247zbMath0239.02024OpenAlexW2020913456WikidataQ100600660 ScholiaQ100600660MaRDI QIDQ2553434

Publication date: 1972

Published in: Pacific Journal of Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2140/pjm.1972.41.247

Mathematics Subject Classification ID

Descriptive set theory (03E15) Model theory (03C99) Other combinatorial set theory (03E05) Other infinitary logic (03C75)

Related Items

On the complexity of approximating the VC dimension. ⋮ Unlabeled sample compression schemes and corner peelings for ample and maximum classes ⋮ Infinitary stability theory ⋮ Multicoloured extremal problems ⋮ Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements ⋮ A Sauer-Shelah-Perles lemma for sumsets ⋮ Some best possible bounds concerning the traces of finite sets ⋮ General forbidden configuration theorems ⋮ On the density of sets of divisors ⋮ Invertibility of ``large submatrices with applications to the geometry of Banach spaces and harmonic analysis ⋮ VC-saturated set systems ⋮ Shattering and more: Extending the complete object ⋮ Forbidden configurations: Induction and linear algebra ⋮ On the convexified Sauer-Shelah theorem ⋮ Pairwise intersections and forbidden configurations ⋮ Forbidden submatrices ⋮ Small forbidden configurations ⋮ On the VC-dimension of uniform hypergraphs ⋮ The Banach-Mazur distance to the cube and the Dvoretzky-Rogers factorization ⋮ Uniform approximation rates and metric entropy of shallow neural networks ⋮ Disjointness through the lens of Vapnik-Chervonenkis dimension: sparsity and beyond ⋮ On the maximal number of columns of a \(\varDelta \)-modular matrix ⋮ Bounding one-way differences ⋮ A uniform version of a theorem by Dvir and Moran ⋮ Nondegenerate spheres in four dimensions ⋮ The \(\varepsilon\)-\(t\)-net problem ⋮ A forbidden configuration theorem of Alon ⋮ What convex geometries tell about shattering-extremal systems ⋮ On minimum saturated matrices ⋮ Periodic existentially closed nilpotent groups ⋮ An unclassifiable unidimensional theory without OTOP ⋮ 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 ⋮ Guarding galleries where every point sees a large area ⋮ Combinatorial independence and sofic entropy ⋮ Counterexample to the Frankl-Pach conjecture for uniform, dense families ⋮ Some recent results on Ramsey-type numbers ⋮ A width parameter useful for chordal and co-comparability graphs ⋮ PAC-learning from general examples ⋮ Shattering, graph orientations, and connectivity ⋮ Repeated columns and an old chestnut ⋮ dp-rank and forbidden configurations ⋮ Vapnik-Chervonenkis density on indiscernible sequences, stability, and the maximum property ⋮ Coverings: variations on a result of Rogers and on the epsilon-net theorem of Haussler and Welzl ⋮ Shattering-extremal set systems of small VC-dimension ⋮ Forbidden configurations and repeated induction ⋮ On membership comparable sets ⋮ 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 ⋮ Constructing strongly equivalent nonisomorphic models for unstable theories ⋮ Approximating a convex body by a polytope using the epsilon-net theorem ⋮ Parameterized and approximation complexity of \textsc{Partial VC Dimension} ⋮ Set families with forbidden subposets ⋮ Type, infratype and the Elton-Pajor theorem ⋮ Constrained versions of Sauer's Lemma ⋮ The Glivenko-Cantelli problem, ten years later ⋮ Domination in tournaments ⋮ Trade-offs between communication and space ⋮ Superstability from categoricity in abstract elementary classes ⋮ 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 ⋮ Separation by convex pseudo-circles ⋮ Forbidden subposet problems for traces of set families ⋮ Testing conditional independence in supervised learning algorithms ⋮ Uncountable universal locally finite groups ⋮ On the learnability of majority rule ⋮ Two proofs for shallow packings ⋮ Choosing between incompatible ideals ⋮ On extremal problems concerning the traces of sets ⋮ A polynomial kernel for trivially perfect editing ⋮ Coordinate density of sets of vectors ⋮ Combinatorial lemmas and applications to dynamics ⋮ Combinatorial independence in measurable dynamics ⋮ A graph-theoretic generalization of the Sauer-Shelah lemma ⋮ Traces of antichains ⋮ Forbidden configurations, discrepancy and determinants ⋮ Selecting a proportion of characters ⋮ VC-dimensions of nondeterministic finite automata for words of equal length ⋮ Toward better depth lower bounds: two results on the multiplexor relation ⋮ Density and dimension ⋮ Some remarks about embeddings of \(l_1^k\) in finite-dimensional spaces ⋮ Two-dimensional partial cubes ⋮ General lower bounds on the query complexity within the exact learning model ⋮ The spectrum problem. I: \(\aleph_{\epsilon}\)-saturated models, the main gap ⋮ Bounding the trace function of a hypergraph with applications ⋮ On the density of sets of vectors ⋮ Ranks and pregeometries in finite diagrams ⋮ Uncountable extensions of countable algebraically closed semigroups ⋮ Embedding of \(\ell^ k_{\infty}\) in finite dimensional Banach spaces ⋮ Matrices with forbidden subconfigurations ⋮ An extremal problem for Graham-Rothschild parameter words ⋮ Hanf number of the first stability cardinal in AECs ⋮ Combinatorics and connectionism ⋮ On families in finite lattices ⋮ Two results on entropy, chaos and independence in symbolic dynamics ⋮ Density results for uniform families ⋮ Structured Codes of Graphs ⋮ 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 the Number of Distinct Rows of a Matrix with Bounded Subdeterminants ⋮ A local variational relation and applications ⋮ Ample Completions of Oriented Matroids and Complexes of Uniform Oriented Matroids ⋮ Independence in topological and \(C^*\)-dynamics ⋮ Vertex isoperimetry and independent set stability for tensor powers of cliques ⋮ 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 ⋮ On the VC-Dimension of Binary Codes ⋮ Shallow packings, semialgebraic set systems, macbeath regions, and polynomial partitioning ⋮ Erdős-Hajnal conjecture for graphs with bounded VC-dimension ⋮ Purity and Separation for Oriented Matroids ⋮ Time and space complexity of deterministic and nondeterministic decision trees ⋮ Edge Multiplicity and Other Trace Functions ⋮ A story of diameter, radius, and (almost) Helly property ⋮ On partial cubes, well-graded families and their duals with some applications in graphs ⋮ Demushkin groups of uncountable rank ⋮ Exploring implications of trace (inversion) formula and Artin algebras in extremal combinatorics ⋮ An elementary proof of a lower bound for the inverse of the star discrepancy ⋮ 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 ⋮ Near-Optimal Lower Bounds for ε-Nets for Half-Spaces and Low Complexity Set Systems ⋮ Restricted Invertibility Revisited ⋮ A proportional Dvoretzky-Rogers factorization result ⋮ A Sauer-Shelah-Perles lemma for lattices ⋮ McCulloch-Pitts Brains and Pseudorandom Functions ⋮ Unnamed Item ⋮ Some new maximum VC classes ⋮ Classes of graphs with low complexity: the case of classes with bounded linear rankwidth ⋮ MULTIVALUED GENERALIZATIONS OF THE FRANKL–PACH THEOREM ⋮ Shattered matchings in intersecting hypergraphs ⋮ 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 ⋮ Turánnical hypergraphs ⋮ Algebraic Properties of ModuloqComplete ℓ-Wide Families ⋮ Some Combinatorial Applications of Gröbner Bases ⋮ Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond ⋮ Forbidding complete hypergraphs as traces ⋮ Aspects of discrete mathematics and probability in the theory of machine learning ⋮ Sequential complexities and uniform martingale laws of large numbers ⋮ On forbidden submatrices ⋮ A lower bound for families of Natarajan dimension \(d\) ⋮ Algebraically closed groups of large cardinality ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Ramsey numbers of Berge-hypergraphs and related structures ⋮ Vapnik-Chervonenkis density in some theories without the independence property, I ⋮ A local Vapnik-Chervonenkis complexity ⋮ ERDŐS AND SET THEORY ⋮ Indiscernible sequences in a model which fails to have the order property ⋮ On chains of relatively saturated submodels of a model without the order property ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ Bounding Embeddings of VC Classes into Maximum Classes ⋮ Theory of Classification: a Survey of Some Recent Advances ⋮ Projective geometries in dense matroids ⋮ Local entropy theory ⋮ Generalized Descriptive Set Theory and Classification Theory ⋮ Entropy dimension of topological dynamical systems ⋮ A rank for the class of elementary submodels of a superstable homogeneous model ⋮ Traces of hypergraphs ⋮ On the VC-dimension and boolean functions with long runs ⋮ Multi-symbol forbidden configurations ⋮ Shattering-extremal set systems from Sperner families ⋮ VC-density for trees ⋮ Labeled Compression Schemes for Extremal Classes ⋮ VC dimension and a union theorem for set systems ⋮ 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 ⋮ On the density of families of sets ⋮ An independence result in quadratic form theory: Infinitary combinatorics applied to ε-Hermitian spaces ⋮ Combinatorial independence and naive entropy ⋮ Family independence for topological and measurable dynamics ⋮ Disjoint representability of sets and their complements ⋮ Digraphs of Bounded Width ⋮ Integer cells in convex sets ⋮ The legacy of Jean Bourgain in geometric functional analysis ⋮ The enumerability of P collapses P to NC ⋮ Unnamed Item ⋮ Fast Diameter Computation within Split Graphs