You are currently browsing the tag archive for the ‘matroid theory’ tag.
Combinatorics is namely a branch of pure mathematics. In this sense it deals with the study of discrete and often finite objects. And it relates to numerus of other areas of mathematics; such as algebra, probability theory, ergodic theory and geometry, as well as to applied subjects in computer science and statistical physics.
In one sense combinatorics is the science of counting. Because, some aspects of combinatorics include the “counting” of objects satisfying certain criteria like enumerative combinatorics. It decides when the criteria can be met, and constructing and analyzing objects meeting the criteria as in combinatorial designs and matroid theory, finding “largest”, “smallest”, or “optimal” objects extremal combinatorics and combinatorial optimization, and finding algebraic structures these objects may have, algebraic combinatorics.
This is the area of mathematics which serves to study families of sets, usually finite, with certain characteristic arrangements of their elements or subsets. And ask what combinations are possible, and how many there are. This includes numerous quite elementary topics, such as enumerating all possible permutations or combinations of a finite set.
Consequently, it is difficult to show all the topics with which a person new to combinatorics might come into contact. Moreover, because of the approachable nature of the subject, combinatorics is often presented with other fields; such as elementary probability, elementary number theory, and so on, to the exclusion of the more significant aspects of the subject.
These include more sophisticated methods of counting sets. For instance, the cardinalities of sequences of sets are often arranged into power series to form the generating functions, which can then be analyzed using techniques of analysis. Since many counting procedures involve the binomial coefficients, it is not surprising to see the hypergeometric functions appear frequently in this regard.
In some cases the enumeration is asymptotic, for instance, the estimates for the number of partitions of an integer. In several cases, the counting can be done in a purely synthetic manner using the “umbral calculus”. Combinatorial arguments determining coefficients can be used to deduce identities among functions, particularly between infinite sums or products, such as some of the famous Ramanujan identities.
A non-enumerative branch of combinatorics is the study of designs. This design theory is properly a study of combinatorial designs. Sets and their subsets arranged into some particularly symmetric or asymmetric pattern, which are collections of subsets with certain intersection properties. Perhaps most familiar are the Latin squares, arrangements of elements into a rectangular array with no repeats in any row or column. Block designs are combinatorial designs of a special type. This area is one one oldest parts of combinatorics, such as in Kirkman’s schoolgirl problem proposed in 1850.
Also famous is the Fano plane, seven points falling into seven “lines”, each with three points. This suggests that connection exists with finite geometries. Suitably axiomatized, these tend to look like geometries over finite fields, although finite planes are much more flexible. The solution of the problem is a special case of 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. Matroids may be viewed as generalized geometries; they are included here as well. Of course graphs themselves are designs, although it is only the most regular graphs which are included in these discussions.
Oh the other hand, A graph is a set V of vertices and a set E of edges —pairs of elements of V. This simple definition makes Graph Theory the appropriate language for discussing binary relations on sets, which is clearly a broad topic. Graphs are basic objects in combinatorics, though it should be noted that while there are very strong connections between graph theory and combinatorics, these two are sometimes thought of as separate subjects. Among the topics of interest are topological properties such as connectivity and planarity, counting problems (how many graphs of a certain type?); coloring problems (recognizing bipartite graphs, the Four-Color Theorem); paths, cycles, and distances in graphs (can one cross the Köningsberg bridges exactly once each?).
There is a significant number of graph-theoretic topics which are the object of complexity studies in computation (e.g. the Traveling Salesman problem, sorting algorithms, the graph-isomorphism problem). The theory also extends to directed, labeled, or multiply-connected graphs. As you can see, the questions range from counting (e.g. the number of graphs on n vertices with k edges) to structural (e.g. which graphs contain Hamiltonian cycles) to algebraic questions (e.g. given a graph G and two numbers x and y, does the Tutte polynomial TG(x,y) have a combinatorial interpretation?).
Finally, it is important to assert that algebraic tools are used in a number of ways in combinatorics. For instance, when incidence matrices can be associated to graphs, or symmetry groups can be associated to block designs, and so on. Particularly common in the study of strongly regular graphs are association schemes.
A particular algebraic topic of interest to combinatorialists is the study of Young tableaux, closely connected to the symmetric groups (enumerating, for example, their representations). Codes (in the sense of coding theory) may be considered part of combinatorics, particularly the construction of nonlinear codes.