On n-dependence

Abstract

In this note we develop and clarify some of the basic combinatorial properties of the new notion of $n$-dependence (for $1\le n<\omega$) recently introduced by Shelah. In the same way as dependence of a theory means its inability to encode a bipartite random graph with a definable edge relation, $n$-dependence corresponds to the inability to encode a random $(n+1)$-partite $(n+1)$-hypergraph with a definable edge relation. Most importantly, we characterize $n$-dependence by counting $\phi$-types over finite sets (generalizing Sauer-Shelah lemma and answering a question of Shelah) and in terms of the collapse of random ordered $(n+1)$-hypergraph indiscernibles down to order-indiscernibles (which implies that the failure of $n$-dependence is always witnessed by a formula in a single free variable).

22 pages; v.2: corrected a small issue in the published version of the paper, in the proof of (3) implies (2) of Theorem 5.4

References in corpus (3)

• Ramsey transfer to semi-retractions
• Dependent dreams: recounting types
• Indiscernibles, EM-types, and Ramsey Classes of Trees

Cited by in corpus (8)

• On n-dependent groups and fields II
• Keisler measures in the wild
• The additive groups of $\mathbb{Z}$ and $\mathbb{Q}$ with predicates for being square-free
• Hypergraph regularity and higher arity VC-dimension
• An improved bound for regular decompositions of $3$-uniform hypergraphs of bounded $V{C}_2$-dimension
• Mekler's Construction and Murphy's Law for 2-Nilpotent Groups
• Notes on trace equivalence
• Classification properties for some ternary structures