Extremal combinatorics

Extremal combinatorics is a field of combinatorics

Combinatorics

Combinatorics is a branch of pure mathematics concerning the study of discrete objects. It is related to many other areas of mathematics, such as algebra, probability theory, ergodic theory and geometry, as well as to applied subjects in computer science and statistical physics...

, which is itself a part of mathematics

Mathematics

Mathematics is the science and study of quantity, structure, space, and change. Mathematicians seek out patterns, formulate new conjectures, and establish truth by rigorous deduction from appropriately chosen axioms and definitions....

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

Number

A number is a mathematical object used in counting and measuring. A notational symbol which represents a number is called a numeral, but in common usage the word number is used for both the abstract object and the symbol, as well as for the word for the number...

s, graph

Graph (mathematics)

In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...

s, vector

Vector space

A vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex...

s, sets, etc.) can be, if it has to satisfy certain restrictions.

For example, how many people can we invite to a party where among each three people there are two who know each other and two who don't know each other? An easy Ramsey-type

Ramsey theory

Ramsey theory, named after Frank P. Ramsey, is a branch of mathematics that studies the conditions under which order must appear. Problems in Ramsey theory typically ask a question of the form: how many elements of some structure must there be to guarantee that a particular property will...

argument shows that at most five persons can attend such a party.

Extremal combinatorics is a field of combinatorics

Combinatorics

Combinatorics is a branch of pure mathematics concerning the study of discrete objects. It is related to many other areas of mathematics, such as algebra, probability theory, ergodic theory and geometry, as well as to applied subjects in computer science and statistical physics...

, which is itself a part of mathematics

Mathematics

Mathematics is the science and study of quantity, structure, space, and change. Mathematicians seek out patterns, formulate new conjectures, and establish truth by rigorous deduction from appropriately chosen axioms and definitions....

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

Number

A number is a mathematical object used in counting and measuring. A notational symbol which represents a number is called a numeral, but in common usage the word number is used for both the abstract object and the symbol, as well as for the word for the number...

s, graph

Graph (mathematics)

In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...

s, vector

Vector space

A vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex...

s, sets, etc.) can be, if it has to satisfy certain restrictions.

For example, how many people can we invite to a party where among each three people there are two who know each other and two who don't know each other? An easy Ramsey-type

Ramsey theory

Ramsey theory, named after Frank P. Ramsey, is a branch of mathematics that studies the conditions under which order must appear. Problems in Ramsey theory typically ask a question of the form: how many elements of some structure must there be to guarantee that a particular property will...

argument shows that at most five persons can attend such a party. 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.