Combinatorics
Organizer: jacobfox [at] stanford.edu (Jacob Fox)
Upcoming Events
A Littlewood polynomial fₙ(x) = ε₀ + ε₁x + ε₂x² + … + εₙxⁿ, where each coefficient εₖ is either +1 or −1. We prove that, almost surely, liminf as n → ∞ of log(max(|fₙ(x)| : x ∈ [−1,1]) / √n ) divided by (log log n)^(1/3) is equal to −(3π² / 4)^(1/3). This answers a question raised by Salem and…
Past Events
An instance of a constraint satisfaction problem is called non-redundant if no constraint is implied by the rest; that is, for each constraint, there exists an assignment that violates that constraint while satisfying all others. The non-redundancy (NRD) of a relation R is the maximum number of…
A perfect difference set is a set S of residues modulo v such that every nonzero residue can be uniquely represented as a difference of two elements of S. In 1980, Erdős offered $1000 for determining whether any set of integers that doesn't already repeat a difference can be extended to a…
Graphs with optimally large spectral gap are known as Ramanujan graphs. Previous constructions of Ramanujan graphs are based on number theory and have specific constraints on the degree and number of vertices. In this talk, we show that, in fact, most regular graphs are…
Coarse graph theory is a developing area, which focuses on the large-scale geometric structure of graphs, particularly through the lens of quasi-isometry. A central goal here is to find coarse analogues of classical graph-theoretic results. We discuss current progress in this…
A conjecture of Alon states that, for some absolute constant C, every finite group G possesses a Cayley graph with clique and independence number each at most C log |G|. Recently, Conlon, Fox, Pham, and Yepremyan have verified this conjecture for most abelian groups using mainly graph-theoretic…
Given a set of n plane curves with no three mutually tangent, how many curve-curve tangencies can occur? What about higher order tangencies? Second, let E be a subset of the plane that contains a circle of every radius; must E have full Hausdorff dimension? What if 'circles' are replaced by a…
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.