Misplaced Pages

#132867

73-410: Combinatorics is well known for the breadth of the problems it tackles. Combinatorial problems arise in many areas of pure mathematics , notably in algebra , probability theory , topology , and geometry , as well as in its many application areas. Many combinatorial questions have historically been considered in isolation, giving an ad hoc solution to a problem arising in some mathematical context. In

146-467: A Hamiltonian cycle in the edge graph of the dodecahedron . Hamilton solved this problem using the icosian calculus , an algebraic structure based on roots of unity with many similarities to the quaternions (also invented by Hamilton). This solution does not generalize to arbitrary graphs. Despite being named after Hamilton, Hamiltonian cycles in polyhedra had also been studied a year earlier by Thomas Kirkman , who, in particular, gave an example of

219-426: A Hamiltonian cycle is called a Hamiltonian graph . Similar notions may be defined for directed graphs , where each edge (arc) of a path or cycle can only be traced in a single direction (i.e., the vertices are connected with arrows and the edges traced "tail-to-head"). A Hamiltonian decomposition is an edge decomposition of a graph into Hamiltonian circuits. A Hamilton maze is a type of logic puzzle in which

292-415: A Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path. The computational problems of determining whether such paths and cycles exist in graphs are NP-complete ; see Hamiltonian path problem for details. Hamiltonian paths and cycles are named after William Rowan Hamilton , who invented the icosian game , now also known as Hamilton's puzzle , which involves finding

365-410: A Hamiltonian path if, for every non-adjacent vertex pairs the sum of their degrees and their shortest path length is greater than n . The above theorem can only recognize the existence of a Hamiltonian path in a graph and not a Hamiltonian Cycle. Many of these results have analogues for balanced bipartite graphs , in which the vertex degrees are compared to the number of vertices on a single side of

438-400: A closed walk passing through each edge of G exactly once. This tour corresponds to a Hamiltonian cycle in the line graph L ( G ) , so the line graph of every Eulerian graph is Hamiltonian. Line graphs may have other Hamiltonian cycles that do not correspond to Euler tours, and in particular the line graph L ( G ) of every Hamiltonian graph G is itself Hamiltonian, regardless of whether

511-456: A collection of finite objects ( numbers , graphs , vectors , sets , etc.) can be, if it has to satisfy certain restrictions. Much of extremal combinatorics concerns classes of set systems ; this is called extremal set theory. For instance, in an n -element set, what is the largest number of k -element subsets that can pairwise intersect one another? What is the largest number of subsets of which none contains any other? The latter question

584-446: A distinction between pure and applied mathematics. Plato helped to create the gap between "arithmetic", now called number theory , and "logistic", now called arithmetic . Plato regarded logistic (arithmetic) as appropriate for businessmen and men of war who "must learn the art of numbers or [they] will not know how to array [their] troops" and arithmetic (number theory) as appropriate for philosophers "because [they have] to arise out of

657-405: A graph is Hamiltonian if it has enough edges . The Bondy–Chvátal theorem operates on the closure cl( G ) of a graph G with n vertices, obtained by repeatedly adding a new edge uv connecting a nonadjacent pair of vertices u and v with deg( v ) + deg( u ) ≥ n until no more pairs with this property can be found. Bondy–Chvátal Theorem (1976)  —  A graph

730-400: A mathematical framework, whereas pure mathematics expressed truths that were independent of the physical world. Hardy made a separate distinction in mathematics between what he called "real" mathematics, "which has permanent aesthetic value", and "the dull and elementary parts of mathematics" that have practical use. Hardy considered some physicists, such as Einstein and Dirac , to be among

803-535: A polyhedron without Hamiltonian cycles. Even earlier, Hamiltonian cycles and paths in the knight's graph of the chessboard , the knight's tour , had been studied in the 9th century in Indian mathematics by Rudrata , and around the same time in Islamic mathematics by al-Adli ar-Rumi . In 18th century Europe, knight's tours were published by Abraham de Moivre and Leonhard Euler . A Hamiltonian path or traceable path

SECTION 10

#1733086288133

876-474: A prime example of generality, the Erlangen program involved an expansion of geometry to accommodate non-Euclidean geometries as well as the field of topology , and other forms of geometry, by viewing geometry as the study of a space together with a group of transformations. The study of numbers , called algebra at the beginning undergraduate level, extends to abstract algebra at a more advanced level; and

949-475: 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

1022-427: A rebirth. Works of Pascal , Newton , Jacob Bernoulli and Euler became foundational in the emerging field. In modern times, the works of J.J. Sylvester (late 19th century) and Percy MacMahon (early 20th century) helped lay the foundation for enumerative and algebraic combinatorics . Graph theory also enjoyed an increase of interest at the same time, especially in connection with the four color problem . In

