Combinatorics

Random walks on graphs can mix slowly. To speed it up, imagine that at each step instead of choosing the neighbor at random, there is a small probability eps>0 that we can choose it. We show that in this case, at least for graphs of bounded degree, there is a way to steer the walk so that we…

Our work begins with the following question about rainbow triangles, inspired by the joints problem: If G is a graph with m edges, each colored with one of r colors, then what is the maximum number of rainbow triangles G can have (as a function of m)? In 2023, Chao and Yu answered this…

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…

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…