Extremal combinatorics

Extremal 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 (numbers, graphs, vectors, 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.

References

* 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.


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • 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 (enumerative combinatorics), deciding when certain criteria can be met,… …   Wikipedia

  • combinatorics — /keuhm buy neuh tawr iks, tor , kom beuh /, n. (used with singular v.) See combinatorial analysis. * * * Branch of mathematics concerned with the selection, arrangement, and combination of objects chosen from a finite set. The number of possible… …   Universalium

  • Outline of combinatorics — See also: Index of combinatorics articles The following outline is presented as an overview of and topical guide to combinatorics: Combinatorics – branch of mathematics concerning the study of finite or countable discrete structures. Contents 1… …   Wikipedia

  • Schnittfamilie — Eine Schnittfamilie F einer N Menge bezeichnet in der Mathematik eine endliche Familie, bei der je zwei ihrer Elemente einen nichtleeren Schnitt haben. Inhaltsverzeichnis 1 Definition 2 Bemerkungen 3 Quellen …   Deutsch Wikipedia

  • List of mathematics articles (E) — NOTOC E E₇ E (mathematical constant) E function E₈ lattice E₈ manifold E∞ operad E7½ E8 investigation tool Earley parser Early stopping Earnshaw s theorem Earth mover s distance East Journal on Approximations Eastern Arabic numerals Easton s… …   Wikipedia

  • Combinatorial design — theory is the part of combinatorial mathematics that deals with the existence and construction of systems of finite sets whose intersections have specified numerical properties. For instance, a balanced incomplete block design (usually called for …   Wikipedia

  • Areas of mathematics — Mathematics has become a vastly diverse subject over history, and there is a corresponding need to categorize the different areas of mathematics. A number of different classification schemes have arisen, and though they share some similarities,… …   Wikipedia

  • Lists of mathematics topics — This article itemizes the various lists of mathematics topics. Some of these lists link to hundreds of articles; some link only to a few. The extremely long list of mathematics articles contains all mathematical articles in alphabetical order.… …   Wikipedia

  • Paul Erdős — at a student seminar in Budapest (fall 1992) Born 26 March 1913 …   Wikipedia

  • Satz von Erdös-Ko-Rado — Der Satz von Erdős Ko Rado ist ein Satz aus der Mengenlehre. Er ist benannt nach seinen Autoren Paul Erdős, Richard Rado und Chao Ko. Der Satz gibt eine obere Grenze für die Mächtigkeit einer k Schnittfamilie (k uniform intersecting family) in… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”