Vapnik-Chervonenkis density on indiscernible sequences, stability, and the maximum property

DOI10.1215/00294527-3153597zbMATH Open1372.03064arXiv1302.5446OpenAlexW2113187842MaRDI QIDQ894257FDOQ894257

Authors: Hunter Johnson 

Publication date: 30 November 2015

Published in: Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Abstract: This paper presents some finite combinatorics of set systems with applications to model theory, particularly the study of dependent theories. There are two main results. First, we give a way of producing lower bounds on VC_ind-density, and use it to compute the exact VC_ind- density of polynomial inequalities, and a variety of geometric set families. The main technical tool used is the notion of a maximum set system, which we juxtapose to indiscernibles. In the second part of the paper we give a maximum set system analogue to Shelah's characterization of stability using indiscernible sequences.

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

Recommendations

• On Vapnik‐Chervonenkis density over indiscernible sequences
• Vapnik-Chervonenkis density in some theories without the independence property. II
• Vapnik-Chervonenkis density in some theories without the independence property. I
• On VC-density in VC-minimal theories
• On the independence property of first-order theories and indiscernible sequences

zbMATH Keywords

stabilityNIPVC-dimensionVC-density

Mathematics Subject Classification ID

Classification theory, stability, and related concepts in model theory (03C45) Extremal set theory (05D05)

Cites Work

• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• A combinatorial problem; stability and order for models and theories in infinitary languages
• On the density of families of sets
• Uniform Central Limit Theorems
• Additivity of the dp-rank
• Title not available (Why is that?)
• Vaught's conjecture for o-minimal theories
• Vapnik-Chervonenkis density in some theories without the independence property. II
• Vapnik-Chervonenkis Classes of Definable Sets
• Unlabeled compression schemes for maximum classes
• dp-rank and forbidden configurations
• Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes
• Title not available (Why is that?)
• On Vapnik‐Chervonenkis density over indiscernible sequences
• A geometric approach to sample compression

Cited In (5)

• On some dynamical aspects of NIP theories
• Vapnik-Chervonenkis density in some theories without the independence property. I
• On Vapnik‐Chervonenkis density over indiscernible sequences
• dp-rank and forbidden configurations
• Vapnik-Chervonenkis density in some theories without the independence property. II

This page was built for publication: Vapnik-Chervonenkis density on indiscernible sequences, stability, and the maximum property

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q894257)