Combinatorics

Given integers k,r, we define the multicolor van der Waerden number w(k;r) to be the largest integer N so that {1,...,N} can be partitioned into r color classes which each lack arithmetic progressions of length k. It is a well-studied problem in additive combinatorics to obtain bounds for…

Put n balls, with weights w(1),...,w(n) into an urn. Draw them out, one at a time, each time picking a ball with chance its weight, relative to what's left. This generates a random permutation and one can ask 'what does it 'look like'. The model is used by psychologists, to settle hands in poker…

Let r_k(s, e; t) denote the smallest N such that any red/blue edge coloring of the complete k-uniform hypergraph on N vertices contains either e red edges among some s vertices, or a blue clique of size t. Erdős and Hajnal introduced the study of this Ramsey number in 1972 and conjectured that…

I will discuss some combinatorics questions that arise in quantum error-correction, specifically in understanding the limits of quantum codes under the practical constraint of locality. I'll discuss known results and open questions. No quantum computing background will be assumed.

A function f from a finite vector space over the field on two elements to itself is linear if f(x+y) = f(x) + f(y) for all pairs (x,y). Suppose f is "a bit linear" -- say, f(x+y)=f(x)+f(y) for 1% of pairs (x,y).  What can you say about f?  Must it be closely related to an actually…

A graph is chordal if each of its cycles of length at least four has a chord. Chordal graphs occupy an extreme end of a trade-off between structure and generalization: they have strong structure and admit many interesting characterizations, but this strong structure makes them a…

Given a finite poset P we ask how small a family of subsets of [n] can be such that it does not contain an induced copy of the poset, but adding any other subset creates such a copy. This number is called the saturation number of P, denoted by sat*(n,P). Despite the apparent similarity to the…

A theorem of MacMahon states that the number of partitions of n for which no part appears exactly once equals the number of partitions of n into parts ≡ 1 (mod 6). The key fact behind this identity is that the numerator and denominator of a certain rational function are products of cyclotomic…

Given a tree T and an abelian group G, a labelling of the vertices of T with distinct elements of G is called harmonious if the sum of the labels along each edge is also distinct. Harmonious labellings were introduced in 1980 by Graham and Sloane in connection with the study of additive bases.…

A 1971 conjecture of Graham (later repeated by Erdős and Graham) asserts that every set A of nonzero residues modulo p has an ordering whose partial sums are all distinct. We prove this conjecture for sets A of up to quasipolynomial size; our result improves the previous bound of log p/loglog p…