1095-509: A separate field of study. There remain many connections with geometric and topological combinatorics, which themselves can be viewed as outgrowths of the early discrete geometry. Combinatorial aspects of dynamical systems is another emerging field. Here dynamical systems can be defined on combinatorial objects. See for example graph dynamical system . There are increasing interactions between combinatorics and physics , particularly statistical physics . Examples include an exact solution of

1168-444: A sharp divergence from physics , particularly from 1950 to 1983. Later this was criticised, for example by Vladimir Arnold , as too much Hilbert , not enough Poincaré . The point does not yet seem to be settled, in that string theory pulls one way, while discrete mathematics pulls back towards proof as central. Mathematicians have always had differing opinions regarding the distinction between pure and applied mathematics. One of

1241-423: A trend towards increased generality. Uses and advantages of generality include the following: Generality's impact on intuition is both dependent on the subject and a matter of personal preference or learning style. Often generality is seen as a hindrance to intuition, although it can certainly function as an aid to it, especially when it provides analogies to material for which one already has good intuition. As

1314-665: Is Hamiltonian if and only if its closure is Hamiltonian. As complete graphs are Hamiltonian, all graphs whose closure is complete are Hamiltonian, which is the content of the following earlier theorems by Dirac and Ore. Dirac's Theorem (1952)  —  A simple graph with n vertices ( n ≥ 3 {\displaystyle n\geq 3} ) is Hamiltonian if every vertex has degree n 2 {\displaystyle {\tfrac {n}{2}}} or greater. Ore's Theorem (1960)  —  A simple graph with n vertices ( n ≥ 3 {\displaystyle n\geq 3} )

1387-481: Is Hamiltonian if the sum of full degrees of every pair of distinct non-adjacent vertices is greater than or equal to 2 n − 1 {\displaystyle 2n-1} The number of vertices must be doubled because each undirected edge corresponds to two directed arcs and thus the degree of a vertex in the directed graph is twice the degree in the undirected graph. Rahman– Kaykobad (2005)  —  A simple graph with n vertices has

1460-468: Is Hamiltonian if, for every pair of non-adjacent vertices, the sum of their degrees is n or greater. The following theorems can be regarded as directed versions: Ghouila–Houiri (1960)  —  A strongly connected simple directed graph with n vertices is Hamiltonian if every vertex has a full degree greater than or equal to n . Meyniel (1973)  —  A strongly connected simple directed graph with n vertices

1533-405: Is a path that visits each vertex of the graph exactly once. A graph that contains a Hamiltonian path is called a traceable graph . A graph is Hamiltonian-connected if for every pair of vertices there is a Hamiltonian path between the two vertices. A Hamiltonian cycle , Hamiltonian circuit , vertex tour or graph cycle is a cycle that visits each vertex exactly once. A graph that contains

SECTION 20

#1733086288133

1606-426: Is a historical name for discrete geometry. It includes a number of subareas such as polyhedral combinatorics (the study of faces of convex polyhedra ), convex geometry (the study of convex sets , in particular combinatorics of their intersections), and discrete geometry , which in turn has many applications to computational geometry . The study of regular polytopes , Archimedean solids , and kissing numbers

1679-436: Is also a part of geometric combinatorics. Special polytopes are also considered, such as the permutohedron , associahedron and Birkhoff polytope . Combinatorial analogs of concepts and methods in topology are used to study graph coloring , fair division , partitions , partially ordered sets , decision trees , necklace problems and discrete Morse theory . It should not be confused with combinatorial topology which

1752-426: 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 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

1825-417: Is an older name for algebraic topology . 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

1898-428: 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 . 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

1971-449: Is answered by 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 n,n . Often it is too hard even to find the extremal answer f ( n ) exactly and one can only give an asymptotic estimate . Ramsey theory

