Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures.
In arithmetic combinatorics, Szemerédi's theorem is a result concerning arithmetic progressions in subsets of the integers. In 1936, Erdős and Turán conjectured that every set of integers A with positive natural density contains a k-term arithmetic progression for every k. Endre Szemerédi proved the conjecture in 1975.
In mathematics, a combinatorial class is a countable set of mathematical objects, together with a size function mapping each object to a non-negative integer, such that there are finitely many objects of each size.
In mathematics, an alternating sign matrix is a square matrix of 0s, 1s, and −1s such that the sum of each row and column is 1 and the nonzero entries in each row and column alternate in sign. These matrices generalize permutation matrices and arise naturally when using Dodgson condensation to compute a determinant. They are also closely related to the six-vertex model with domain wall boundary conditions from statistical mechanics. They were first defined by William Mills, David Robbins, and Howard Rumsey in the former context.
The Stanley–Wilf conjecture, formulated independently by Richard P. Stanley and Herbert Wilf in the late 1980s, states that the growth rate of every proper permutation class is singly exponential. It was proved by Adam Marcus and Gábor Tardos (2004) and is no longer a conjecture. Marcus and Tardos actually proved a different conjecture, due to Zoltán Füredi and Péter Hajnal (1992), which had been shown to imply the Stanley–Wilf conjecture by Klazar (2000).
In mathematics, arithmetic combinatorics is a field in the intersection of number theory, combinatorics, ergodic theory and harmonic analysis.
In combinatorial mathematics and theoretical computer science, a permutation pattern is a sub-permutation of a longer permutation. Any permutation may be written in one-line notation as a sequence of digits representing the result of applying the permutation to the digit sequence 123...; for instance the digit sequence 213 represents the permutation on three elements that swaps elements 1 and 2. If π and σ are two permutations represented in this way, then π is said to contain σ as a pattern if some subsequence of the digits of π has the same relative order as all of the digits of σ.
In the study of permutation patterns, there has been considerable interest in enumerating specific permutation classes, especially those with relatively few basis elements. This area of study has turned up unexpected instances of Wilf equivalence, where two seemingly-unrelated permutation classes have the same numbers of permutations of each length.
Dominique Foata is a mathematician who works in enumerative combinatorics. With Pierre Cartier and Marcel-Paul Schützenberger he pioneered the modern approach to classical combinatorics, that lead, in part, to the current blossoming of algebraic combinatorics. His pioneering work on permutation statistics, and his combinatorial approach to special functions, are especially notable.
In the mathematics of paper folding, map folding and stamp folding are two problems of counting the number of ways that a piece of paper can be folded. In the stamp folding problem, the paper is a strip of stamps with creases between them, and the folds must lie on the creases. In the map folding problem, the paper is a map, divided by creases into rectangles, and the folds must again lie only along these creases.
Norman Linstead Biggs is a leading British mathematician focusing on discrete mathematics and in particular algebraic combinatorics.
In combinatorial mathematics, a Stirling permutation of order k is a permutation of the multiset 1, 1, 2, 2, ..., k, k with the additional property that, for each value i appearing in the permutation, the values between the two copies of i are larger than i. For instance, the 15 Stirling permutations of order three are
Rodica Eugenia Simion was a Romanian-American mathematician. She was the Columbian School Professor of Mathematics at George Washington University. Her research concerned combinatorics: she was a pioneer in the study of permutation patterns, and an expert on noncrossing partitions.
In the study of permutations and permutation patterns, Wilf equivalence is an equivalence relation on permutation classes. Two permutation classes are Wilf equivalent when they have the same numbers of permutations of each possible length, or equivalently if they have the same generating functions. The equivalence classes for Wilf equivalence are called Wilf classes; they are the combinatorial classes of permutation classes. The counting functions and Wilf equivalences among many specific permutation classes are known.
Wojciech Samotij is a Polish mathematician who works in combinatorics, additive number theory, Ramsey theory and graph theory.
Mireille Bousquet-Mélou is a French mathematician who specializes in enumerative combinatorics and who works as a senior researcher for the Centre national de la recherche scientifique (CNRS) at the computer science department (LaBRI) of the University of Bordeaux.
Sergey Kitaev is a Professor of Mathematics at the University of Strathclyde, Glasgow, Scotland. He obtained his Ph.D. in mathematics from the University of Gothenburg in 2003 under the supervision of Einar Steingrímsson. Kitaev's research interests concern aspects of combinatorics and graph theory.
Sylvie Corteel is a French mathematician at the Centre national de la recherche scientifique and Paris Diderot University and the University of California, Berkeley, who was an editor-in-chief of the Journal of Combinatorial Theory, Series A. Her research concerns the enumerative combinatorics and algebraic combinatorics of permutations, tableaux, and partitions.
In the mathematical field of graph theory, a word-representable graph is a graph that can be characterized by a word whose entries alternate in a prescribed way. In particular, if the vertex set of the graph is V, one should be able to choose a word w over the alphabet V such that letters a and b alternate in w if and only if the pair ab is an edge in the graph. For example, the cycle graph labeled by a, b, c and d in clock-wise direction is word-representable because it can be represented by abdacdbc: the pairs ab, bc, cd and ad alternate, but the pairs ac and bd do not.
Ian P. Goulden is a Canadian and British mathematician. He works as a professor at the University of Waterloo in the department of Combinatorics and Optimization. He obtained his PhD from the University of Waterloo in 1979 under the supervision of David M. Jackson. His PhD thesis was titled Combinatorial Decompositions in the Theory of Algebraic Enumeration. Goulden is well known for his contributions in enumerative combinatorics such as the Goulden-Jackson cluster method.
