In a proper edge coloring of a graph, a ‘rainbow’ cycle is a cycle where every edge has a different color. In this talk, we will discuss a recent paper that shows that for a graph with sufficiently many edges (n log n log log n), we can find a rainbow cycle in any proper edge coloring of the graph. The key idea involves passing the problem to a sublinear expander graph along with some probabilistic arguments. We will highlight the key ideas in the proof and the details of significant intermediate lemmas.

Flag algebras are a powerful tool in extremal graph theory introduced by Alexander Razborov in 2007. They allow for automatic discovery of nontrivial bounds on subgraph densities in graphs. We describe some of the main ideas behind flag algebras: types and flags, the downward operator, semidefinite programming, and graph limits -- and how they are simpler than they first appear.

What is the computational complexity of matrix multiplication? What is the Shannon capacity of the 7-cycle? What is the size of the largest set in F_p^n containing no line? It turns out that these questions all are the same "type" of question, and can be unified in a theory of amortization developed by Strassen in the late 1980s. We introduce the basic concepts of this theory, following the recent survey of Wigderson and Zuiddam. Surprisingly, the central construction is quite reminiscent of the definition of an affine scheme.

In this talk we consider generalizations of two classical problems: one problem, derived from a problem of Erdos and Renyi, where given any r-edge coloring of K_n, we ask to find the maximum number of vertices guaranteed to be adjacent to edges of the same color, and another problem by Gerencser and Gyarfas, where given any r-edge coloring of K_n, we ask for the largest monochromatic connected component we are guaranteed to find. In the power of many colors generalization, we look for objects using up to s colors rather than monochromatic objects. We will present bounds for these two problems from a recent work by Alon, Bucic, Christoph, and Krivelevich.

       The Collatz map is defined on the set of positive integers as follows: for odd x, Col(x) = 3x + 1 and for even x, Col(x) = x/2. The notorious Collatz conjecture states that the orbit N, Col(N), Col(Col(N)), and so on, of any positive integer N eventually reaches 1. Let Col_min(N) denote the smallest number in the orbit of N. It has long been understood that one can control the iterations of the Collatz map up to the k-th iteration with k of the order roughly log(N) by considering N modulo a suitable power of two. These local considerations eventually lead to the result of Korec: For any θ > log_4(3), for almost all N, one has Col_min(N) < N^θ.

       Recently, Terrence Tao combined these local considerations with a certain invariant measure type argument to significantly improve the result of Korec. Specifically, he proved that for any function f(N) tending to infinity, almost all N satisfy Col_min(N) < f(N). Here almost all is understood in the sense of logarithmic density.

       In this talk, I will explain the main ideas in the proof, closely following Tao's paper, which shares the title with this talk. If time permits, I will also discuss potential directions for future research.

The Sylvester--Gallai theorem asserts that for any finitely many points not on a single line, there exists a line passing through exactly two of the points. This kind of line is called ordinary. In this talk, I will talk about a result of Green and Tao that determines the minimum number of ordinary lines for n points when n is large enough. The main intermediate result in the proof is a strong structural theorem, which roughly says that points with linearly many ordinary lines should mostly lie on a cubic curve.

Given C>1, a set X, and two metrics d and d' on X, we say that (X,d') is a C-distorted copy of (X,d) whenever the product of the Lipschitz constant of Id:(X,d) -> (X,d') and the Lipschitz constant of Id:(X,d') -> (X,d) is at most C. Following Matoušek(1992), a sequence of metric spaces ((X_n,d_n))_n is a bounded distortion Ramsey family if for any k, any small ε>0 and any large C>1 we have for sufficiently large n that any C-distorted copy of (X_n,d_n) contains a (1+ε)-distorted copy of (X_k,d_k). In this talk, we provide 3 examples of bounded distortion Ramsey families. Firstly, X_n = {1,2,..,n} with the trivial metric, i.e. any two distinct points have distance 1. Secondly, X_n = {1,2,..,n} with the metric inherited from the real line: d(i,j)=|i-j|. Thirdly, X_n = {0,1}^n the n-dim Hamming cube with the Hamming metric. The last example is due to Bourgain-Milman-Wolfson(1986), using a non-linear analogue of Rademacher type.

