An official website of the United States government
Abstract We prove various results around indiscernibles in monadically NIP theories. First, we provide several characterizations of monadic NIP in terms of indiscernibles, mirroring previous characterizations in terms of the behavior of finite satisfiability. Second, we study (monadic) distality in hereditary classes and complete theories. Here, via finite combinatorics, we prove a result implying that every planar graph admits a distal expansion. Finally, we prove a result implying that no monadically NIP theory interprets an infinite group, and note an example of a (monadically) stable theory with no distal expansion that does not interpret an infinite group.
more »
« less
Characterizations of monadic NIP
We give several characterizations of when a complete first-order theory T T is monadically NIP, i.e. when expansions of T T by arbitrary unary predicates do not have the independence property. The central characterization is a condition on finite satisfiability of types. Other characterizations include decompositions of models, the behavior of indiscernibles, and a forbidden configuration. As an application, we prove non-structure results for hereditary classes of finite substructures of non-monadically NIP models that eliminate quantifiers.
more »
« less
- Award ID(s):
- 1855789
- PAR ID:
- 10409420
- Date Published:
- Journal Name:
- Transactions of the American Mathematical Society, Series B
- Volume:
- 8
- Issue:
- 30
- ISSN:
- 2330-0000
- Page Range / eLocation ID:
- 948 to 970
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
The authors correct results in “Characterizations of monadic NIP” [Trans. Amer. Math. Soc. Ser. B 8 (2021), pp. 948–970]. The notion of endless indiscernible triviality is introduced and replaces indiscernible triviality throughout, in particular in Theorem 1.1. The claim regarding the failure of 4-wqo in Theorem 1.2 is withdrawn and remains unproved.more » « less
-
We establish a list of characterizations of bounded twin-width for hereditary classes of totally ordered graphs: as classes of at most exponential growth studied in enumerative combinatorics, as monadically NIP classes studied in model theory, as classes that do not transduce the class of all graphs studied in finite model theory, and as classes for which model checking first-order logic is fixed-parameter tractable studied in algorithmic graph theory. This has several consequences. First, it allows us to show that every hereditary class of ordered graphs either has at most exponential growth, or has at least factorial growth. This settles a question first asked by Balogh, Bollobás, and Morris [Eur. J. Comb. ’06] on the growth of hereditary classes of ordered graphs, generalizing the Stanley-Wilf conjecture/Marcus-Tardos theorem. Second, it gives a fixed-parameter approximation algorithm for twin-width on ordered graphs. Third, it yields a full classification of fixed-parameter tractable first-order model checking on hereditary classes of ordered binary structures. Fourth, it provides a model-theoretic characterization of classes with bounded twin-width. Finally, it settles our small conjecture [SODA ’21] in the case of ordered graphs.more » « less
-
Fix a weakly minimal (i.e. superstable [Formula: see text]-rank [Formula: see text]) structure [Formula: see text]. Let [Formula: see text] be an expansion by constants for an elementary substructure, and let [Formula: see text] be an arbitrary subset of the universe [Formula: see text]. We show that all formulas in the expansion [Formula: see text] are equivalent to bounded formulas, and so [Formula: see text] is stable (or NIP) if and only if the [Formula: see text]-induced structure [Formula: see text] on [Formula: see text] is stable (or NIP). We then restrict to the case that [Formula: see text] is a pure abelian group with a weakly minimal theory, and [Formula: see text] is mutually algebraic (equivalently, weakly minimal with trivial forking). This setting encompasses most of the recent research on stable expansions of [Formula: see text]. Using various characterizations of mutual algebraicity, we give new examples of stable structures of the form [Formula: see text]. Most notably, we show that if [Formula: see text] is a weakly minimal additive subgroup of the algebraic numbers, [Formula: see text] is enumerated by a homogeneous linear recurrence relation with algebraic coefficients, and no repeated root of the characteristic polynomial of [Formula: see text] is a root of unity, then [Formula: see text] is superstable for any [Formula: see text].more » « less
-
Truncated Karhunen–Loève (KL) representations are used to construct finite dimensional (FD) models for non-Gaussian functions with finite variances. The second moment specification of the random coefficients of these representations are enhanced to full probabilistic characterization by using translation, polynomial chaos, and translated polynomial chaos models, referred to as T, PC, and PCT models. Following theoretical considerations on KL representations and T, PC, and PCT models, three numerical examples are presented to illustrate the implementation and performance of these models. The PCT models inherit the desirable features of both T and PC models. It approximates accurately all quantities of interest considered in these examples.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1090/btran/94
