An official website of the United States government
This paper builds model-theoretic tools to detect changes in complexity among the simple theories. We develop a generalization of dividing, called shearing, which depends on a so-called context c. This leads to defining c-superstability, a syntactical notion, which includes supersimplicity as a special case. The main result is a separation theorem showing that for any countable context and any two theories T1, T2, such that T1 is c-superstable and T2 is c-unsuperstable, and for arbitrarily large mu, it is possible to build models of any theory interpreting both T1 and T2 whose restriction to tau(T1) is mu-saturated and whose restriction to tau(T2) is not aleph1-saturated. (This suggests “c-superstable” is really a dividing line.) The proof uses generalized Ehrenfeucht-Mostowski models, and along the way, we clarify the use of these techniques to realize certain types while omitting others. In some sense, shearing allows us to study the interaction of complexity coming from the usual notion of dividing in simple theories and the more combinatorial complexity detected by the general definition. This work is inspired by our recent progress on Keisler’s order, but does not use ultrafilters, rather aiming to build up the internal model theory of these classes. https://doi.org/10.1090/tran/8513
more »
« less
Some simple theories from a Boolean algebra point of view
We find a strong separation between two natural families of simple rank one theories in Keisler's order: the theories $$T_m$$ reflecting graph sequences, which witness that Keisler's order has the maximum number of classes, and the theories $$T_{n,k}$$, which are the higher-order analogues of the triangle-free random graph. The proof involves building Boolean algebras and ultrafilters ``by hand'' to satisfy certain model theoretically meaningful chain conditions. This may be seen as advancing a line of work going back through Kunen's construction of good ultrafilters in ZFC using families of independent functions. We conclude with a theorem on flexible ultrafilters, and open questions.
more »
« less
- PAR ID:
- 10517940
- Publisher / Repository:
- Annals of Pure and Applied Logic
- Date Published:
- Journal Name:
- Annals of Pure and Applied Logic
- Volume:
- 175
- Issue:
- PB
- ISSN:
- 0168-0072
- Page Range / eLocation ID:
- 103345
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Dividing asks about inconsistency along indiscernible sequences. In order to study the finer structure of simple theories without much dividing, the authors recently introduced shearing, which essentially asks about inconsistency along generalized indiscernible sequences. Here we characterize the shearing of the random graph. We then use shearing to distinguish between the random graph and the theories $$T_{n,k}$$, the higher-order analogues of the triangle-free random graph. It follows that shearing is distinct from dividing in simple unstable theories, and distinguishes meaningfully between classes of simple unstable rank one theories. The paper begins with an overview of shearing, and includes open questions.more » « less
-
Although it is well known that some exponential family random graph model (ERGM) families exhibit phase transitions (in which small parameter changes lead to qualitative changes in graph structure), the behavior of other models is still poorly understood. Recently, Krivitsky and Morris have reported a previously unobserved phase transition in the edge/concurrent vertex family (a simple starting point for models of sexual contact networks). Here, we examine this phase transition, showing it to be a first-order transition with respect to an order parameter associated with the fraction of concurrent vertices. This transition stems from weak cooperativity in the recruitment of vertices to the concurrent phase, which may not be a desirable property in some applications.more » « less
-
The Wiener index of a finite graph $$G$$ is the sum over all pairs $(p,q)$ of vertices of $$G$$ of the distance between $$p$$ and $$q$$. When $$P$$ is a finite poset, we define its Wiener index as the Wiener index of the graph of its Hasse diagram. In this paper, we find exact expressions for the Wiener indices of the distributive lattices of order ideals in minuscule posets. For infinite families of such posets, we also provide results on the asymptotic distribution of the distance between two random order ideals.more » « less
-
Abstract In order to better understand manifold neural networks (MNNs), we introduce Manifold Filter-Combine Networks (MFCNs). Our filter-combine framework parallels the popular aggregate-combine paradigm for graph neural networks (GNNs) and naturally suggests many interesting families of MNNs which can be interpreted as manifold analogues of various popular GNNs. We propose a method for implementing MFCNs on high-dimensional point clouds that relies on approximating an underlying manifold by a sparse graph. We then prove that our method is consistent in the sense that it converges to a continuum limit as the number of data points tends to infinity, and we numerically demonstrate its effectiveness on real-world and synthetic data sets.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1016/j.apal.2023.103345