We outline the connections between combinatorics and algebraic geometry, coming in the theory of toric varieties. We introduce fans, a combinatorial object, and show how to obtain convex polytopes and toric varieties from fans. We also explain how every matroid has an associated fan structure, it’s Bergman fan. Combinatorial properties of fans reflect geometric properties of these objects, and we focus on concrete examples of this behavior. This lays the groundwork for a bridge between the fields of algebraic geometry, convex geometry, matroid theory and combinatorics. 

The objective of this talk is to give a broad introduction to the novel theory of Lorentzian polynomials due to Brändén and Huh. Lorentzian polynomials link objects exhibiting discrete convexity (like Newton polytopes, discrete matroids) to those with continuous convexity (like quadratic forms and convex bodies) in a very deep and structural manner. We will enumerate (if time allows with some proofs) some of the main properties and connections to algebraic geometry, convex geometry and combinatorics. 

Schubert calculus provides a systematic way to answer questions such as, "How many lines intersect a generic quadruple of lines in P^3?"  Along the way, we will also encounter the Grassmannian, symmetric functions, and Young tableaux.

During the last lecture, we saw how the theory of Schubert calculus provides powerful tools for solving problems related to the enumeration of geometric configurations. In this talk, we will explore Knutson-Tao puzzles, a combinatorial approach that computes Schubert calculus. 

3-week mini series: Algebraic Methods in Combinatorics

September 13th: Noah Kravitz

Title: Nearly sharp bounds for the Ramsey numbers r(4,t)

Abstract: The Ramsey number r(s,t) is defined to be the smallest natural number n such that every graph on n vertices contains either a clique of size s or an independent set of size t.  Last semester Xiaoyu talked about a breakthrough relating to the growth rate of the "diagonal" Ramsey numbers r(t,t).  In the extreme opposite regime, one can study the growth rate of r(s,t) for s fixed and t going to infinity.  In this direction, I will focus on recent work of Mattheus and Verstraete that determines r(4,t) nearly exactly. 

September 20th: Cosmas Kravaris

Title: Random algebraic construction of extremal graphs

Abstract: Given a finite graph H and a natural number n, ex(n,H) is the largest possible number of edges of an n-vertex graph G with no copy of H (i.e. no injective graph homomorphism from H to G). We are interested in the asymptotics of ex(n,H) as n goes to infinity. Turán's theorem determines ex(n,H) when H is a complete graph, and the Erdős-Stone-Simonovits theorem determines ex(n,H) when H has chromatic number at least 3.  When H is bipartite, little is known. In this talk we will give a random algebraic construction of Bukh for constructing n-vertex graphs with many edges and no copy of the complete bipartite graph K_{s,t} for every s and some large value t. The idea is to sample uniformly a polynomial and consider a "polarity-type" graph associated to it. If time permits, related bounds and constructions will be discussed. The talk is based on the paper of Bukh (2015) and the book of Zhao (2023).

September 27th: Hung-Hsun Hans Yu

Title: Toward the Tight Density in the Finite Field Kakeya Problem

Abstract: The finite field Kakeya problem was first raised as the finite field model for the famous Kakeya conjecture, which asks to lower bound the dimension of a set in the Euclidean space containing a segment of length one in each direction. The finite field model was first solved, by Dvir, where he introduced the polynomial method to show that any Kakeya set must have constant density. This result was refined by Dvir, Kopparty, Saraf and Sudan later, where they introduced the method of multiplicities. The work left a multiplicative gap of two between the upper bound and the lower bound of the density, which was recently closed up by Boris Bukh and Ting-Wei Chao. In the talk, I will give a proof of Dvir, Kopparty, Saraf and Sudan's result, and I will also talk about where Bukh and Chao managed to get an improvement..

