Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Ramsey theory
Summary
Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of the mathematical field of combinatorics that focuses on the appearance of order in a substructure given a structure of a known size. Problems in Ramsey theory typically ask a question of the form: "how big must some structure be to guarantee that a particular property holds?"
A typical result in Ramsey theory starts with some mathematical structure that
is then cut into pieces. How big must the original structure be in order to ensure that at least one of the pieces has a given interesting property? This idea can be defined as partition regularity.
For example, consider a complete graph of order n; that is, there are n vertices and each vertex is connected to every other vertex by an edge. A complete graph of order 3 is called a triangle. Now colour each edge either red or blue. How large must n be in order to ensure that there is either a blue triangle or a red triangle? It turns out that the answer is 6. See the article on Ramsey's theorem for a rigorous proof.
Another way to express this result is as follows: at any party with at least six people, there are three people who are all either mutual acquaintances (each one knows the other two) or mutual strangers (none of them knows either of the other two). See theorem on friends and strangers.
This also is a special case of Ramsey's theorem, which says that for any given integer c, any given integers n1,...,nc, there is a number, R(n1,...,nc), such that if the edges of a complete graph of order R(n1,...,nc) are coloured with c different colours, then for some i between 1 and c, it must contain a complete subgraph of order ni whose edges are all colour i. The special case above has c = 2 and n1 = n2 = 3.
Two key theorems of Ramsey theory are:
Van der Waerden's theorem: For any given c and n, there is a number V, such that if V consecutive numbers are coloured with c different colours, then it must contain an arithmetic progression of length n whose elements are all the same colour.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related courses (2)
MATH-360: Graph theory
The course aims to introduce the basic concepts and results of modern Graph Theory with special emphasis on those topics and techniques that have proved to be applicable in theoretical computer scienc
MATH-337: Number theory I.c - Combinatorial number theory
This is an introductory course to combinatorial number theory. The main objective of this course is to learn how to use combinatorial, topological, and analytic methods to solve problems in number the
Related lectures (4)
Ramsey Theory: Alterations and Colorings
Explores Ramsey theory, alterations, colorings in graphs, monochromatic matchings, and the significance of large cliques.
Graph Theory Basics
Introduces graph theory basics, Ramsey theory, and graph coloring concepts.
Chemical Engineering of Heterogeneous Reactions
Explores observed rates in heterogeneous reactions, internal mass transfer impact, reaction kinetics, Arrhenius equation, and heat transfer effects.
Related publications (8)
Related people (1)
Related concepts (5)
Ramsey's theorem
In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (say, blue and red), let r and s be any two positive integers. Ramsey's theorem states that there exists a least positive integer R(r, s) for which every blue-red edge colouring of the complete graph on R(r, s) vertices contains a blue clique on r vertices or a red clique on s vertices.
Clique (graph theory)
In the mathematical area of graph theory, a clique (ˈkliːk or ˈklɪk) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph is an induced subgraph of that is complete. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science: the task of finding whether there is a clique of a given size in a graph (the clique problem) is NP-complete, but despite this hardness result, many algorithms for finding cliques have been studied.
Independent set (graph theory)
In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set of vertices such that for every two vertices in , there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in . A set is independent if and only if it is a clique in the graph's complement. The size of an independent set is the number of vertices it contains. Independent sets have also been called "internally stable sets", of which "stable set" is a shortening.