In mathematics, structural Ramsey theory is a categorical generalisation of Ramsey theory, rooted in the idea that many important results of Ramsey theory have "similar" logical structures. The key observation is noting that these Ramsey-type theorems can be expressed as the assertion that a certain category (or class of finite structures) has the Ramsey property (defined below).
Structural Ramsey theory began in the 1970s [1] with the work of Nešetřil and Rödl, and is intimately connected to Fraïssé theory. It received some renewed interest in the mid-2000s due to the discovery of the Kechris–Pestov–Todorčević correspondence, which connected structural Ramsey theory to topological dynamics.
Leeb is given credit [2] for inventing the idea of a Ramsey property in the early 70s. The first publication of this idea appears to be Graham, Leeb and Rothschild's 1972 paper on the subject. [3] Key development of these ideas was done by Nešetřil and Rödl in their series of 1977 [4] and 1983 [5] papers, including the famous Nešetřil–Rödl theorem. This result was reproved independently by Abramson and Harrington, [6] and further generalised by Prömel . [7] More recently, Mašulović [8] [9] [10] and Solecki [11] [12] [13] have done some pioneering work in the field.
This article will use the set theory convention that each natural number can be considered as the set of all natural numbers less than it: i.e. . For any set , an -colouring of is an assignment of one of labels to each element of . This can be represented as a function mapping each element to its label in (which this article will use), or equivalently as a partition of into pieces.
Here are some of the classic results of Ramsey theory:
These "Ramsey-type" theorems all have a similar idea: we fix two integers and , and a set of colours . Then, we want to show there is some large enough, such that for every -colouring of the "substructures" of size inside , we can find a suitable "structure" inside , of size , such that all the "substructures" of with size have the same colour.
What types of structures are allowed depends on the theorem in question, and this turns out to be virtually the only difference between them. This idea of a "Ramsey-type theorem" leads itself to the more precise notion of the Ramsey property (below).
Let be a category. has the Ramsey property if for every natural number , and all objects in , there exists another object in , such that for every -colouring , there exists a morphism which is -monochromatic, i.e. the set
is -monochromatic. [10]
Often, is taken to be a class of finite -structures over some fixed language , with embeddings as morphisms. In this case, instead of colouring morphisms, one can think of colouring "copies" of in , and then finding a copy of in , such that all copies of in this copy of are monochromatic. This may lend itself more intuitively to the earlier idea of a "Ramsey-type theorem".
There is also a notion of a dual Ramsey property; has the dual Ramsey property if its dual category has the Ramsey property as above. More concretely, has the dual Ramsey property if for every natural number , and all objects in , there exists another object in , such that for every -colouring , there exists a morphism for which is -monochromatic.
In 2005, Kechris, Pestov and Todorčević [14] discovered the following correspondence (hereafter called the KPT correspondence) between structural Ramsey theory, Fraïssé theory, and ideas from topological dynamics.
Let be a topological group. For a topological space , a -flow (denoted ) is a continuous action of on . We say that is extremely amenable if any -flow on a compact space admits a fixed point , i.e. the stabiliser of is itself.
For a Fraïssé structure , its automorphism group can be considered a topological group, given the topology of pointwise convergence, or equivalently, the subspace topology induced on by the space with the product topology. The following theorem illustrates the KPT correspondence:
Theorem (KPT). For a Fraïssé structure , the following are equivalent:
- The group of automorphisms of is extremely amenable.
- The class has the Ramsey property.
In mathematics, and more specifically in linear algebra, a linear map is a mapping between two vector spaces that preserves the operations of vector addition and scalar multiplication. The same names and the same definition are also used for the more general case of modules over a ring; see Module homomorphism.
In probability theory, the central limit theorem (CLT) states that, under appropriate conditions, the distribution of a normalized version of the sample mean converges to a standard normal distribution. This holds even if the original variables themselves are not normally distributed. There are several versions of the CLT, each applying in the context of different conditions.
Distributions, also known as Schwartz distributions or generalized functions, are objects that generalize the classical notion of functions in mathematical analysis. Distributions make it possible to differentiate functions whose derivatives do not exist in the classical sense. In particular, any locally integrable function has a distributional derivative.
In statistics, maximum likelihood estimation (MLE) is a method of estimating the parameters of an assumed probability distribution, given some observed data. This is achieved by maximizing a likelihood function so that, under the assumed statistical model, the observed data is most probable. The point in the parameter space that maximizes the likelihood function is called the maximum likelihood estimate. The logic of maximum likelihood is both intuitive and flexible, and as such the method has become a dominant means of statistical inference.
In the mathematical field of real analysis, the monotone convergence theorem is any of a number of related theorems proving the good convergence behaviour of monotonic sequences, i.e. sequences that are non-increasing, or non-decreasing. In its simplest form, it says that a non-decreasing bounded-above sequence of real numbers converges to its smallest upper bound, its supremum. Likewise, a non-increasing bounded-below sequence converges to its largest lower bound, its infimum. In particular, infinite sums of non-negative numbers converge to the supremum of the partial sums if and only if the partial sums are bounded.
In mathematics, the Laplace operator or Laplacian is a differential operator given by the divergence of the gradient of a scalar function on Euclidean space. It is usually denoted by the symbols , (where is the nabla operator), or . In a Cartesian coordinate system, the Laplacian is given by the sum of second partial derivatives of the function with respect to each independent variable. In other coordinate systems, such as cylindrical and spherical coordinates, the Laplacian also has a useful form. Informally, the Laplacian Δf (p) of a function f at a point p measures by how much the average value of f over small spheres or balls centered at p deviates from f (p).
In mathematics, a self-adjoint operator on a complex vector space V with inner product is a linear map A that is its own adjoint. That is, for all ∊ V. If V is finite-dimensional with a given orthonormal basis, this is equivalent to the condition that the matrix of A is a Hermitian matrix, i.e., equal to its conjugate transpose A∗. By the finite-dimensional spectral theorem, V has an orthonormal basis such that the matrix of A relative to this basis is a diagonal matrix with entries in the real numbers. This article deals with applying generalizations of this concept to operators on Hilbert spaces of arbitrary dimension.
In mathematics, a linear form is a linear map from a vector space to its field of scalars.
In mathematics, an indicator function or a characteristic function of a subset of a set is a function that maps elements of the subset to one, and all other elements to zero. That is, if A is a subset of some set X, then if and otherwise, where is a common notation for the indicator function. Other common notations are and
In vector calculus, Green's theorem relates a line integral around a simple closed curve C to a double integral over the plane region D bounded by C. It is the two-dimensional special case of Stokes' theorem. In one dimension, it is equivalent to the fundamental theorem of calculus. In three dimensions, it is equivalent to the divergence theorem.
In mathematics, the adele ring of a global field is a central object of class field theory, a branch of algebraic number theory. It is the restricted product of all the completions of the global field and is an example of a self-dual topological ring.
In algebraic geometry, a branch of mathematics, Serre duality is a duality for the coherent sheaf cohomology of algebraic varieties, proved by Jean-Pierre Serre. The basic version applies to vector bundles on a smooth projective variety, but Alexander Grothendieck found wide generalizations, for example to singular varieties. On an n-dimensional variety, the theorem says that a cohomology group is the dual space of another one, . Serre duality is the analog for coherent sheaf cohomology of Poincaré duality in topology, with the canonical line bundle replacing the orientation sheaf.
In mathematics, differential algebra is, broadly speaking, the area of mathematics consisting in the study of differential equations and differential operators as algebraic objects in view of deriving properties of differential equations and operators without computing the solutions, similarly as polynomial algebras are used for the study of algebraic varieties, which are solution sets of systems of polynomial equations. Weyl algebras and Lie algebras may be considered as belonging to differential algebra.
This is a glossary of properties and concepts in category theory in mathematics.
The Artin reciprocity law, which was established by Emil Artin in a series of papers, is a general theorem in number theory that forms a central part of global class field theory. The term "reciprocity law" refers to a long line of more concrete number theoretic statements which it generalized, from the quadratic reciprocity law and the reciprocity laws of Eisenstein and Kummer to Hilbert's product formula for the norm symbol. Artin's result provided a partial solution to Hilbert's ninth problem.
In mathematics, Hochschild homology (and cohomology) is a homology theory for associative algebras over rings. There is also a theory for Hochschild homology of certain functors. Hochschild cohomology was introduced by Gerhard Hochschild (1945) for algebras over a field, and extended to algebras over more general rings by Henri Cartan and Samuel Eilenberg (1956).
In mathematics, a space, where is a real number, is a specific type of metric space. Intuitively, triangles in a space are "slimmer" than corresponding "model triangles" in a standard space of constant curvature . In a space, the curvature is bounded from above by . A notable special case is ; complete spaces are known as "Hadamard spaces" after the French mathematician Jacques Hadamard.
In mathematics, a line integral is an integral where the function to be integrated is evaluated along a curve. The terms path integral, curve integral, and curvilinear integral are also used; contour integral is used as well, although that is typically reserved for line integrals in the complex plane.
In extremal graph theory, the forbidden subgraph problem is the following problem: given a graph , find the maximal number of edges an -vertex graph can have such that it does not have a subgraph isomorphic to . In this context, is called a forbidden subgraph.
In mathematics, the hypergraph regularity method is a powerful tool in extremal graph theory that refers to the combined application of the hypergraph regularity lemma and the associated counting lemma. It is a generalization of the graph regularity method, which refers to the use of Szemerédi's regularity and counting lemmas.