2-week Mini Series: Local Algorithms and Factors of IID

October 4th: Jason Prodromidis

Title: Local Algorithms: Applications and Obstructions

Abstract: In this talk, we will be introducing the notion of local algorithms. As we will see, in the case of the independence number of a typical d-regular graph, local algorithms work well, but not as well as we would like them to. The analysis of the problem will show that certain obstructions can arise, when trying to make a local algorithm work to find a set with specific properties. If time permits, we will also mention a group theoretic application of those types of algorithms, as well as results that describe the regimes that local algorithms can be used in a more general setting.

October 11th: Eyob Tsegaye

Title: Factors of IID for Graph Colorings and Graph Cuts

Abstract: We will be continuing the discussion last week of local algorithms, but taking it in a different (but very related) direction to discuss factors of iid. We will use the theory here to show that there exist 5-colorings of infinite random planar graphs which are invariant under isometries of the plane. We will then give a more concrete combinatorial application and show how factors of iid can be used to give upper and lower bounds on the limiting minimum and maximum relative size of a bisection in families of d-regular graphs

3-week Mini Series: Sumset Problems

October 25th: Daniel Zhu

Title: Fourier analysis and the Erdős distinct subset sets problem

Abstract: We discuss the application of Fourier-analytic techniques to the Erdős distinct subset sets problem, including a new exposition of the lower bound of Dubroff, Fox, and Xu (2020). Time permitting, we will also discuss a recent result of Cambie, Gao, Kim, and Liu extending the problem to a modular setting.

November 1st: Daniel Carter

Title: On the Diameter of Finite Sidon Sets

Abstract: A Sidon set, also known as a Golomb ruler or B_2 set, is a set of integers where every difference of pairs of distinct elements is unique. An old result of Erdős-Turán states that any k-element Sidon set must have diameter at least k^2 - (b + o(1)) k^(3/2) for some 0 ≤ b ≤ 2; Erdős offered $1000 for a proof or disproof that b = 0. We discuss recent work improving the upper bound on b by Balogh, Füredi, and Roy (2021); O'Bryant (2022); and myself, Hunter, and O'Bryant (2023).

November 8th: Kunal Chawla

Title: The Bourgain-Gamburd expansion machine

Abstract: I will describe an interesting, hands-on proof of expansion for Cayley graphs of SL(n, F_p) by Bourgain and Gamburd (2008). Instead of relying on Property T or deep number theory, the proof relies on analytic and combinatorial methods, using estimates on product sets to show equidistribution of the random walk.

November 15th: Kevin Ren

Title: Pinned Distances in the Plane

Abstract: Given a set of n points, it is known (Guth-Katz '15) that they span >= c (n/log n) distinct distances, which nearly matches the sqrt(n) x sqrt(n) grid example which (exercise!) gives O(n/sqrt(log n)). However, the pinned version, which asks for a point in the set that spans a lot of distances with the other points, remains more elusive. Following Solymosi-Tóth ('01), we show that there exists a point that spans >= c n^(6/7) distinct distances with the other points. This is accomplished through a clever combination of tools in discrete incidence geometry.

November 29th: Seoyeon Yang

Title: Uniqueness of giant component on expander graphs

Abstract: Emergence of a giant component in a random graph is an interesting phenomenon in percolation theory. There's a conjecture on general graphs that under a certain condition, there's an emergence of the unique giant component. We discuss this on the expander graphs using double counting. If time permits, we discuss the critical probability for finite regular expanding graphs of high girth. Based on the work of Alon, Benjamini, and Stacey (2005).

December 6th: Vanshika Jain

Title: Exploring the Representations of the General Linear Group GL_m(C) Through Young Tableaux

Abstract: To study the representations of the general linear group GL_m(C), we first study a linear algebraic construction, which extends symmetric and exterior products. Central to our study is the use of Young tableaux, which provide a parametric framework for these representations. Then, we will look at how these representations can also be constructed from representations of the symmetric group, and show their relation to certain quadratic equations. 

