Organizer: David Conlon & Nets H. Katz & Tom Hutchcroft & Shukun Wu Contacts: Shukun Wu (skwu@caltech.edu)
ON PISIER TYPE PROBLEMS
Marcelo Sales (Emory University)
TBA
Recent progress on the Polynomial Szemeredi Theorem
James Leng (UCLA)
We discuss progress on the polynomial Szemeredi theorem, which in recent years has received a breakthrough due to Peluse who introduced the technique of "degree lowering." We will emphasize how higher order Fourier analysis enters the polynomial Szemeredi theorem and how common techniques used in the field could be used to tackle the problem and some different variations of the problem.
Structure and Complexity of Graphical Designs for Weighted Graphs through Eigenpolytopes
Catherine Babecki (University of Washington)
We extend the theory of graphical designs, which are quadrature rules for graphs, to positively weighted graphs. Through Gale duality for polytopes, we show that there is a bijection between graphical designs and the faces of eigenpolytopes associated to the graph. This bijection proves the existence of graphical designs with positive quadrature weights, and upper bounds the size of a graphical design. We further show that any combinatorial polytope appears as the eigenpolytope of a positively weighted graph. Through this universality, we establish two complexity results for graphical designs: it is strongly NP-complete to determine if there is a graphical design smaller than the mentioned upper bound, and it is #P-complete to count the number of minimal graphical designs.
Extended commonality of paths and cycles via Schur convexity
Joonkyung Lee (Hanyang University)
A graph $H$ is \emph{common} if the number of monochromatic copies of $H$ in a 2-edge-colouring of the complete graph $K_n$ is asymptotically minimised by the random colouring, or equivalently, $t_H(W)+t_H(1-W)\geq 2^{1-e(H)}$ holds for every graphon $W:[0,1]^2\rightarrow [0,1]$, where $t_H(.)$ denotes the homomorphism density of the graph $H$. Paths and cycles being common is one of the earliest cornerstones in extremal graph theory, due to Mulholland and Smith (1959), Goodman (1959), and Sidorenko (1989).
We prove a graph homomorphism inequality that extends the commonality of paths and cycles.
Namely, $t_H(W)+t_H(1-W)\geq t_{K_2}(W)^{e(H)} +t_{K_2}(1-W)^{e(H)}$ whenever $H$ is a path or a cycle and $W:[0,1]^2\rightarrow\mathbb{R}$ is a bounded symmetric measurable function.
This answers a question of Sidorenko from 1989, who proved a slightly weaker result for even-length paths to prove the commonality of odd cycles. Furthermore, it also settles a recent conjecture of Behague, Morrison, and Noel in a strong form, who asked if the inequality holds for graphons $W$ and odd cycles $H$. Our proof uses Schur convexity of complete homogeneous symmetric functions, which may be of independent interest.
Joint work with Jang Soo Kim.
Product sets of arithmetic progressions
Wenqiang Xu (Stanford University)
We prove that the size of the product set of any finite arithmetic progression $\mathcal{A}\subset \mathbb{Z}$ satisfies
\[|\mathcal A \cdot \mathcal A| \ge \frac{|\mathcal A|^2}{(\log |\mathcal A|)^{2\theta +o(1)} } ,\]
where $2\theta=1-(1+\log\log 2)/(\log 2)$ is the constant appearing in the celebrated Erd\H{o}s multiplication table problem. This confirms a conjecture of Elekes and Ruzsa from about two decades ago.
If instead $\mathcal{A}$ is relaxed to be a subset of a finite arithmetic progression in integers with positive constant density, we prove that
\[|\mathcal A \cdot \mathcal A | \ge \frac{|\mathcal A|^{2}}{(\log |\mathcal A|)^{2\log 2- 1 + o(1)}}. \]
This solves the typical case of another conjecture of Elekes and Ruzsa on the size of the product set of a set $\mathcal{A}$ whose sum set is of size $O(|\mathcal{A}|)$.
Our bounds are sharp up to the $o(1)$ term in the exponents.
This is joint work with Yunkun Zhou.
An Elekes-Szabo-type theorem in F_p
Yifan Jing (University of Oxford)
The celebrated Elekes-Szabo theorem asserts that an irreducible algebraic set V in C^3 admits no power-saving if and only if it is in coordinatewise correspondence with a product of connected subgroups of powers of 1-dimensional complex algebraic groups. The result was recently generalized to C^n by Bays and Breuillard. On the other hand, little is known when the ambient field has character p. In this talk, I will talk about an Elekes-Szabo-type result for collinearity on a cubic surface in F_p with a quantitative bound, based on joint work with Tingxiang Zou.
Finding large additive and multiplicative Sidon sets in sets of integers
Yifan Jing (University of Oxford)
Given natural numbers $s$ and $k$, we say that a finite set $X$ of integers is an additive $B_{s}[k]$ set if for any integer $n$, the number of solutions to the equation
\[ n = x_1 + ... + x_s, \]
with $x_1, ..., x_s$ lying in $X$, is at most $k$, where we consider two such solutions to be the same if they differ only in the ordering of the summands. We define a multiplicative $B_{s}[k]$ set analogously. These sets have been studied thoroughly from various different perspectives in combinatorial and additive number theory. For instance, even in the case $s=2$ and $k=1$, wherein such sets are referred to as Sidon sets, the problem of characterising the largest additive $B_{s}[k]$ set in $\{1, 2, ..., N\}$ remains a major open question in the area.
In this talk, we consider this problem from an arithmetic combinatorial perspective, and so, we show that for every natural number $s$ and for every finite set $A$ of integers, the largest additive $B_{s}[1]$ subset $B$ of $A$ and the largest multiplicative $B_{s}[1]$ subset $C$ of $A$ satisfy
\[ \max \{ |B| , |C| \} \gg_s |A|^{\eta_s/s} , \]
where $\eta_s \gg (\log \log s)^{1/2 - o(1)}$.
Sums of linear transformations
Jeck Lim (Caltech)
Let L_1 and L_2 be linear transformations from Z^d to Z^d satisfying certain mild conditions. Then, for any finite subset A of Z^d, we prove a lower bound for |L_1(A) + L_2(A)|, inspired from the Brunn-Minkowski inequality. This partially confirms a (corrected version of a) conjecture of Bukh and is best possible up to the lower-order term for many choices of L_1 and L_2. As an application, we prove a lower bound for |A + c.A| when A is a finite set of real numbers and c is an algebraic number.
A decoupling interpretation of an old argument for Vinogradov's Mean Value Theorem
Zane Li (Indiana University Bloomington)
There are two proofs of Vinogradov's Mean Value Theorem (VMVT), the harmonic analysis decoupling proof by Bourgain, Demeter, and Guth from 2015 and the number theoretic efficient congruencing proof by Wooley from 2017. While there has been recent work illustrating the relation between these two methods, VMVT has been open since 1935. It is then natural to ask: What does old partial progress on VMVT look like in harmonic analysis language? How similar or different does it look from current decoupling proofs? We talk about an old argument that shows VMVT "asymptotically" due to Karatsuba and interpret this in decoupling language. This is ongoing work in progress with Brian Cook, Kevin Hughes, Olivier Robert, Akshat Mudgal, and Po-Lam Yung.
Structural Szemerédi-Trotter Results
Olivine Silier (Caltech)
We study sharp examples of the Szemerédi--Trotter bound: constructions of points and lines in the plane with maximum number of incidences. In joint work with Adam Sheffer, we prove structural properties of such constructions when the number of points and lines are equal, and the points form a Cartesian product. We show there exist many families of parallel lines or many families of concurrent lines.
We also introduce the first infinite family of sharp Szemerédi-Trotter constructions, and in joint work with Larry Guth, the first such family with no underlying lattice structure, which yield sharp discrete Loomis-Whitney constructions as a corollary.
In the work with Adam Sheffer, our techniques are based on the concept of line energy. Rudnev and Shkredov recently introduced this concept and showed how it is connected to point--line incidences. We prove that their bound is tight up to sub-polynomial factors.
Harmonic analysis over $\mathbb{Q}_p$ and decoupling
Zane Li (Indiana University Bloomington)
In this talk, we discuss harmonic analysis over the $\mathbb{Q}_p$. Compared to when working over $\mathbb{R}$, tools such as the uncertainty principle and wavepacket decomposition are not just useful heuristics, but rigorously true. Additionally, decoupling estimates over $\mathbb{Q}_p$ are still strong enough to imply exponential sum applications which have been key applications of real decoupling theorems. This observation along with an optimization of the Guth-Maldague-Wang argument allowed the speaker with Shaoming Guo and Po-Lam Yung to show that the discrete restriction constant for the parabola is $\lesssim_{\varepsilon} (\log N)^{2 + \varepsilon}$. No familiarity of the $p$-adic analysis will be assumed.
Results on the largest sum-free subsets of integers
Shukun Wu (Caltech)
An old conjecture in additive combinatorics asks: what is the largest sum-free subset of any set of N positive integers? Here the word "largest" should be understood in terms of cardinality. In this talk, I will discuss some recent progress on this conjecture, and the analogous conjecture on (k,l)-sum-free sets. The main method we used is Fourier analysis. This is joint work with Yifan Jing.
H-percolation
Brett Kolesnik (University of California, San Diego)
A graph G is said to H-percolate if all missing edges can be added eventually by iteratively completing copies of H minus an edge. This process was introduced by Bollobás (1967) and studied more recently by Balogh, Bollobás and Morris (2012) in the case that G is the Erdős–Rényi graph G(n,p). In this talk, we will discuss our recent work with Zsolt Bartha, which locates the critical percolation threshold p_c when H=K_r, answering an open problem of Balogh, Bollobás and Morris. The proof works for all “reasonably balanced” H (such that H-e is 2-balanced for all edges e in H).
Decoupling inequalities for quadratic forms and beyond
Changkeun Oh (University of Wisconsin–Madison)
In this talk, I will present some recent progress on decoupling inequalities for some translation- and dilation-invariant systems (TDI systems in short). In particular, I will emphasize decoupling inequalities for quadratic forms. If time permits, I will also discuss some interesting phenomenon related to Brascamp-Lieb inequalities that appears in the study of a cubic TDI system. Joint work with Shaoming Guo, Pavel Zorin-Kranich, and Ruixiang Zhang.
Supercritical percolation on finite transitive graphs
Philip Easo (Caltech)
In bond percolation, we build a random subgraph of a graph G by indepedently choosing to retain each edge with probability p. We call these retained edges "open" and the rest "closed". For many examples of G, when we increase the parameter p across a narrow critical window, the subgraph of open edges undergoes a phase transition: with high probability, below the window, it contains no giant components, whereas above the window, it contains at least one giant component. Now take G to be a large, finite, connected, transitive graph with bounded vertex degrees. We prove that above the window, there is exactly one giant component with high probability. This was conjectured to hold by Benjamini in 2001 but was previously only known for large torii and expanders, using methods specific to those cases. The work that I will describe is joint with Tom Hutchcroft.”
Point-box incidences and logarithmic density of semilinear graphs
Minh Tran (University of Notre Dame)
Zarankiewicz’s problem in graph theory asks to determine for each n and k the largest possible number of edges |E| in a K_{k,k}-free bipartite graph G = (V_1, V_2; E) with |V_1|+|V_2|=n. Using polynomial partitioning among other tools, Fox, Pach, Sheffer, Suk, and Zahl established that semialgebraic graphs enjoy stronger bounds than the usual Kovari-Sos-Turan bounds for general graphs; this provides an abstract setting for the Szemerédi-Trotter theorem and related incidence bounds. We obtain even stronger bounds for semilinear graphs, demonstrate that these are close to being optimal, and apply them to show that the number of incidences between points and boxes with axis parallel sides on the plane whose incidence graph is K_{k,k}-free is almost linear. I will also discuss how these results are related to the notion of modularity in model theory. (Joint with Abdul Basit, Artem Chernikov, Sergei Starchenko, and Terence Tao).