back to index

  • Ph.D. thesis: Persistence and Regularity in Unstable Model Theory, Berkeley, 2009. PDF, overview.

    Abstracts of papers (in near chronological order):

  • M. Malliaris, "Realization of \phi-types and Keisler's order." Annals of Pure and Applied Logic 157 (2009) 220-224. PDF, mathscinet

    Abstract: We show that the analysis of Keisler's order can be localized to the study of \phi-types. Specifically, if D is a regular ultrafilter on \lambda \geq \aleph_0 such that \lcf(\omega, D) \geq \lambda^+ and M is a model whose theory is countable, then M^\lambda/D is \lambda^+-saturated iff it realizes all \phi-types over sets of size \lambda.

  • M. Malliaris, "The characteristic sequence of an unstable formula," Journal of Symbolic Logic, 75, 4 (2010) pp. 1415-1440. PDF, published version

    Abstract: This article introduces and develops the theory of characteristic sequences. For a first-order formula \phi(x;y) we introduce and study the characteristic sequence (P_n : n \in \omega) of hypergraphs defined by P_n(y1, . . . , yn) := \exists x (\bigwedge_{i\leq n} \phi(x;y) ). We show that combinatorial and classification theoretic properties of the characteristic sequence reflect classification theoretic properties of \phi and vice versa. The main results are a characterization of NIP and of simplicity in terms of persistence of configurations in the characteristic sequence. Specifically, we show that some tree properties are detected by the presence of certain combinatorial configurations in the characteristic sequence while other properties such as instability and the independence property manifest themselves in the persistence of complicated configurations under localization. Post script: in 2.4(4) and its uses, clearly 'infinite' should be 'unbounded' relative to the size of the language, or just assume L is finite.

  • M. Malliaris, "Edge distribution and density in the characteristic sequence," Annals of Pure and Applied Logic 162, 1 (2010) 1-19. PDF, published version

    Abstract: The characteristic sequence of hypergraphs (P_n : n \in \omega) associated to a formula \phi(x; y), introduced in [5], is defined by P_n(y1, . . . yn) = \exists x (\bigwedge_{i\leq n} \phi(x;y_i)). We continue the study of characteristic sequences, showing that graph-theoretic techniques, notably Szemer\'edi's celebrated regularity lemma, can be naturally applied to the study of model-theoretic complexity via the characteristic sequence. Specifically, we relate classification-theoretic properties of \phi and of the P_n (considered as formulas) to density between components in Szemer\'edi-regular decompositions of graphs in the characteristic sequence. In addition, we use Szemer\'edi regularity to calibrate model-theoretic notions of independence by describing the depth of independence of a constellation of sets and showing that certain failures of depth imply Shelah's strong order property SOP3; this sheds light on the interplay of independence and order in unstable theories.

  • M. Malliaris, "Hypergraph sequences as a tool for saturation of ultrapowers," Journal of Symbolic Logic 77, 1 (2012) 195-223. PDF, published version

    Abstract: Let T_1, T_2 be countable first-order theories, M_i a model of T_i, and D any regular ultrafilter on \lambda \geq \aleph_0. A longstanding open problem of Keisler asks when T2 is more complex than T1, as measured by the fact that for any such \lambda and D, M^\lambda/D realizes all types over sets of size at most \lambda. In this paper, building on the author's prior work [11] [12] [13], we show that the relative complexity of first-order theories in Keisler's sense is reflected in the relative graph-theoretic complexity of sequences of hypergraphs associated to formulas of the theory. After reviewing prior work on Keisler's order, we present the new construction in the context of ultrapowers, give various applications to the open question of the unstable classification, and investigate the interaction between theories and regularizing sets. Notably, we show that there is a minimum TP2 theory, and that maximality is implied by the density of certain graph edges (between components arising from Szemeredi-regular decompositions) remaining bounded away from 0 and 1. We also introduce and discuss flexible ultrafilters, a relevant class of regular ultrafilters which reflect the sensitivity of certain unstable (non low) theories to the sizes of regularizing sets, and prove that any ultrafilter which saturates the minimal TP2 theory is flexible.

  • M. Malliaris, "Independence, order, and the interaction of ultrafilters and theories," Annals of Pure and Applied Logic 163, 11 (2012) 1580-1595. [Gödel Research Prize Fellowship] PDF, science direct

    Abstract: We consider the question, of longstanding interest, of realizing types in regular ultrapowers. In particular, this is a question about the interaction of ultrafilters and theories, which is both coarse and subtle. It suffices to consider types given by instances of a single formula. In this article, we analyze a class of formulas \phi whose associated characteristic sequence of hypergraphs can be seen as describing both realization of first- and second-order types in ultrapowers as well as properties of the corresponding ultrafilters. These formulas act, via the characteristic sequence, as points of contact with the ultrafilter D, in the sense that they translate structural properties of ultrafilters into model-theoretically meaningful properties and vice versa. Such formulas characterize saturation for various key theories (the theory of the random graph T_{rg}, the theory of a parametrized family of independent equivalence relations T_{feq}), yet their scope in the order \trianglelefteq does not extend beyond T_{feq}. The proof applies Shelah's classification of second-order quantifiers.

  • M. Malliaris and S. Shelah, "Regularity lemmas for stable graphs.'' Trans. Amer. Math. Soc., 366 (2014), 1551-1585. PDF, journal link

    Abstract: We develop a framework in which Szemer\'edi's celebrated Regularity Lemma for graphs interacts with core model-theoretic ideas and techniques. Our work relies on a coincidence of ideas from model theory and graph theory: arbitrarily large half-graphs coincide with model-theoretic instability, so in their absence, structure theorems and technology from stability theory apply. In one direction, we address a problem from the classical Szemer\'edi theory. It was known that the 'irregular pairs' in the statement of Szemer\'edi's regularity lemma cannot be eliminated, due to the counterexample of half-graphs (i.e., the order property). We show that half-graphs are the only essential difficulty, by giving a much stronger version of Szemer\'edi's regularity lemma for stable graphs, in which there are no irregular pairs, the bounds are significantly improved, and each component satisfies an indivisibility condition. In the other direction, we take a more model-theoretic approach, and give several new Szemer\'edi-type partition theorems for graphs with the non-k_*-order property. The first theorem gives a partition of any stable graph into indiscernible components (i.e., each component is either a complete or an empty graph) whose interaction is strongly uniform. To prove this, we first give a finitary version of the classic model-theoretic fact that stable theories admit large sets of indiscernibles, by showing that in finite stable graphs one can extract much larger indiscernible sets than expected by Ramsey's theorem. The second and third theorems allow for a much smaller number of components at the cost of weakening the 'indivisibility' condition on the components. We also discuss some extensions to graphs without the independence property. All graphs are finite and all partitions are equitable, i.e. the sizes of the components differ by at most 1. In the last three theorems, the number of components depends on the size of the graph; in the first theorem quoted, this number is a function of \epsilon only, as in the usual Szemer\'edi regularity lemma.

  • M. Malliaris and S. Shelah, "Constructing regular ultrafilters from a model-theoretic point of view." Trans. Amer. Math. Soc. 367 (2015), 8139--8173. PDF, arxiv, link to journal version

    Abstract: This paper contributes to the set-theoretic side of understanding Keisler's order. We consider properties of ultrafilters which affect saturation of unstable theories: the lower cofinality \lcf(\aleph_0, D) of \aleph_0 modulo D, saturation of the minimum unstable theory (the random graph), flexibility, goodness, goodness for equality, and realization of symmetric cuts. We work in ZFC except when noted, as several constructions appeal to complete ultrafilters thus assume a measurable cardinal. The main results are as follows. First, we investigate the strength of flexibility, known to be detected by non-low theories. Assuming \kappa > \aleph_0 is measurable, we construct a regular ultrafilter on \lambda \geq 2^\kappa which is flexible (thus: ok) but not good, and which moreover has large \lcf(\aleph_0) but does not even saturate models of the random graph. This implies (a) that flexibility alone cannot characterize saturation of any theory, however (b) by separating flexibility from goodness, we remove a main obstacle to proving non-low does not imply maximal, and (c) from a set-theoretic point of view, consistently, ok need not imply good, addressing a problem from Dow 1985. Under no additional assumptions, we prove that there is a loss of saturation in regular ultrapowers of unstable theories, and give a new proof that there is a loss of saturation in ultrapowers of non-simple theories. More precisely, for D regular on \kappa and M a model of an unstable theory, M^\kappa/D is not (2^\kappa)^+-saturated; and for M a model of a non-simple theory and \lambda = \lambda^{<\lambda}, M^\lambda/D is not \lambda^{++}-saturated. Finally, we investigate realization and omission of symmetric cuts, significant both because of the maximality of the strict order property in Keisler's order, and by recent work of the authors on SOP_2. We prove that if D is a \kappa-complete ultrafilter on \kappa, any ultrapower of a sufficiently saturated model of linear order will have no (\kappa, \kappa)-cuts, and that if \de is also normal, it will have a (\kappa^+, \kappa^+)-cut. We apply this to prove that for any n < \omega, assuming the existence of n measurable cardinals below \lambda, there is a regular ultrafilter D on \lambda such that any D-ultrapower of a model of linear order will have n alternations of cuts. Moreover, D will \lambda^+-saturate all stable theories but will not (2^{\kappa})^+-saturate any unstable theory, where \kappa is the smallest measurable cardinal used in the construction.

  • M. Malliaris and S. Shelah, "Model-theoretic properties of ultrafilters built by independent families of functions." J Symb Logic 79, 1 (2014) 103-134. PDF, journal

    Abstract: Via two short proofs and three constructions, we show how to increase the model-theoretic precision of a widely used method for building ultrafilters. We begin by showing that any flexible regular ultrafilter makes the product of an unbounded sequence of finite cardinals large, and then prove directly that a ``bottleneck'' in the inductive construction of a regular ultrafilter on \lambda (i.e. a point after which all antichains of P(\lambda)/D have cardinality less than \lambda) essentially prevents any subsequent ultrafilter from being flexible, \emph{thus} from saturating any non-low theory. The constructions are as follows. First, we construct a regular filter D on \lambda so that any ultrafilter extending D fails to $\lambda^+$-saturate ultrapowers of the random graph, \emph{thus} of any unstable theory. The proof constructs the omitted random graph type directly. Second, assuming existence of a measurable cardinal $\kappa$, we construct a regular ultrafilter on $\lambda > \kappa$ which is $\lambda$-flexible but not $\kappa^{++}$-good, improving our previous answer to a question raised in Dow 1975. Third, assuming a weakly compact cardinal $\kappa$, we construct an ultrafilter to show that $\lcf(\aleph_0)$ may be small while all symmetric cuts of cofinality $\kappa$ are realized. Thus certain families of pre-cuts may be realized while still failing to saturate any unstable theory. Our methods advance the general problem of constructing ultrafilters whose ultrapowers have a precise degree of saturation.

  • M. Malliaris and S. Shelah, "A dividing line within simple unstable theories." Advances in Math 249 (2013) 250--288. PDF, journal

    Abstract: We give the first (ZFC) dividing line in Keisler's order among the unstable theories, specifically among the simple unstable theories. That is, for any infinite cardinal \lambda for which there is \mu < \lambda \leq 2^\mu, we construct a regular ultrafilter D on \lambda such that (i) for any model M of a stable theory or of the random graph, M^\lambda/D is \lambda^+-saturated but (ii) if Th(N) is not simple or not low then N^\lambda/D is not \lambda^+-saturated. The non-saturation result relies on the notion of flexible ultrafilters. To prove the saturation result we develop a property of a class of simple theories, called Qr1, generalizing the fact that whenever B is a set of parameters in some sufficiently saturated model of the random graph, |B| = \lambda and \mu < \lambda \leq 2^\mu, then there is a set A with |A| = \mu such that any nonalgebraic p \in S(B) is finitely realized in A. In addition to giving information about simple unstable theories, our proof reframes the problem of saturation of ultrapowers in several key ways. We give a new characterization of good filters in terms of ``excellence,'' a measure of the accuracy of the quotient Boolean algebra. We introduce and develop the notion of {moral} ultrafilters on Boolean algebras. We prove a so-called ``separation of variables'' result which shows how the problem of constructing ultrafilters to have a precise degree of saturation may be profitably separated into a more set-theoretic stage, building an excellent filter, followed by a more model-theoretic stage: building moral ultrafilters on the quotient Boolean algebra, a process which highlights the complexity of certain patterns, arising from first-order formulas, in certain Boolean algebras.

  • M. Malliaris and S. Shelah, "Saturating the random graph with an independent family of small range." In Logic Without Borders. Paper: arxiv

    Abstract: Motivated by Keisler's order, a far-reaching program of understanding basic model-theoretic structure through the lens of regular ultrapowers, we prove that for a class of regular filters D on I, |I| = \lambda > \aleph_0, the fact that P(I)/D has little freedom (as measured by the fact that any maximal antichain is of size <\lambda, or even countable) does not prevent extending D to an ultrafilter D_1 on I which saturates ultrapowers of the random graph. "Saturates" means that M^I/D_1 is (\lambda^+)-saturated whenever M is a model of the random graph. This was known to be true for stable theories, and false for non-simple and non-low theories. This result and the techniques introduced in the proof have catalyzed the authors' subsequent work on Keisler's order for simple unstable theories. The introduction, which includes a part written for model theorists and a part written for set theorists, discusses our current program and related results.

  • M. Malliaris and S. Shelah, "Cofinality spectrum theorems in model theory, set theory and general topology." J. Amer. Math. Soc. 29 (2016), 237--297. PDF, arxiv, journal

    Abstract: We connect and solve two longstanding open problems in quite different areas: the model-theoretic question of whether $SOP_2$ is maximal in Keisler's order, and the question from set theory/general topology of whether $\mathfrak{p} = \mathfrak{t}$, the oldest problem on cardinal invariants of the continuum. We do so by showing these problems can be translated into instances of a more fundamental problem which we state and solve completely, using model-theoretic methods.

  • M. Malliaris and S. Shelah, "General topology meets model theory: on $\mathfrak{p}$ and $\mathfrak{t}$." Research announcement. PNAS 2013 110 (33) 13300-13305. PDF, journal

    Abstract: Cantor proved in 1874 that the continuum is uncountable, and Hilbert's first problem asks whether it is the smallest uncountable cardinal. A program arose to study cardinal invariants of the continuum, which measure the size of the continuum in various ways. By work of Godel and of Cohen, Hilbert's first problem is independent of ZFC (Zermelo-Fraenkel set theory with the axiom of choice). Much work both before and since has been done on inequalities between these cardinal invariants, but some basic questions have remained open despite Cohen's introduction of forcing. The oldest and perhaps most famous of these is whether ''\mathfrak{p} = \mathfrak{t}'' which was proved in a special case by Rothberger (1948), building on Hausdorff (1936). In this paper we explain how our work on the structure of Keisler's order, a large-scale classification problem in model theory, led to the solution of this problem in ZFC as well as of an a priori unrelated open question in model theory.

  • M. Malliaris and S. Shelah, "Existence of optimal ultrafilters and the fundamental complexity of simple theories." Advances in Math 290 (2016) 614-681. journal, arxiv, new pdf

    Abstract: In the first edition of Classification Theory, the second author characterized the stable theories in terms of saturation of ultrapowers. Prior to this theorem, stability had already been defined in terms of counting types, and the unstable formula theorem was known. A contribution of the ultrapower characterization was that it involved sorting out the global theory, and introducing nonforking, seminal for the development of stability theory. Prior to the present paper, there had been no such characterization of an unstable class. In the present paper, we first establish the existence of so-called optimal ultrafilters on Boolean algebras, which are to simple theories as Keisler's good ultrafilters are to all theories. Then, assuming a supercompact cardinal, we characterize the simple theories in terms of saturation of ultrapowers. To do so, we lay the groundwork for analyzing the global structure of simple theories, in ZFC, via complexity of certain amalgamation patterns. This brings into focus a fundamental complexity in simple unstable theories having no real analogue in stability.

  • M. Malliaris and S. Shelah, "Model-theoretic applications of cofinality spectrum problems." Israel J. Math. 220 (2017), no. 2, 947-1014. arxiv, journal

    Abstract: We apply the recently developed technology of cofinality spectrum problems to prove a range of theorems in model theory. First, we prove that any model of Peano arithmetic is lambda-saturated iff it has cofinality at least lambda and the underlying order has no (kappa, kappa)-cuts for regular kappa strictly less than lambda. Second, assuming instances of GCH, we prove that SOP2 characterizes maximality in the interpretability order trianglestar, settling a prior conjecture and proving that SOP2 is a real dividing line. Third, we establish the beginnings of a structure theory for NSOP2, proving that NSOP2 can be characterized by the existence of few inconsistent higher formulas. In the course of the paper, we show that \mathfrak{p}_s = \mathfrak{t}_s in any weak cofinality spectrum problem closed under exponentiation (naturally defined). We also prove that the local versions of these cardinals need not coincide, even in cofinality spectrum problems arising from Peano arithmetic.

  • M. Malliaris and A. Pillay, "The stable regularity lemma revisited." Proc. Amer. Math. Soc. 144 (2016), no. 4, 1761--1765. arxiv, journal

    Abstract: We prove a regularity lemma with respect to arbitrary Keisler measures mu on V, nu on W where the bipartite graph (V,W,R) is definable in a saturated structure M and the formula R(x,y) is stable. The proof is rather quick and uses local stability theory. The special case where (V,W,R) is pseudofinite, mu, nu are the counting measures and M is suitably chosen (for example a nonstandard model of set theory), yields the Malliaris-Shelah stable regularity lemma though without explicit bounds or equitability.

  • M. Malliaris and S. Shelah, "Keisler's order has infinitely many classes." Israel J. Math. 224 (2018), no. 1, 189–230. pdf, journal

    Abstract: We prove, in ZFC, that there is an infinite strictly descending chain of classes of theories in Keisler's order. Thus Keisler's order is infinite and not a well order. Moreover, this chain occurs within the simple unstable theories, considered model-theoretically tame. Keisler's order is a central notion of the model theory of the 60s and 70s which compares first-order theories (and implicitly ultrafilters) according to saturation of ultrapowers. Prior to this paper, it was long thought to have finitely many classes, linearly ordered. The model-theoretic complexity we find is witnessed by a very natural class of theories, the n-free k-hypergraphs studied by Hrushovski. This complexity reflects the difficulty of amalgamation and appears orthogonal to forking.

  • M. Malliaris and S. Shelah, "Open problems on ultrafilters and some connections to the continuum." In Contemporary Mathematics Volume 690, 2017. PDF

    Abstract: We discuss a range of open problems at the intersection of set theory, model theory, and general topology, mainly around the construction of ultrafilters. Along the way we prove uniqueness for a weak notion of cut.

  • M. Malliaris and S. Shelah, "Cofinality spectrum problems: the axiomatic approach." Topology Appl. 213 (2016), 50-79. PDF, mathscinet

    Abstract: Our investigations are framed by two overlapping problems: finding the right axiomatic framework for so-called cofinality spectrum problems, and a 1985 question of Dow on the conjecturally nonempty (in ZFC) region of OK but not good ultrafilters. We define the lower-cofinality spectrum for a regular ultrafilter \de on \lambda and show that this spectrum may consist of a strict initial segment of cardinals below \lambda and also that it may finitely alternate. We define so-called `automorphic ultrafilters' and prove that the ultrafilters which are automorphic for some, equivalently every, unstable theory are precisely the good ultrafilters. We axiomatize a bare-bones framework called ''lower cofinality spectrum problems'', consisting essentially of a single tree projecting onto two linear orders. We prove existence of a lower cofinality function in this context and show by example that it holds of certain theories whose model theoretic complexity is bounded.

  • M. Malliaris and C. Terry, "On unavoidable induced subgraphs in large prime graphs." J. Graph Theory, Volume 88, Issue 2 (June 2018), pps. 255-270. journal, arxiv

    Abstract: Chudnovsky, Kim, Oum, and Seymour recently established that any prime graph contains one of a short list of induced prime subgraphs. In the present paper we reprove their theorem using many of the same ideas, but with the key model-theoretic ingredient of first determining the so-called amount of stability of the graph. This approach changes the applicable Ramsey theorem, improves the bounds and offers a different structural perspective on the graphs in question. Complementing this, we give an infinitary proof which implies the finite result.

  • M. Malliaris, "The clique covering problem and other questions." In a special issue of J. Logics and Applications, vol. 4, issue 10, November 2017, devoted to the Godel research prize fellowships, guest editor, Matthias Baaz. link (see page 3411)

    Abstract: Mainly expository paper discussing two open problems, written for a commemoration of the Godel prize fellowships.

  • D. Casey and M. Malliaris, "Notes on cofinality spectrum problems." arxiv

    Abstract: These notes are based on Appalachian Set Theory lectures given by M. Malliaris on November 5, 2016 with D. Casey as the official scribe. The aim of the lectures was to present the setup and some key arguments of "Cofinality spectrum problems in model theory, set theory and general topology" by Malliaris and Shelah. This provides a sketch of the proof that p=t and that SOP2 theories are maximal in Keisler's order.

  • M. Malliaris and S. Shelah, "A new look at interpretability and saturation." Ann Pure Appl Logic 170, 5 (2019) 642-671. arxiv, journal

    Abstract: We investigate the interpretability ordering $\trianglelefteq^*$ using generalized Ehrenfeucht-Mostowski models. This gives a new approach to proving inequalities and investigating the structure of types.

  • M. Malliaris and A. Peretz, "What simplicity is not." Simplicity: ideals of practice in mathematics and the arts. 51–58, Math. Cult. Arts, Springer, Cham, 2017. link

  • M. Malliaris, "Model theory and ultraproducts." Proceedings of the 2018 ICM, Rio de Janeiro. arxiv, link to book

    Abstract: The article motivates saturation of ultrapowers from a general mathematical point of view.

  • M. Malliaris and S. Shelah, "An example of a new simple theory." Contemporary Mathematics volume 752, 2020, pps. 121-152. arxiv.

    Abstract: We construct a countable simple theory which, in Keisler's order, is strictly above the random graph and also in some sense orthogonal to the building blocks of the recently discovered infinite descending chain. As a result we prove in ZFC that there are incomparable classes in Keisler's order.

  • N. Alon, R. Livni, M. Malliaris, S. Moran. "Private PAC learning implies finite Littlestone dimension." 51st Symposium on the Theory of Computing (STOC), 2019. arxiv

    Abstract: We show that every approximately differentially private learning algorithm (possibly improper) for a class H with Littlestone dimension~d requires Ω(log*(d)) examples. As a corollary it follows that the class of thresholds over N can not be learned in a private manner; this resolves open question due to [Bun et al., 2015, Feldman and Xiao, 2015]. We leave as an open question whether every class with a finite Littlestone dimension can be learned by an approximately differentially private algorithm.

  • M. Malliaris and S. Shelah. "A separation theorem for simple theories." Trans. Amer. Math. Soc. 375 (2022), 1171-1205. arxiv, journal

    Abstract: 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. We prove a separation theorem showing that for any countable context c 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 the language of T1 is mu-saturated and whose restriction to the language of T2 is not (aleph_1)-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.

  • M. Malliaris and S. Shelah. "Keisler's order is not simple (and simple theories may not be either)." Advances in Mathematics 392 (2021) paper 108036, 94pp. arxiv, journal

    Abstract: Solving a decades-old problem we show that Keisler's 1967 order on theories has the maximum number of classes. The theories we build are simple unstable with no nontrivial forking, and reflect growth rates of sequences which may be thought of as densities of certain regular pairs, in the sense of Szemerédi's regularity lemma. The proof involves ideas from model theory, set theory, and finite combinatorics.

  • M. Malliaris and S. Shelah. "Notes on the stable regularity lemma." Bull. Symb. Log. 27 (2021), no. 4, 415–425. arxiv, journal

    Abstract: This is a short expository account of the regularity lemma for stable graphs proved by the authors, with some comments on the model theoretic context, written for a general logical audience.

  • M. Malliaris and A. Peretz. "Realizing infinity." Based on a lecture at 'On the Infinite: An Interdisciplinary Symposium,' IHP/Sorbonne. Forthcoming. arxiv

  • P. Diaconis and M. Malliaris. "Complexity and randomness in the Heisenberg groups (and beyond)." New Zealand J. Math. 52 (2021), 403-426. journal, arxiv

    Abstract: By studying the commuting graphs of conjugacy classes of the sequence of Heisenberg groups $H_{2n+1}(p)$ and their limit $H_\infty(p)$ we find pseudo-random behavior (and the random graph in the limiting case). This makes a nice case study for transfer of information between finite and infinite objects. Some of this behavior transfers to the problem of understanding what makes understanding the character theory of the uni-upper-triangular group (mod p) "wild". Our investigations in this paper may be seen as a meditation on the question: is randomness simple or is it complicated?

  • M. Malliaris and S. Shelah. "Some simple theories from a Boolean algebra point of view." to appear, Annals of Pure and Applied Logic. journal, arxiv 2021.

    Abstract: We find a strong separation between two natural families of simple rank one theories in Keisler's order: the theories Tm reflecting graph sequences, which witness that Keisler's order has the maximum number of classes, and the theories Tn,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.

  • M. Malliaris and S. Shelah. "New simple theories from hypergraph sequences." to appear, Model Theory [in Special Issue for Boris Zilber's 75th]. arxiv 2021.

    Abstract: We develop a family of simple rank one theories built over quite arbitrary sequences of finite hypergraphs. (This extends an idea from the recent proof that Keisler's order has continuum many classes, however, the construction does not require familiarity with the earlier proof.) We prove a model-completion and quantifier-elimination result for theories in this family. We develop a combinatorial property which they share. We invoke regular ultrafilters to show the strength of this property, showing that any flexible ultrafilter which is good for the random graph is able to saturate such theories.

  • M. Malliaris and S. Moran. "Agnostic online learning and excellent sets." arxiv 2021.

    Abstract: We revisit a key idea from the interaction of model theory and combinatorics, the existence of large ``indivisible'' sets, called ``epsilon-excellent,'' in k-edge stable graphs (equivalently, Littlestone classes). Translating to the language of probability, we find a quite different existence proof for epsilon-excellent sets in Littlestone classes, using regret bounds in online learning. This proof applies to any epsilon less than one-half, compared to less than one over two to the two to the k or so in the original proof. We include a second proof using closure properties and the VC theorem, with other advantages but weaker bounds. As a simple corollary, the Littlestone dimension remains finite under some natural modifications to the definition. A theme in these proofs is the interaction of two abstract notions of majority, arising from measure, and from rank or dimension; we prove that these densely often coincide and that this is characteristic of Littlestone (stable) classes. The last section lists several open problems.

  • M. Malliaris and S. Shelah. "Shearing in some simple rank one theories." To appear, Israel J. Math. arxiv 2021.

    Abstract: 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.

  • M. Malliaris and S. Shelah. "The Turing degrees and Keisler's order." Journal of Symbolic Logic, 1-11 (2022). journal, pdf

    Abstract: There is a Turing functional Phi taking A′ to a theory TA whose complexity is exactly that of the jump of A, and which has the property that A is Turing-reducible to B if and only if TA is below TB in Keisler’s order. In fact, by more elaborate means and related theories, we may keep the complexity at the level of A without using the jump.

  • M. Malliaris. "Notes on model theory and complexity." For the proceedings of the 2019 CLMPST.

    Abstract: The aim is to provide some background and intuition for Keisler’s order on theories, complementing a talk of the author at the Congress in 2019 which discussed the recent theorem of Malliaris and Shelah that Keisler’s order has the maximum number of classes.

  • N. Alon, M. Bun, R. Livni, M. Malliaris, and S. Moran. "Private and online learnability are equivalent." J. ACM, 2022. journal

    Abstract: Let H be a binary-labelled concept class. We prove that H can be PAC-learned by an (approximate) differentially-private algorithm if and only if it has a finite Littlestone dimension. This implies a qualitative equivalence between online learnability and private PAC learnability.

  • L. N. Coregliano and M. Malliaris. "Countable Ramsey." arxiv 74 pages, 2022.

    Abstract: The celebrated Erdős-Hajnal Conjecture says that in any proper hereditary class of finite graphs we are guaranteed to have a clique or anti-clique of size $n^c$, which is a much better bound than the logarithmic size that is provided by Ramsey's Theorem in general. On the other hand, in uncountable cardinalities, the model-theoretic property of stability guarantees a uniform set much larger than the bound provided by the Erdős-Rado Theorem in general.

    Even though the consequences of stability in the finite have been much studied in the literature, the countable setting seems a priori quite different, namely, in the countably infinite the notion of largeness based on cardinality alone does not reveal any structure as Ramsey's Theorem already provides a countably infinite uniform set in general. In this paper, we show that the natural notion of largeness given by upper density reveals that these phenomena meet in the countable: a countable graph has an almost clique or anti-clique of positive upper density if and only if it has a positive upper density almost stable set. Moreover, this result also extends naturally to countable models of a universal theory in a finite relational language.

    Our methods explore a connection with the notion of convergence in the theory of limits of dense combinatorial objects, introducing and studying a natural approximate version of the Erdős-Hajnal property that allows for a negligible error in the edges (in general, predicates) but requires linear-sized uniform sets in convergent sequences of models (this is much stronger than what stable regularity can provide as the error is required to go to zero). Finally, surprisingly, we completely characterize all hereditary classes of finite graphs that have this approximate Erdős-Hajnal property. The proof highlights both differences and similarities with the original conjecture.

  • L. N. Coregliano and M. Malliaris. "Weak randomness in graphons and theons." arxiv 62 pages, 2022.

    Abstract: Call a hereditary family F of graphs strongly persistent if there exists a graphon W such that in all subgraphons W′ of W, F is precisely the class of finite graphs that have positive density in W′.

    The first result of the paper is a complete characterization of the hereditary families of graphs that are strongly persistent as precisely those that are closed under substitutions. In fact, we prove an analogous characterization for the natural extension of these properties to structures in finite relational languages.

    We call graphons (or more generally theons) with the self-similarity property above weakly random. Weak randomness can be seen as a weakening of graph quasirandomness: while the latter requires densities of any finite graph to be the same in any subgraphon, the former only requires the set of finite graphs with positive density to be invariant across subgraphons. A hereditary family F is said to have the weakly random Erdős--Hajnal property (WR) if every graphon that is a limit of graphs in F has a weakly random subgraphon; this includes as a special case the approximate Erdős--Hajnal property (AEHP), where the subgraphon is required to be an almost clique or almost anti-clique. Among families of graphs that are closed under substitutions, we completely characterize the families that belong to WR as those with "few" prime graphs.

    The classes AEHP and WR can be seen as measuring the complexity of hereditary families in terms of structural variation in their limit objects (here specifically in terms of unavoidable sub-objects), and this work can be seen as initiating a classification theory for hereditary families of finite structures.

  • M. Malliaris and S. Moran. "The unstable formula theorem revisited via algorithms." arxiv 21 pages, 2022.

    Abstract: This paper is about the surprising interaction of a foundational result from model theory about stability of theories, which seems to be inherently about the infinite, with algorithmic stability in learning. Specifically, we develop a complete algorithmic analogue of Shelah's celebrated Unstable Formula Theorem, with algorithmic properties taking the place of the infinite. This draws on several new theorems as well as much recent work. In particular we introduce a new "Probably Eventually Correct" learning model, of independent interest, and characterize Littlestone (stable) classes in terms of this model; and we describe Littlestone classes via approximations, by analogy to definability of types in model theory.


    Contact information:
    Department of Mathematics
    University of Chicago
    5734 S. University Avenue
    Chicago, IL 60637

    back to main page

  • space