2044-483: Is enshrined in the full title of the Sadleirian Chair , "Sadleirian Professor of Pure Mathematics", founded (as a professorship) in the mid-nineteenth century. The idea of a separate discipline of pure mathematics may have emerged at that time. The generation of Gauss made no sweeping distinction of the kind between pure and applied . In the following years, specialisation and professionalisation (particularly in

2117-516: Is offered by American mathematician Andy Magid : I've always thought that a good model here could be drawn from ring theory. In that subject, one has the subareas of commutative ring theory and non-commutative ring theory . An uninformed observer might think that these represent a dichotomy, but in fact the latter subsumes the former: a non-commutative ring is a not-necessarily-commutative ring. If we use similar conventions, then we could refer to applied mathematics and nonapplied mathematics, where by

2190-445: Is the basic example of a problem in enumerative combinatorics. The twelvefold way provides a unified framework for counting permutations , combinations and partitions . 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

2263-455: Is the problem of factoring large integers , which is the basis of the RSA cryptosystem , widely used to secure internet communications. It follows that, presently, the distinction between pure and applied mathematics is more a philosophical point of view or a mathematician's preference rather than a rigid subdivision of mathematics. Ancient Greek mathematicians were among the earliest to make

Combinatorics - Misplaced Pages Continue

2336-449: Is the study of finite Markov chains , especially on combinatorial objects. Here again probabilistic tools are used to estimate the mixing time . 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

2409-428: Is the study of optimization on discrete and combinatorial objects. It started as a part of combinatorics and graph theory, but is now viewed as a branch of applied mathematics and computer science, related to operations research , algorithm theory and computational complexity theory . Coding theory started as a part of design theory with early combinatorial constructions of error-correcting codes . The main idea of

2482-594: The Ising model , and a connection between the Potts model on one hand, and the chromatic and Tutte polynomials on the other hand. Pure mathematics Pure mathematics is the study of mathematical concepts independently of any application outside mathematics . These concepts may originate in real-world concerns, and the results obtained may later turn out to be useful for practical applications, but pure mathematicians are not primarily motivated by such applications. Instead,

2555-514: The Weierstrass approach to mathematical analysis ) started to make a rift more apparent. At the start of the twentieth century mathematicians took up the axiomatic method , strongly influenced by David Hilbert 's example. The logical formulation of pure mathematics suggested by Bertrand Russell in terms of a quantifier structure of propositions seemed more and more plausible, as large parts of mathematics became axiomatised and thus subject to

2628-488: The analysis of algorithms . The full scope of combinatorics is not universally agreed upon. According to H.J. Ryser , a definition of the subject is difficult because it crosses so many mathematical subdivisions. Insofar as an area can be described by the types of problems it addresses, combinatorics is involved with: Leon Mirsky has said: "combinatorics is a range of linked studies which have something in common and yet diverge widely in their objectives, their methods, and

2701-468: The ancient world . Indian physician Sushruta asserts in Sushruta Samhita that 63 combinations can be made out of 6 different tastes, taken one at a time, two at a time, etc., thus computing all 2 − 1 possibilities. Greek historian Plutarch discusses an argument between Chrysippus (3rd century BCE) and Hipparchus (2nd century BCE) of a rather delicate enumerative problem, which

