Abstract: We show that the analysis of Keisler's order can be localized to the study of \phitypes. 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 \phitypes over sets of size \lambda.
Abstract: This article introduces and develops the theory of characteristic sequences. For a firstorder 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.
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 graphtheoretic techniques, notably Szemer\'edi's celebrated regularity lemma, can be naturally applied to the study of modeltheoretic complexity via the characteristic sequence. Specifically, we relate classificationtheoretic properties of \phi and of the P_n (considered as formulas) to density between components in Szemer\'ediregular decompositions of graphs in the characteristic sequence. In addition, we use Szemer\'edi regularity to calibrate modeltheoretic 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.
Abstract: Let T_1, T_2 be countable firstorder 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 firstorder theories in Keisler's sense is reflected in the relative graphtheoretic 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 Szemerediregular 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.
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 secondorder 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 modeltheoretically 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 secondorder quantifiers.
Abstract: We develop a framework in which Szemer\'edi's celebrated Regularity Lemma for graphs interacts with core modeltheoretic ideas and techniques. Our work relies on a coincidence of ideas from model theory and graph theory: arbitrarily large halfgraphs coincide with modeltheoretic 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 halfgraphs (i.e., the order property). We show that halfgraphs 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 modeltheoretic approach, and give several new Szemer\'editype partition theorems for graphs with the nonk_*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 modeltheoretic 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.
Abstract: This paper contributes to the settheoretic 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 nonlow 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 nonlow does not imply maximal, and (c) from a settheoretic 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 nonsimple 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 nonsimple 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 \kappacomplete 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 Dultrapower 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.
Abstract: Via two short proofs and three constructions, we show how to increase the modeltheoretic 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 nonlow 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 precuts 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.
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 nonsaturation 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 socalled ``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 settheoretic stage, building an excellent filter, followed by a more modeltheoretic stage: building moral ultrafilters on the quotient Boolean algebra, a process which highlights the complexity of certain patterns, arising from firstorder formulas, in certain Boolean algebras.
Abstract: Motivated by Keisler's order, a farreaching program of understanding basic modeltheoretic 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 nonsimple and nonlow 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.
Abstract: We connect and solve two longstanding open problems in quite different areas: the modeltheoretic 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 modeltheoretic methods.
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 (ZermeloFraenkel 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 largescale 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.
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 socalled 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.
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 lambdasaturated 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.
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 MalliarisShelah stable regularity lemma though without explicit bounds or equitability.
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 modeltheoretically tame. Keisler's order is a central notion of the model theory of the 60s and 70s which compares firstorder 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 modeltheoretic complexity we find is witnessed by a very natural class of theories, the nfree khypergraphs studied by Hrushovski. This complexity reflects the difficulty of amalgamation and appears orthogonal to forking.
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.
Abstract: Our investigations are framed by two overlapping problems: finding the right axiomatic framework for socalled 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 lowercofinality 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 socalled `automorphic ultrafilters' and prove that the ultrafilters which are automorphic for some, equivalently every, unstable theory are precisely the good ultrafilters. We axiomatize a barebones 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.
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 modeltheoretic ingredient of first determining the socalled 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.
Abstract: Mainly expository paper discussing two open problems, written for a commemoration of the Godel prize fellowships.
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.
Abstract: We investigate the interpretability ordering $\trianglelefteq^*$ using generalized EhrenfeuchtMostowski models. This gives a new approach to proving inequalities and investigating the structure of types.
Abstract: The article motivates saturation of ultrapowers from a general mathematical point of view.
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.
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.
Abstract: This paper builds modeltheoretic tools to detect changes in complexity among the simple theories. We develop a generalization of dividing, called shearing, which depends on a socalled context c. This leads to defining csuperstability, 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 csuperstable and T2 is cunsuperstable, 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 musaturated and whose restriction to the language of T2 is not (aleph_1)saturated. (This suggests "csuperstable" is really a dividing line.) The proof uses generalized EhrenfeuchtMostowski 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.
Abstract: Solving a decadesold 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.
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.
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 pseudorandom 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 uniuppertriangular 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?
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 higherorder analogues of the trianglefree 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.
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 modelcompletion and quantifierelimination 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.
Abstract: We revisit a key idea from the interaction of model theory and combinatorics, the existence of large ``indivisible'' sets, called ``epsilonexcellent,'' in kedge stable graphs (equivalently, Littlestone classes). Translating to the language of probability, we find a quite different existence proof for epsilonexcellent sets in Littlestone classes, using regret bounds in online learning. This proof applies to any epsilon less than onehalf, 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.
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 higherorder analogues of the trianglefree 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.
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 Turingreducible 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.
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.
Abstract: Let H be a binarylabelled concept class. We prove that H can be PAClearned by an (approximate) differentiallyprivate algorithm if and only if it has a finite Littlestone dimension. This implies a qualitative equivalence between online learnability and private PAC learnability.
Abstract: The celebrated ErdősHajnal Conjecture says that in any proper hereditary class of finite graphs we are guaranteed to have a clique or anticlique 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 modeltheoretic property of stability guarantees a uniform set much larger than the bound provided by the ErdősRado 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 anticlique 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ősHajnal property that allows for a negligible error in the edges (in general, predicates) but requires linearsized 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ősHajnal property. The proof highlights both differences and similarities with the original conjecture.
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.
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 selfsimilarity 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ősHajnal 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ősHajnal property (AEHP), where the subgraphon is required to be an almost clique or almost anticlique. 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 subobjects), and this work can be seen as initiating a classification theory for hereditary families of finite structures.
Abstract: We develop a theory of higharity PAC learning, which is statistical learning in the presence of "structured correlation". In this theory, hypotheses are either graphs, hypergraphs or, more generally, structures in finite relational languages, and i.i.d. sampling is replaced by sampling an induced substructure, producing an exchangeable distribution. Our main theorems establish a higharity (agnostic) version of the fundamental theorem of statistical learning.
.
 space 
