Extremal combinatorics is a field of
combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many appl ...
, which is itself a part of
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
. 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 original 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 c ...
s,
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 discre ...
s,
vector
Vector most often refers to:
*Euclidean vector, a quantity with a magnitude and a direction
*Vector (epidemiology), an agent that carries and transmits an infectious pathogen into another living organism
Vector may also refer to:
Mathematic ...
s,
sets, etc.) can be, if it has to satisfy certain restrictions.
Much of extremal combinatorics concerns
class
Class 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 differentl ...
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, 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 are ...
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, who ...
, 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 mathematics that focuses on the appearance of order in a substructure given a structure of a known size. Problems in Ramsey theory typically ask a ...
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.
See also
*
Extremal graph theory
Extremal graph theory is a branch of combinatorics, itself an area of mathematics, that lies at the intersection of extremal combinatorics and graph theory. In essence, extremal graph theory studies how global properties of a graph influence local ...
*
Sauer–Shelah lemma
In combinatorial mathematics and extremal set theory, the Sauer–Shelah lemma states that every family of sets with small VC dimension consists of a small number of sets. It is named after Norbert Sauer and Saharon Shelah, who published it indep ...
*
Erdős–Ko–Rado theorem
In mathematics, the Erdős–Ko–Rado theorem limits the number of sets in a family of sets for which every two sets have at least one element in common. Paul Erdős, Chao Ko, and Richard Rado proved the theorem in 1938, but did not publish it ...
*
Kruskal–Katona theorem
In algebraic combinatorics, the Kruskal–Katona theorem gives a complete characterization of the ''f''-vectors of abstract simplicial complexes. It includes as a special case the Erdős–Ko–Rado theorem and can be restated in terms of unifor ...
*
Fisher's inequality Fisher's inequality is a necessary condition for the existence of a balanced incomplete block design, that is, a system of subsets that satisfy certain prescribed conditions in combinatorial mathematics. Outlined by Ronald Fisher, a population genet ...
*
Union-closed sets conjecture
The union-closed sets conjecture is an open problem in combinatorics posed by Péter Frankl in 1979. A family of sets is said to be ''union-closed'' if the union of any two sets from the family belongs to the family. The conjecture states: For e ...
References
*.
*.
*{{Citation
, last1 = Frankl , first1 = Peter , author1-link = Péter Frankl
, last2 = Rödl , first2 = Vojtěch , author2-link = Vojtěch Rödl
, title = Forbidden intersections
, journal = Transactions of the American Mathematical Society
, volume = 300
, issue = 1
, pages = 259–286
, year = 1987 , doi=10.2307/2000598, doi-access = free.
*
Combinatorial optimization