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

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

Saharon Shelah

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 (only showing first 100 items - show all)

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 ⋮ Treelike decompositions for transductions of sparse graphs ⋮ 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 ⋮ A characterization of list learnability ⋮ 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 ⋮ A bicriteria approximation algorithm for the minimum hitting set problem in measurable range spaces ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ On the maximal number of columns of a \(\Delta \)-modular integer matrix: bounds and computations ⋮ Bounding Embeddings of VC Classes into Maximum Classes ⋮ Shattering \(k\)-sets with permutations ⋮ Discrepancy and sparsity ⋮ Theory of Classification: a Survey of Some Recent Advances ⋮ Projective geometries in dense matroids ⋮ Geometric decision procedures and the VC dimension of linear arithmetic theories ⋮ 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 ⋮ On the complexity of approximating the VC dimension. ⋮ Unlabeled sample compression schemes and corner peelings for ample and maximum classes

This page was built for publication: A combinatorial problem; stability and order for models and theories in infinitary languages