Combinatorics
Organizer: jacobfox [at] stanford.edu (Jacob Fox)
Upcoming Events
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.
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…
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…
Past Events
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…
Define an equivalence relation on the symmetric group S_n by declaring two permutations equivalent if their weak excedances occur in the same positions and share the same values, up to reordering. This talk explores the resulting “excedance equivalence classes” of S_n: their number, the size of…
We will begin by briefly introducing the use of higher-order Fourier analysis in additive combinatorics for a general audience. In particular, we will discuss the arithmetic regularity lemma and how it identifies a certain class of arithmetically-structured functions -- nilsequences -- as…
Semialgebraic graphs are a convenient way to encode many problems in discrete geometry. These include the Erdős unit distance problem and many of its variants, the point-line incidence problems studied by Szemerédi–Trotter and by Guth–Katz, more general problems about incidences of…
Given two vertex-ordered graphs G and H, the ordered Ramsey number R_<(G,H) is the smallest N such that whenever the edges of a vertex-ordered complete graph K_N are red/blue-colored, then there is a red (ordered) copy of G or a blue (ordered) copy of H. Let P_n^t denote the t-th power of a…