2774-525: The bijective approach and various tools in analysis and analytic number theory and has connections with statistical mechanics . Partitions can be graphically visualized with Young diagrams or Ferrers diagrams . They occur in a number of branches of mathematics and physics , including the study of symmetric polynomials and of the symmetric group and in group representation theory in general. Graphs are fundamental objects in combinatorics. Considerations of graph theory range from enumeration (e.g.,

2847-482: The "real" mathematicians, but at the time that he was writing his Apology , he considered general relativity and quantum mechanics to be "useless", which allowed him to hold the opinion that only "dull" mathematics was useful. Moreover, Hardy briefly admitted that—just as the application of matrix theory and group theory to physics had come unexpectedly—the time may come where some kinds of beautiful, "real" mathematics may be useful as well. Another insightful view

2920-428: The appeal is attributed to the intellectual challenge and aesthetic beauty of working out the logical consequences of basic principles. While pure mathematics has existed as an activity since at least ancient Greece , the concept was elaborated upon around the year 1900, after the introduction of theories with counter-intuitive properties (such as non-Euclidean geometries and Cantor's theory of infinite sets), and

2993-586: The binomial coefficients—was presented by mathematicians in treatises dating as far back as the 10th century, and would eventually become known as Pascal's triangle . Later, in Medieval England , campanology provided examples of what is now known as Hamiltonian cycles in certain Cayley graphs on permutations. During the Renaissance , together with the rest of mathematics and the sciences , combinatorics enjoyed

Combinatorics - Misplaced Pages Continue

3066-453: The bipartition rather than the number of vertices in the whole graph. Theorem  —  A 4-connected planar triangulation has a Hamiltonian cycle. Theorem  —  A 4-connected planar graph has a Hamiltonian cycle. An algebraic representation of the Hamiltonian cycles of a given weighted digraph (whose arcs are assigned weights from a certain ground field)

3139-592: The classical Chomsky–Schützenberger hierarchy of classes of formal grammars is perhaps the best-known result in the field. Geometric combinatorics is related to convex and discrete geometry . It asks, for example, how many faces of each dimension a convex polytope can have. Metric properties of polytopes play an important role as well, e.g. the Cauchy theorem on the rigidity of convex polytopes. Special polytopes are also considered, such as permutohedra , associahedra and Birkhoff polytopes . Combinatorial geometry

3212-615: The combinatorial topics may be enumerative in nature or involve matroids , polytopes , partially ordered sets , or finite geometries . On the algebraic side, besides group and representation theory, lattice theory and commutative algebra are common. Combinatorics on words deals with formal languages . 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,

3285-574: The degree of coherence they have attained." One way to define combinatorics is, perhaps, to describe its subdivisions with their problems and techniques. This is the approach that is used below. However, there are also purely historical reasons for including or not including some topics under the combinatorics umbrella. Although primarily concerned with finite systems, some combinatorial questions and techniques can be extended to an infinite (specifically, countable ) but discrete setting. Basic combinatorial concepts and enumerative results appeared throughout

3358-534: The design of biological experiments. Modern applications are also found in a wide gamut of areas including finite geometry , tournament scheduling , lotteries , mathematical chemistry , mathematical biology , algorithm design and analysis , networking , group testing and cryptography . Finite geometry is the study of 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

3431-475: The discovery of apparent paradoxes (such as continuous functions that are nowhere differentiable , and Russell's paradox ). This introduced the need to renew the concept of mathematical rigor and rewrite all mathematics accordingly, with a systematic use of axiomatic methods . This led many mathematicians to focus on mathematics for its own sake, that is, pure mathematics. Nevertheless, almost all mathematical theories remained motivated by problems coming from

3504-561: The goal is to find the unique Hamiltonian cycle in a given graph. Any Hamiltonian cycle can be converted to a Hamiltonian path by removing one of its edges, but a Hamiltonian path can be extended to a Hamiltonian cycle only if its endpoints are adjacent. All Hamiltonian graphs are biconnected , but a biconnected graph need not be Hamiltonian (see, for example, the Petersen graph ). An Eulerian graph G (a connected graph in which every vertex has even degree) necessarily has an Euler tour,

3577-507: The graph G is Eulerian. A tournament (with more than two vertices) is Hamiltonian if and only if it is strongly connected . The number of different Hamiltonian cycles in a complete undirected graph on n vertices is ⁠ ( n – 1)! / 2 ⁠ and in a complete directed graph on n vertices is ( n – 1)! . These counts assume that cycles that are the same apart from their starting point are not counted separately. The best vertex degree characterization of Hamiltonian graphs

3650-412: The idea of deducing the form of a cylinder from the rotation of a rectangle about one of its sides, a number of real rectangles and cylinders, however imperfect in form, must have been examined. Like all other sciences, mathematics arose out of the needs of men...But, as in every department of thought, at a certain stage of development the laws, which were abstracted from the real world, become divorced from

3723-409: The later twentieth century, however, powerful and general theoretical methods were developed, making combinatorics into an independent branch of mathematics in its own right. One of the oldest and most accessible parts of combinatorics is graph theory , which by itself has numerous natural connections to other areas. Combinatorics is used frequently in computer science to obtain formulas and estimates in

SECTION 50

#1733086288133

3796-406: The latter we mean not-necessarily-applied mathematics ... [emphasis added] Friedrich Engels argued in his 1878 book Anti-Dühring that "it is not at all true that in pure mathematics the mind deals only with its own creations and imaginations. The concepts of number and figure have not been invented from any source other than the world of reality". He further argued that "Before one came upon

3869-640: The main items studied. This area provides a rich source of examples for design theory . It should not be confused with discrete geometry ( combinatorial geometry ). 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 algebra , geometry, number theory and throughout combinatorics and graph theory. Notable classes and examples of partial orders include lattices and Boolean algebras . Matroid theory abstracts part of geometry . It studies

3942-484: The most famous (but perhaps misunderstood) modern examples of this debate can be found in G.H. Hardy 's 1940 essay A Mathematician's Apology . It is widely believed that Hardy considered applied mathematics to be ugly and dull. Although it is true that Hardy preferred pure mathematics, which he often compared to painting and poetry , Hardy saw the distinction between pure and applied mathematics to be simply that applied mathematics sought to express physical truth in

4015-495: The number of permutations and combinations , and these formulas may have been familiar to Indian mathematicians as early as the 6th century CE. The philosopher and astronomer Rabbi Abraham ibn Ezra ( c.  1140 ) established the symmetry of binomial coefficients , while a closed formula was obtained later by the talmudist and mathematician Levi ben Gerson (better known as Gersonides), in 1321. The arithmetical triangle—a graphical diagram showing relationships among

4088-521: 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 G ( 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. While combinatorial methods apply to many graph theory problems,

4161-420: The operations of addition and subtraction are involved. One important technique in arithmetic combinatorics is the ergodic theory of dynamical systems . 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

4234-404: 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

4307-495: The properties of sets (usually, finite sets) of vectors in a vector space that do not depend on the particular coefficients in a 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 studies how large or how small

4380-471: The real world or from less abstract mathematical theories. Also, many mathematical theories, which had seemed to be totally pure mathematics, were eventually used in applied areas, mainly physics and computer science . A famous early example is Isaac Newton 's demonstration that his law of universal gravitation implied that planets move in orbits that are conic sections , geometrical curves that had been studied in antiquity by Apollonius . Another example

4453-550: The real world, and are set up against it as something independent, as laws coming from outside, to which the world has to conform." Hamiltonian cycle In the mathematical field of graph theory , a Hamiltonian path (or traceable path ) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit ) is a cycle that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form

SECTION 60

#1733086288133

4526-409: The results, analytic combinatorics aims at obtaining asymptotic formulae . Partition theory studies various enumeration and asymptotic problems related to integer partitions , 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

4599-405: The sake of the demonstrations themselves, in the same way as we accept many other things in mathematics for this and for no other reason. And since many of his results were not applicable to the science or engineering of his day, Apollonius further argued in the preface of the fifth book of Conics that the subject is one of those that "...seem worthy of study for their own sake." The term itself

4672-416: The same time led to a partial fragmentation of the field. 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

4745-479: The sea of change and lay hold of true being." Euclid of Alexandria , when asked by one of his students of what use was the study of geometry, asked his slave to give the student threepence, "since he must make gain of what he learns." The Greek mathematician Apollonius of Perga was asked about the usefulness of some of his theorems in Book IV of Conics to which he proudly asserted, They are worthy of acceptance for

4818-460: The second half of the 20th century, combinatorics enjoyed a rapid growth, which led to establishment of dozens of new journals and conferences in the subject. In part, the growth was spurred by new connections and applications to other fields, ranging from algebra to probability, from functional analysis to number theory , etc. These connections shed the boundaries between combinatorics and parts of mathematics and theoretical computer science, but at

4891-459: The simple criteria of rigorous proof . Pure mathematics, according to a view that can be ascribed to the Bourbaki group , is what is proved. "Pure mathematician" became a recognized vocation, achievable through training. The case was made that pure mathematics is useful in engineering education : One central concept in pure mathematics is the idea of generality; pure mathematics often exhibits

4964-447: The study of functions , called calculus at the college freshman level becomes mathematical analysis and functional analysis at a more advanced level. Each of these branches of more abstract mathematics have many sub-specialties, and there are in fact many connections between pure mathematics and applied mathematics disciplines. A steep rise in abstraction was seen mid 20th century. In practice, however, these developments led to

5037-434: The subject is to design efficient and reliable methods of data transmission. It is now a large field of study, part of information theory . Discrete geometry (also called combinatorial geometry) also began as a part of combinatorics, with early results on convex polytopes and kissing numbers . With the emergence of applications of discrete geometry to computational geometry , these two fields partially merged and became

5110-424: The things studied include continuous graphs and trees , extensions of Ramsey's theorem , and Martin's axiom . Recent developments concern combinatorics of the continuum and combinatorics on successors of singular cardinals. Gian-Carlo Rota used the name continuous combinatorics to describe geometric probability , since there are many analogies between counting and measure . Combinatorial optimization

5183-457: The two disciplines are generally used to seek solutions to different types of problems. Design theory is a study of combinatorial designs , which are collections of subsets with certain intersection properties. Block designs 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

5256-628: Was later shown to be related to Schröder–Hipparchus numbers . Earlier, in the Ostomachion , Archimedes (3rd century BCE) may have considered the number of configurations of a tiling puzzle , while combinatorial interests possibly were present in lost works by Apollonius . In the Middle Ages , combinatorics continued to be studied, largely outside of the European civilization . The Indian mathematician Mahāvīra ( c.  850 ) provided formulae for

5329-526: Was provided in 1972 by the Bondy – Chvátal theorem, which generalizes earlier results by G. A. Dirac (1952) and Øystein Ore . Both Dirac's and Ore's theorems can also be derived from Pósa's theorem (1962). Hamiltonicity has been widely studied with relation to various parameters such as graph density , toughness , forbidden subgraphs and distance among other parameters. Dirac and Ore's theorems basically state that

#132867