Vapnik-Chervonenkis density in some theories without the independence property, I

DOI10.1090/tran/6659zbMath1423.03119arXiv1109.5438OpenAlexW1975177932WikidataQ59892890 ScholiaQ59892890MaRDI QIDQ2790718

Dugald Macpherson, Alf Dolich, Matthias Aschenbrenner, Deirdre Haskell, Sergei Starchenko

Publication date: 8 March 2016

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1109.5438

Mathematics Subject Classification ID

Classification theory, stability, and related concepts in model theory (03C45) Model theory of ordered structures; o-minimality (03C64)

Related Items (27)

Structure and regularity for subsets of groups with finite VC-dimension ⋮ Vapnik-Chervonenkis dimension and density on Johnson and Hamming graphs ⋮ Unavoidable subprojections in union-closed set systems of infinite breadth ⋮ On VC-minimal theories and variants ⋮ Computability of validity and satisfiability in probability logics over finite and countable models ⋮ Combinatorial properties of nonarchimedean convex sets ⋮ Burden in Henselian valued fields ⋮ Neighbourhood complexity of graphs of bounded twin-width ⋮ A family of dp-minimal expansions of \((\mathbb{Z}; +)\) ⋮ A definable \((p,q)\)-theorem for NIP theories ⋮ The classification of dp-minimal and dp-small fields ⋮ Profinite groups with NIP theory andp-adic analytic groups ⋮ RAMSEY GROWTH IN SOME NIP STRUCTURES ⋮ THERE ARE NO INTERMEDIATE STRUCTURES BETWEEN THE GROUP OF INTEGERS AND PRESBURGER ARITHMETIC ⋮ On some dynamical aspects of NIP theories ⋮ Definability of types and VC density in differential topological fields ⋮ DP-MINIMAL VALUED FIELDS ⋮ THE DP-RANK OF ABELIAN GROUPS ⋮ A NEW DP-MINIMAL EXPANSION OF THE INTEGERS ⋮ Cutting lemma and Zarankiewicz's problem in distal structures ⋮ VC-density for trees ⋮ On \(n\)-dependence ⋮ On VC-density in VC-minimal theories ⋮ THICKET DENSITY ⋮ Externally definable sets and dependent pairs II ⋮ Additivity of the dp-rank ⋮ Model Theory in Algebra, Analysis and Arithmetic: A Preface

Cites Work

• The Szemerédi-Trotter theorem in the complex plane
• Vapnik-Chervonenkis density in some theories without the independence property. II
• An incidence theorem in higher dimensions
• Strongly dependent theories
• \(p\)-adic and real subanalytic sets
• Dp-minimality: basic facts and examples
• Polynomial bounds for VC dimension of sigmoidal and general Pfaffian neural networks
• A combinatorial distinction between the Euclidean and projective planes
• Ecole d'été de probabilités de Saint-Flour XII - 1982
• Compression schemes, stable definable families, and o-minimal structures
• Maximum number of edges joining vertices on a cube
• Repeated angles in the plane and related problems
• Classification theory and the number of non-isomorphic models.
• The homeomorphic embedding of \(K_n\) in the \(m\)-cube
• Problems and theorems in analysis. I. Series, integral calculus, theory of functions. Transl. from the German by Dorothee Aeppli
• Types in valued fields with coefficient maps
• Cell decompositions of \(C\)-minimal structures
• Discrepancy and approximations for bounded VC-dimension
• Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension
• Coset-minimal groups
• On the number of sets definable by polynomials
• Essentially periodic ordered groups
• On the independence property
• Density and dimension
• The Vapnik-Chervonenkis dimension of a random graph
• Bounded VC-dimension implies a fractional Helly theorem
• Tight upper bounds for the discrepancy of half-spaces
• Almost optimal set covers in finite VC-dimension
• Presburger arithmetic and recognizability of sets of natural numbers by automata: New proofs of Cobham's and Semenov's theorems
• On variants of \(o\)-minimality
• Externally definable sets and dependent pairs
• Closed asymptotic couples
• Unavoidable traces of set systems
• A combinatorial problem; stability and order for models and theories in infinitary languages
• On the density of families of sets
• Dependent first order theories, continued
• Stable theories with a new predicate
• Additivity of the dp-rank
• On uniform definability of types over finite sets
• On dp-minimal ordered structures
• Regularity partitions and the topology of graphons
• Randomness and semigenericity
• On dp-minimality, strong dependence and weight
• Cell decomposition forP-minimal fields
• A partition calculus in set theory
• Partially ordered sets and the independence property
• ℵ 0 -Categorical Distributive Lattices of Finite Breadth
• Théories d'arbres
• Elimination of quantifiers for ordered valuation rings
• Zero-One Laws for Sparse Random Graphs
• Vapnik-Chervonenkis Classes of Definable Sets
• On definable subsets of p-adic fields
• On stability and products
• Stable graphs
• Uniform Central Limit Theorems
• One-Dimensional p -Adic Subanalytic Sets
• A version of o-minimality for the p-adics
• On the Number of Incidences Between Points and Curves
• One-dimensional fibers of rigid subanalytic sets
• Analytic $p$-adic cell decomposition and integrals
• Weakly o-minimal structures and real closed fields
• Quasi-o-minimal structures
• On decidable extensions of Presburger arithmetic: from A. Bertrand numeration sytems to Pisot numbers
• The Theory of Ordered Abelian Groups does not have the Independence Property
• Stability, the f.c.p., and superstability; model theoretic properties of formulas in first order theory
• Model Theory
• Canonical forms for definable subsets of algebraically closed and real closed valued fields
• On the number of cells defined by a family of polynomials on a variety
• Externally definable sets and dependent pairs II
• Least energy nodal solutions for elliptic equations with indefinite nonlinearity
• Rigid Subanalytic Sets
• On Vapnik‐Chervonenkis density over indiscernible sequences
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• On a problem of K. Zarankiewicz
• The strange logic of random graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Vapnik-Chervonenkis density in some theories without the independence property, I