Extremal combinatorics is a field of

combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ...

, which is itself a part of

mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

. Extremal combinatorics studies how large or how small a collection of finite objects (

number A number is a mathematical object used to count, measure, and label. The most basic examples are the natural numbers 1, 2, 3, 4, and so forth. Numbers can be represented in language with number words. More universally, individual numbers can ...

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discret ...

vector Vector most often refers to: * Euclidean vector, a quantity with a magnitude and a direction * Disease vector, an agent that carries and transmits an infectious pathogen into another living organism Vector may also refer to: Mathematics a ...

s, sets, etc.) can be, if it has to satisfy certain restrictions. Much of extremal combinatorics concerns

class Class, Classes, or The Class may refer to: Common uses not otherwise categorized * Class (biology), a taxonomic rank * Class (knowledge representation), a collection of individuals or objects * Class (philosophy), an analytical concept used d ...

es of sets; this is called extremal set theory. For instance, in an ''n''-element set, what is the largest number of ''k''-element

subset In mathematics, a Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they a ...

s that can pairwise intersect one another? What is the largest number of subsets of which none contains any other? The latter question is answered by

Sperner's theorem Sperner's theorem, in discrete mathematics, describes the largest possible families of finite sets none of which contain any other sets in the family. It is one of the central results in extremal set theory. It is named after Emanuel Sperner, wh ...

, which gave rise to much of extremal set theory. Another kind of example: How many people can be invited to a party where among each three people there are two who know each other and two who don't know each other?

Ramsey theory 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 R ...

shows that at most five persons can attend such a party (see

Theorem on Friends and Strangers The theorem on friends and strangers is a mathematical theorem in an area of mathematics called Ramsey theory. Statement Suppose a party has six people. Consider any two of them. They might be meeting for the first time—in which case we will ...

). Or, suppose we are given a finite set of nonzero integers, and are asked to mark as large a subset as possible of this set under the restriction that the sum of any two marked integers cannot be marked. It appears that (independent of what the given integers actually are) we can always mark at least one-third of them.

References

*. *. *. * Combinatorial optimization {{combin-stub

See also

References