January 30

Speaker: Florian Richter

Title: Finding infinite arithmetic structures in sets of positive density

Abstract: In the 1970's Erdos asked several questions about what kind of infinite arithmetic structures can be found in every set of natural numbers with positive density. In recent joint work with Bryna Kra, Joel Moreira, and Donald Robertson we use ergodic methods to resolve some of these long-standing problems. This talk will provide an overview of our results and describe some of the dynamical structures that are used to prove them.

3-week mini series: Entropy methods

February 6

Speaker: Noah Kravitz

Title: Entropy and counting (Entropy week 1/3)

Abstract: The goal of this talk is to demonstrate how entropy methods can be useful in extremal graph theory.  After giving a brief review of the basic properties of entropy, I will outline several short entropic proofs of “classic” results (e.g., Bregman's Theorem) and motivate the definition of graph entropy.  This talk is based on a survey paper of Radhakrishnan.

February 13

Speaker: Hans Yu

Title: Application of the entropy method: Sidorenko's conjecture (Entropy week 2/3)

Abstract: In the second week of the series, we will apply the entropy method to prove special cases of a graph-theoretic conjecture of Sidorenko. The conjecture, in some sense, claims a lower bound on the number of copies of a given bipartite graph in another graph in terms of its number of edges.  We will see how basic properties covered in the previous week can be combined to lead to something nontrivial.

February 20

Speaker: Eyob Tsegaye

Title: Application of the entropy method: the Sunflower Conjecture (Entropy week 3/3)

Abstract: In the third and final week of the series on entropy methods, we look at the sunflower conjecture! A sunflower is a (finite) family of subsets of some larger set that are disjoint apart from their mutual intersection. We show how entropy methods can be used to achieve the best currently known bound on how large a family of sets can be before it contains a sunflower. This talk follows a blog post by Terry Tao.

2-week mini series: Slice-rank and applications

February 27

Speaker: Aleksa Milojevic

Title: Sunflowers via slice-rank (Slice-rank week 1/2)

Abstract: We will start by reviewing the solution to the capset problem by Croot, Lev, Pach and Ellenberg, Gijswijt, and then present a version of the polynomial method, called the slice rank method, introduced by Tao to symmetrize their proof. Then, we will discuss how slice rank can be used in other combinatorial problems, for example to bound the size of the biggest family of subsets of {1, 2, ..., n} without k-sunflowers. Additionally, we will cover applications of the slice rank method beyond sunflowers if time constraints allow.

March 6

Speaker: Cosmas Kravaris

Title: Slice rank of tensor powers: upper and lower bounds (Slice-rank week 2/2)

Abstract: The slice rank of a function T from A x A x A to the reals is bounded by the number of slice sets (subsets of  A x A x A where one coordinate is fixed) which cover the support of T. Fixing a linear order on each A and taking an antichain of maximal elements of the support of T, the minimum number of slice sets which cover this antichain is a lower bound for the slice rank of T. Using this, we show that the slice rank solution to the capset problem does not (naively) generalize to k-APs when k>=8. Moving on, we can form the tensor power T^n from A^n x A^n x A^n to the reals and look at the exponential growth rate of the slice rank of T^n as n grows. The bounds for the sunflower and capset tensors we saw last time are upper bounds for this rate. Using the asymptotic equipartition property, this rate is given via an entropy condition, and (if time permits) the exact rates are computed for the sunflower and capset tensors. The talk follows the 2016 blog post of Sawin and Tao.

March 13: SPRING BREAK

March 20

Speaker: Noah Kravitz

Title: New bounds for sets avoiding 3-term arithmetic progressions

Abstract: A set of integers is called 3AP-free if it does not contain a non-trivial 3-term arithmetic progression {x, x+y, x+2y}.  What is the largest possible size of a 3AP-free subset of the first N integers?  Roth showed that the answer is <<N/loglogN (in particular, o(N)).  A recent breakthrough of Kelley and Meka improves this bound to <<N exp(-\Omega(logN)^{1/11}); this is the first upper bound of the same “shape” as the lower bound coming from Behrend’s construction of 3AP-free sets.  I will give a gentle introduction to the ideas of Kelley and Meka’s proof in the finite field setting.

March 27

Speaker: Eyob Tsegaye

Title: Adjacent transposition shuffle via censoring inequalities

Abstract: The adjacent transposition shuffle is a method of card shuffling where at each step a pair of adjacent cards in the deck is swapped. In 2016, Lacoin showed that this shuffle has a mixing time of (1/pi^2+o(1))N^3logN. The proof is motivated by a simple yet powerful idea by Peres and Winkler that fewer shuffles can only hurt you (if we censor certain updates, it will take longer to mix). This intuition is not true in general and requires some subtle requirements about the "monotonicity" of the underlying system. In this talk, we will discuss what monotonicity means in this context, formalize this intuition, and see how it is used in the context of the adjacent transposition shuffle.

April 3

Speaker: Xiaoyu He

Title: An exponential improvement for diagonal Ramsey

Abstract: In the biggest breakthrough in Ramsey theory since Erdos' first-moment paper, Campos, Griffiths, Morris, and Sahasrabudhe have proved that the diagonal Ramsey number R(k) satisfies R(k) <= (4-epsilon)^k. The classical Erdos-Szekeres algorithmic proof of 4^k searches for a monochromatic clique by iteratively restricting to monochromatic neighborhoods. The new algorithm cleverly pursues two Erdos-Szekeres search paths simultaneously, one diagonal and one extremely off-diagonal. In this talk we give an overview of the Campos-Griffiths-Morris-Sahasrabudhe algorithm, which is easy to state but hard to analyze.

I also discuss my personal intuition for why (at first blush) this proof seems surprisingly specific to this particular Ramsey number, and not to generalize to off-diagonal, directed, or bipartite Ramsey numbers. It seems there are actually two exponential gaps in the bounds sqrt(2)^k <= R(k) <= 4^k, a local-to-global gap from sqrt(2)^k to 2^k and a color-inefficiency gap from 2^k to 4^k, and this new proof improves entirely on the latter half of the picture.

April 10

Speaker: Tung Nguyen

Title: Extensions of Rödl’s theorem

Abstract: An early application of the regularity lemma, Rödl’s theorem from 1986 says that every graph with no induced copy of a given graph contains a linear-sized vertex subset inducing a very sparse or very dense subgraph. It has found many applications, in particular in the investigation of quasirandomness and the Erdős–Hajnal conjecture. This talk first surveys several extensions of this result, focusing on both quantitative and qualitative aspects, and then discusses in-depth a proof of one such extension due to Chudnovsky, Scott, Seymour, and Spirkl.

April 17

Speaker: Cosmin Pohoata

Title: Convexity, color avoidance, and perfect k-hash codes

Abstract: In this talk I will discuss a few favorite open problems that are related in some way or another with Ramsey numbers, the Erdős-Szekeres problem, and the polynomial method (and also the words from the title), together with casual speculations.

April 24

Speaker: Jason Prodromidis

Title: The Study of the Ising Model via Percolation

Abstract: The Ising model is a very important model in statistical physics, introduced more than a century ago. Since then, the model itself and its variants have been objects of study in Probability Theory. In this talk, we will introduce the Ising model in Z^d and discuss some of its properties, which are mostly related to phase transition properties. An important tool in our study will be the connection of the Ising Model to a percolation model, known as the Random Cluster Model.

May 1

Speaker: Matija Bucic

Title: Robust sublinear expanders

Abstract: Expander graphs have been perhaps one of the most widely useful classes of graphs ever considered. In this talk we will focus on a fairly weak notion of expanders called sublinear expanders, first considered in combinatorics by Komlos and Szemeredi around 25 years ago. They have found many remarkable applications ever since incliding resolutions of multiple classical questions in the field.

In this talk we will focus on a more recent idea that one may impose a certain robustness condition on sublinear expanders which still allows for an (almost) decomposition lemma to hold while on the other hand allowing us to prove a number of properties usually associated with much stronger expander graphs.

After introducing the notions and giving a high level overview of how and when these type of ideas may be useful we will discuss a number of properties of such robust sublinear expanders and give an illustration of how they can be used.

September 14

Speaker: Xiaoyu He

Title: Slow and Lonely Runners

Abstract: One formulation of the Lonely Runner Conjecture states that if 0 < v_1 < v_2 <...< v_n are n positive integers, then there is a time t such that every (v_i t) is at least 1/(n+1) away from an integer. This talk is about a recent line of attack on this problem by Bohman and Peng, who showed that if all the speeds are at most (2-\epsilon) n, then the conjecture is true. They reduce this toy problem to a certain graph/hypergraph problem about matchings and vertex covers, and finish it off with number-theoretic techniques related to the Jacobsthal function.

September 21

Speaker: Noah Kravitz

Title: Hamidoune’s isoperimetric method

Abstract: In additive combinatorics, it is often desirable not only to establish general inequalities but also to solve the associated “inverse problems” of determining when equality (or near-equality) occurs.  For example, the Cauchy-Davenport Theorem asserts that if A,B are subsets of the cyclic group mod p, then |A+B| is at least min{|A|+|B|-1, p}, and Vosper’s Theorem shows (essentially) that equality holds if and only if A, B are arithmetic progressions with the same common difference.  The topic of this talk is Hamidoune’s elementary but versatile “isoperimetric method” for attacking such inverse problems.  In particular, I will describe Hamidoune’s alternative proof of (a generalization of) Vosper’s Theorem and Tao’s use of similar machinery to establish a non-abelian Freiman-Kneser-type theorem.

September 28

Speaker: Fan Wei

Title: On the limits of bounded degree graphs

Abstract: In this short talk, I will give a gentle introduction to the graph limit theory of bounded degree graphs, and show how some results, such as property testing, which is well-studied in the setting of dense graphs, also have its somewhat more restricted forms when discussing bounded degree graphs.

October 5

Speaker: Tara Abrishami

Title: Infinite families of bipartite Ramanujan graphs

Abstract: In this talk, I will give an overview of the proof that there exist infinite families of bipartite Ramanujan graphs by Marcus, Spielman, and Srivastava (here). The proof relies on a method called interlacing polynomials. If a family of polynomials is interlacing, then there exists a polynomial in the family whose largest root is at most the largest root of the sum. I will also mention some other results obtained by the same method, as time permits.  

October 12

Speaker: Cosmas Kravaris

Title: Concentration of measure for the Hamming cube and the symmetric group

Abstract: We begin with the definition of a Levy family of metric measure spaces, an axiomatization of the phenomenon of concentration of measure. We list some examples and state the main two theorems of this talk: the Hamming cubes form a Levy family and the symmetric groups form a Levy family. We then recall some basic definitions about martingales and state the key ingredient in the proof: Azuma’s martingale inequality. As time permits, we outline a proof of Azuma’s inequality and the main two theorems. This talk is based on the 1986 book of Milman and Schechtman “Asymptotic Theory of Finite Dimensional Normed Spaces”.

October 19: OCTOBER BREAK

October 26

Speaker: Hans Yu

Title: The method of hypergraph containers

Abstract: Given an Erdős–Rény random graph G(n,p), we may ask how big p should be in order for it to exhibit some Ramsey-type or Turán-type behavior. Problems of this flavor were studied using tools designed speicifcally for sparse rsets, such as the transference machinery or the sparse regularity lemma. However, in this talk, I will talk about yet another approach, discovered by Saxton–Thomason and Balogh–Morris–Samotij independently, that unifies lots of results using the method of hypergraph containers. I will mention two applications of the hypergraph container theorem, and sketch a proof of the theorem if there is time.

November 2

Speaker: Ryan Alweiss

Title: Monochromatic sums and products of polynomials

Abstract: A celebrated result of Moreira from 2016 is that the pattern {x,x+y,xy} is partition regular; i.e. any coloring of N with finitely many colors has x,x+y,xy all the same color.  Before this, it was not even known if x+y,xy is partition regular; in the 70s Hindman conjectured that {x,y,x+y,xy} is partition regular and this remains unsolved.  In this talk, we will generalize Moreira's result, and prove that {x,x+y,xy} is partition regular in a more general setting, over polynomial rings such as the rings of polynomials of t with 0 constant term.  In addition to being more general, the proof is considerably shorter and simpler.

November 9

Speaker: Micha Christoph

Title: Breaking the degeneracy barrier for coloring graphs with no K_t-minor

Abstract: In 1943, Hadwiger conjectured that every Graph with no K_t minor is t-1 colorable. Solving this conjecture is considered to be one of the most important open problems in graph theory. In the 80s, Kostochka and independently Thomason showed that every graph with no K_t minor is O(t(log t)^{1/2})-degenerate and therefore, also O(t(log t)^{1/2}) colorable. Much more recently (2020), Norin, Postle and Song made the first significant improvement on this bound, using a method called density increment. They showed that every graph with no K_t minor is O(t(log t)^{a}) colorable for any a>¼. In this talk we will discuss their approach and if time permits also have a look at the differences to the even newer paper by Delcourt and Postle (2021) improving the above bound to O(t * log log t).

November 16

Speaker: Tung Nguyen

Title: Highly connected subgraphs

Abstract: This talk aims to survey some results and conjectures regarding sufficient conditions for a graph to contain a highly connected subgraph (possibly with some additional properties). These sufficient conditions involve average degree, minimum degree, and chromatic number.

November 23; THANKSGIVING

November 30

Speaker: Alan Chang

Title: Spherical designs

Abstract: A spherical design of strength t is a finite subset X of the sphere S^(n-1) such that the average value of any polynomial f of degree t or less on X equals the average value of f on the whole sphere. In this talk, we show how Delsarte, Goethals, and Seidel used spherical harmonics to prove a lower bound on the size of a spherical design. (In a 2013 paper, Bondarenko, Radchenko, and Viazovska showed that this lower bound is tight, up to a constant factor.)

December 7

Speaker: Jason Prodromidis

Title: It all starts from Erdos-Littlewood-Offord

Abstract: In 1943, in a paper studying the roots of random polynomials, Littlewood and Offord proved a very nice Lemma for sums with random signs. Two years later, Erdos optimized that result, and his result is today referred to as the Erdos-Littlewood-Offord Lemma. GIven this Lemma itself and its proof, it is possible to ask many questions, towards many different directions. The purpose of this talk is to ask and answer as many questions as possible, that naturally arise from the Erdos-Littlewood-Offord Lemma.

December 14

Speaker: Cosmas Kravaris

Title: Ramsey theory for trees

Abstract: Consider the binary tree with N levels. Weight each vertex with the number 2^-l where l is the level of the vertex (i.e. 0, 1, ... N-1). In 2003, Furstenberg and Weiss proved the following Szemeredi-type theorem: for any δ>0 and k, there exists N such that every subset of the binary tree with N levels with density > δΝ contains an "arithmetic replica" of the binary tree with k levels. Their proof relies on recurrence properties of Markov chains on trees. In this talk, we provide a proof of this theorem by Pach, Solymosi and Tardos (2012) using elementary methods (+ assuming Szemeredi's theorem). Pach, Solymosi and Tardos (2012) also give an asymptotically tight construction of colorings of the binary rooted tree with no monochromatic "replicas". Their construction is probabilistic and relies on Azuma's inequality.