Extremal combinatorics
Encyclopedia
Extremal combinatorics is a field of combinatorics
, which is itself a part of mathematics
. Extremal combinatorics studies how large or how small a collection of finite objects (number
s, graph
s, vector
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
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.
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
, which is itself a part of mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
. Extremal combinatorics studies how large or how small a collection of finite objects (number
Number
A number is a mathematical object used to count and measure. In mathematics, the definition of number has been extended over the years to include such numbers as zero, negative numbers, rational numbers, irrational numbers, and complex numbers....
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 the British mathematician and philosopher Frank P. Ramsey, is a branch of mathematics that studies the conditions under which order must appear...
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.