Extremal combinatorics: Difference between revisions

Revision as of 10:11, 3 November 2007

Latest revision as of 21:15, 14 February 2025

(39 intermediate revisions by 31 users not shown)

Line 1:

{{Short description|Area of combinatorics}}

'''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 (mathematics)|graph]]s, [[vector space|vector]]s, [[set]]s, etc.) can be, if it has to satisfy certain restrictions.

{{No footnotes|date=November 2024}}

'''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, [[graphGraph (discrete mathematics)|graph]]s, [[vector space|vector]]s, [[setSet (mathematics)|sets]]s, etc.) can be, if it has to satisfy certain restrictions.

Much of extremal combinatorics concerns [[class (set theory)|class]]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]]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]], which gave rise to much of extremal set theory.

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 theory|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 an as large as possible subset of them 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.

ForAnother kind of example,: howHow many people can webe inviteinvited 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 theory|Ramsey-type]] argument shows that at most five persons can attend such a party (see [[Theorem on Friends and Strangers]]). Or, suppose we are given a finite set of nonzero integers, and are asked to mark an as large a subset as possible subset of themthis 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==

==See also==

* Stasys Jukna, ''Extremal Combinatorics, With Applications in Computer Science'' ([http://lovelace.thi.informatik.uni-frankfurt.de/~jukna/EC_Book/preface.html preface]). Springer-Verlag, 2001. ISBN 3-540-66313-4.

*[[Extremal graph theory]]

*[[Sauer–Shelah lemma]]

*[[Erdős–Ko–Rado theorem]]

*[[Kruskal–Katona theorem]]

*[[Fisher's inequality]]

*[[Union-closed sets conjecture]]

==References==

*{{citation

[[Category:Combinatorics]]

| last1 = Jukna | first1 = Stasys

| publisher = Springer Verlag

| title = Extremal Combinatorics, With Applications in Computer Science

| url = https://web.vu.lt/mif/s.jukna/EC_Book_2nd/index.html

| isbn = 978-3-642-17363-9

| year = 2011}}.

*{{Citation

| last1 = Alon | first1 = Noga | author1-link = Noga Alon

| last2 = Krivelevich | first2 = Michael | author2-link = Michael Krivelevich

| url = http://www.math.tau.ac.il/~nogaa/PDFS/epc7.pdf

| title = Extremal and Probabilistic Combinatorics

| year = 2006}}.

*{{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| jstor = 2000598 }}.

[[Category:Extremal combinatorics| ]]

{{Combin-stub}}

[[Category:Combinatorics|*]]

[[Category:Combinatorial optimization]]

{{Combincombin-stub}}