Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Combinatorics
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
== Approaches and subfields of combinatorics == ===Enumerative combinatorics=== [[Image:Catalan 4 leaves binary tree example.svg|320px|right|thumb|Five [[binary tree]]s on three [[Vertex (graph theory)|vertices]], an example of [[Catalan number]]s.]] {{Main|Enumerative combinatorics}} Enumerative combinatorics is the most classical area of combinatorics and concentrates on counting the number of certain combinatorial objects. Although counting the number of elements in a set is a rather broad [[mathematical problem]], many of the problems that arise in applications have a relatively simple combinatorial description. [[Fibonacci numbers]] is the basic example of a problem in enumerative combinatorics. The [[twelvefold way]] provides a unified framework for counting [[permutations]], [[combinations]] and [[Partition of a set|partitions]]. ===Analytic combinatorics=== {{Main|Analytic combinatorics}} [[Analytic combinatorics]] concerns the enumeration of combinatorial structures using tools from [[complex analysis]] and [[probability theory]]. In contrast with enumerative combinatorics, which uses explicit combinatorial formulae and [[generating functions]] to describe the results, analytic combinatorics aims at obtaining [[Asymptotic analysis|asymptotic formulae]]. === Partition theory === [[Image:Partition3D.svg|150px|right|thumb|A [[plane partition]].]] {{Main|Integer partition|l1=Partition theory}} Partition theory studies various enumeration and asymptotic problems related to [[integer partition]]s, and is closely related to [[q-series]], [[special functions]] and [[orthogonal polynomials]]. Originally a part of [[number theory]] and [[analysis]], it is now considered a part of combinatorics or an independent field. It incorporates the [[Bijective proof|bijective approach]] and various tools in analysis and [[analytic number theory]] and has connections with [[statistical mechanics]]. Partitions can be graphically visualized with [[Young diagram]]s or [[Ferrers diagram]]s. They occur in a number of branches of [[mathematics]] and [[physics]], including the study of [[symmetric polynomial]]s and of the [[symmetric group]] and in [[Group representation|group representation theory]] in general. ===Graph theory=== [[Image:Petersen1 tiny.svg|thumb|150px|[[Petersen graph]].]] {{Main|Graph theory}} Graphs are fundamental objects in combinatorics. Considerations of graph theory range from enumeration (e.g., the number of graphs on ''n'' vertices with ''k'' edges) to existing structures (e.g., Hamiltonian cycles) to algebraic representations (e.g., given a graph ''G'' and two numbers ''x'' and ''y'', does the [[Tutte polynomial]] ''T''<sub>''G''</sub>(''x'',''y'') have a combinatorial interpretation?). Although there are very strong connections between graph theory and combinatorics, they are sometimes thought of as separate subjects.<ref>Sanders, Daniel P.; [http://www.math.gatech.edu/~sanders/graphtheory/writings/2-digit.html ''2-Digit MSC Comparison''] {{webarchive|url=https://web.archive.org/web/20081231163112/http://www.math.gatech.edu/~sanders/graphtheory/writings/2-digit.html |date=2008-12-31 }}</ref> While combinatorial methods apply to many graph theory problems, the two disciplines are generally used to seek solutions to different types of problems. ===Design theory=== {{Main|Combinatorial design}} Design theory is a study of [[combinatorial design]]s, which are collections of subsets with certain [[Set intersection|intersection]] properties. [[Block design]]s are combinatorial designs of a special type. This area is one of the oldest parts of combinatorics, such as in [[Kirkman's schoolgirl problem]] proposed in 1850. The solution of the problem is a special case of a [[Steiner system]], which play an important role in the [[classification of finite simple groups]]. The area has further connections to [[coding theory]] and geometric combinatorics. Combinatorial design theory can be applied to the area of [[design of experiments]]. Some of the basic theory of combinatorial designs originated in the statistician [[Ronald Fisher]]'s work on the design of biological experiments. Modern applications are also found in a wide gamut of areas including [[finite geometry]], [[Tournament|tournament scheduling]], [[Lottery|lotteries]], [[mathematical chemistry]], [[mathematical biology]], [[Algorithm design|algorithm design and analysis]], [[Computer network|networking]], [[group testing]] and [[cryptography]].<ref>{{harvnb|Stinson|2003|loc=pg.1}}</ref> ===Finite geometry=== {{Main|Finite geometry}} Finite geometry is the study of [[Geometry|geometric systems]] having only a finite number of points. Structures analogous to those found in continuous geometries ([[Euclidean plane]], [[real projective space]], etc.) but defined combinatorially are the main items studied. This area provides a rich source of examples for [[Combinatorial design|design theory]]. It should not be confused with discrete geometry ([[combinatorial geometry]]). === Order theory === [[Image:Hasse diagram of powerset of 3.svg|thumb|right|150px|[[Hasse diagram]] of the [[Power set|powerset]] of {x,y,z} ordered by [[Inclusion map|inclusion]].]] {{Main|Order theory}} Order theory is the study of [[partially ordered sets]], both finite and infinite. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". Various examples of partial orders appear in [[abstract algebra|algebra]], geometry, number theory and throughout combinatorics and graph theory. Notable classes and examples of partial orders include [[Lattice (order)|lattices]] and [[Boolean algebras]]. ===Matroid theory=== {{Main|Matroid theory}} Matroid theory abstracts part of [[geometry]]. It studies the properties of sets (usually, finite sets) of vectors in a [[vector space]] that do not depend on the particular coefficients in a [[linear independence|linear dependence]] relation. Not only the structure but also enumerative properties belong to matroid theory. Matroid theory was introduced by [[Hassler Whitney]] and studied as a part of order theory. It is now an independent field of study with a number of connections with other parts of combinatorics. ===Extremal combinatorics=== {{Main|Extremal combinatorics}}Extremal combinatorics studies how large or how small a collection of finite objects ([[number]]s, [[Graph (discrete mathematics)|graphs]], [[Vector space|vectors]], [[Set (mathematics)|sets]], etc.) can be, if it has to satisfy certain restrictions. Much of extremal combinatorics concerns [[Class (set theory)|classes]] of [[set system]]s; 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 family#Sperner's theorem|Sperner's theorem]], which gave rise to much of extremal set theory. The types of questions addressed in this case are about the largest possible graph which satisfies certain properties. For example, the largest [[triangle-free graph]] on ''2n'' vertices is a [[complete bipartite graph]] ''K<sub>n,n</sub>''. Often it is too hard even to find the extremal answer ''f''(''n'') exactly and one can only give an [[asymptotic analysis|asymptotic estimate]]. [[Ramsey theory]] is another part of extremal combinatorics. It states that any [[sufficiently large]] configuration will contain some sort of order. It is an advanced generalization of the [[pigeonhole principle]]. ===Probabilistic combinatorics=== [[Image:Self avoiding walk.svg|thumb|right|150px|[[Self-avoiding walk]] in a [[Lattice graph|square grid graph]].]] {{Main|Probabilistic method}} In probabilistic combinatorics, the questions are of the following type: what is the probability of a certain property for a random discrete object, such as a [[random graph]]? For instance, what is the average number of triangles in a random graph? Probabilistic methods are also used to determine the existence of combinatorial objects with certain prescribed properties (for which explicit examples might be difficult to find) by observing that the probability of randomly selecting an object with those properties is greater than 0. This approach (often referred to as ''the'' [[probabilistic method]]) proved highly effective in applications to extremal combinatorics and graph theory. A closely related area is the study of finite [[Markov chains]], especially on combinatorial objects. Here again probabilistic tools are used to estimate the [[Markov chain mixing time|mixing time]].{{clarify|date=November 2022}} Often associated with [[Paul Erdős]], who did the pioneering work on the subject, probabilistic combinatorics was traditionally viewed as a set of tools to study problems in other parts of combinatorics. The area recently grew to become an independent field of combinatorics. ===Algebraic combinatorics=== [[Image:Young diagram for 541 partition.svg|thumb|right|150px|[[Young diagram]] of the [[integer partition]] (5, 4, 1).]] {{Main|Algebraic combinatorics}} Algebraic combinatorics is an area of [[mathematics]] that employs methods of [[abstract algebra]], notably [[group theory]] and [[representation theory]], in various combinatorial contexts and, conversely, applies combinatorial techniques to problems in [[abstract algebra|algebra]]. Algebraic combinatorics has come to be seen more expansively as an area of mathematics where the interaction of combinatorial and algebraic methods is particularly strong and significant. Thus the combinatorial topics may be [[Enumerative combinatorics|enumerative]] in nature or involve [[matroid]]s, [[polytope]]s, [[partially ordered set]]s, or [[Finite geometry|finite geometries]]. On the algebraic side, besides group and representation theory, [[lattice theory]] and [[commutative algebra]] are common. ===Combinatorics on words=== [[Image:Morse-Thue sequence.gif|thumb|right|210px|Construction of a [[Thue–Morse sequence|Thue–Morse infinite word]].]] {{Main|Combinatorics on words}} Combinatorics on words deals with [[formal language]]s. It arose independently within several branches of mathematics, including [[number theory]], [[group theory]] and [[probability]]. It has applications to enumerative combinatorics, [[fractal analysis]], [[theoretical computer science]], [[automata theory]], and [[linguistics]]. While many applications are new, the classical [[Chomsky–Schützenberger hierarchy]] of classes of [[formal grammar]]s is perhaps the best-known result in the field. ===Geometric combinatorics=== [[Image:Icosahedron.svg|150px|thumb|right|An [[icosahedron]].]] {{Main|Geometric combinatorics}} Geometric combinatorics is related to [[Convex geometry|convex]] and [[discrete geometry]]. It asks, for example, how many faces of each dimension a [[convex polytope]] can have. [[Metric geometry|Metric]] properties of polytopes play an important role as well, e.g. the [[Cauchy's theorem (geometry)|Cauchy theorem]] on the rigidity of convex polytopes. Special polytopes are also considered, such as [[permutohedron|permutohedra]], [[associahedron|associahedra]] and [[Birkhoff polytope]]s. [[Combinatorial geometry]] is a historical name for discrete geometry. It includes a number of subareas such as [[polyhedral combinatorics]] (the study of [[Face (geometry)|faces]] of [[Convex polyhedron|convex polyhedra]]), [[convex geometry]] (the study of [[convex set]]s, in particular combinatorics of their intersections), and [[discrete geometry]], which in turn has many applications to [[computational geometry]]. The study of [[regular polytope]]s, [[Archimedean solid]]s, and [[kissing number]]s is also a part of geometric combinatorics. Special polytopes are also considered, such as the [[permutohedron]], [[associahedron]] and [[Birkhoff polytope]]. ===Topological combinatorics=== [[Image:Collier-de-perles-rouge-vert.svg|150px|thumb|right|[[Necklace splitting problem|Splitting a necklace]] with two cuts.]] {{Main|Topological combinatorics}} Combinatorial analogs of concepts and methods in [[topology]] are used to study [[graph coloring]], [[fair division]], [[partition of a set|partitions]], [[partially ordered set]]s, [[decision tree]]s, [[necklace problem]]s and [[discrete Morse theory]]. It should not be confused with [[combinatorial topology]] which is an older name for [[algebraic topology]]. ===Arithmetic combinatorics=== {{Main|Arithmetic combinatorics}} Arithmetic combinatorics arose out of the interplay between [[number theory]], combinatorics, [[ergodic theory]], and [[harmonic analysis]]. It is about combinatorial estimates associated with arithmetic operations (addition, subtraction, multiplication, and division). [[Additive number theory]] (sometimes also called additive combinatorics) refers to the special case when only the operations of addition and subtraction are involved. One important technique in arithmetic combinatorics is the [[ergodic theory]] of [[dynamical system]]s. ===Infinitary combinatorics=== {{Main|Infinitary combinatorics}} Infinitary combinatorics, or combinatorial set theory, is an extension of ideas in combinatorics to infinite sets. It is a part of [[set theory]], an area of [[mathematical logic]], but uses tools and ideas from both set theory and extremal combinatorics. Some of the things studied include [[continuous graph]]s and [[Tree (set theory)|trees]], extensions of [[Ramsey's theorem]], and [[Martin's axiom]]. Recent developments concern combinatorics of the [[Continuum (set theory)|continuum]]<ref>[[Andreas Blass]], ''Combinatorial Cardinal Characteristics of the Continuum'', Chapter 6 in Handbook of Set Theory, edited by [[Matthew Foreman]] and [[Akihiro Kanamori]], Springer, 2010</ref> and combinatorics on successors of singular cardinals.<ref>{{Citation |last=Eisworth |first=Todd |title=Successors of Singular Cardinals |date=2010 |url=http://link.springer.com/10.1007/978-1-4020-5764-9_16 |work=Handbook of Set Theory |pages=1229–1350 |editor-last=Foreman |editor-first=Matthew |place=Dordrecht |publisher=Springer Netherlands |language=en |doi=10.1007/978-1-4020-5764-9_16 |isbn=978-1-4020-4843-2 |access-date=2022-08-27 |editor2-last=Kanamori |editor2-first=Akihiro}}</ref> [[Gian-Carlo Rota]] used the name ''continuous combinatorics''<ref>{{Cite web |url=http://faculty.uml.edu/dklain/cpc.pdf |title=''Continuous and profinite combinatorics'' |access-date=2009-01-03 |archive-date=2009-02-26 |archive-url=https://web.archive.org/web/20090226040144/http://faculty.uml.edu/dklain/cpc.pdf |url-status=live }}</ref> to describe [[geometric probability]], since there are many analogies between ''counting'' and ''measure''.
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)