[Proof Complexity] MIAO seminar Tue Sep 17 at 14:00 CE(S)T with Morgan Shirley: Large corner-free sets in high dimensions

[Jakob Nordström]

Dear all,

With apologies for the somewhat short notice, we are happy to announce 
that on Tuesday September 17 at 14:00 CE(S)T we will start up the autumn 
semester of the MIAO seminar series with the seminar "Large corner-free 
sets in high dimensions" given by Morgan Shirley at the University of 
Victoria. You find the abstract at the bottom of this message.

We will run this as a hybrid seminar at the University of Copenhagen. 
Local participants are warmly welcome to a room that will be posted on 
the seminar webpage as soon as it is determined --- there is a decent 
chance that this will be room 1-0-14 at Universitetsparken 1 --- while 
other participants are equally warmly welcome to join virtually at 
https://lu-se.zoom.us/j/61925271827 . Please feel free to share this 
information with colleagues who you think might be interested. We are 
also hoping to record the seminar and post on the MIAO Research YouTube 
channel https://youtube.com/@MIAOresearch for people who would like to 
hear the talk but cannot attend.

Most of our seminars consist of two parts: first a 50-55-minute regular 
talk, and then after a break a ca-1-hour in-depth technical presentation 
with (hopefully) a lot of interaction. The intention is that the first 
part of the seminar will give all listeners a self-contained overview of 
some exciting research results, and after the break people who have the 
time and interest will get an opportunity to really get into the 
technical details. (However, for those who feel that the first part was 
enough, it is perfectly fine to just discretely drop out during the 
break. No questions asked; no excuses needed.)

More information about upcoming MIAO seminars can usually be found with 
somewhat better forward notice at 
https://jakobnordstrom.se/miao-seminars/ . If you do not wish to receive 
these announcements, or receive several copies of them, please send a 
message to jn at di.ku.dk.

Best regards,
Jakob Nordström

**********

Tuesday Sep 17 at 14:00 at the University of Copenhagen (exact location 
TBD) and on Zoom
Large corner-free sets in high dimensions
(Morgan Shirley, University of Victoria)

A central question in additive combinatorics is to understand how large 
arithmetic progression-free sets can be. In this talk, I will focus on 
this question for high-dimensional generalization of arithmetic 
progressions (AP) known as corners. A (2-dimensional) corner is a triple 
of the form (x,y),(x+d,y),(x,y+d) for some d > 0 in [N]x[N]. Extending 
this definition to higher dimensions, a k-dimensional corner in [N]^k is 
a (k+1)-tuple defined similarly for some d. While it is known that 
corner-free sets have a vanishingly small density, the precise bounds on 
their size remain unknown.

Until recently, the best-known corner-free sets were derived from 
constructions of AP-free sets: a construction of a 3-term AP-free set by 
Behrend from 1946, and a generalization by Rankin for k-term APs in 
1961. New results by Linial and Shraibman (CCC 2021) and Green (New 
Zealand Journal of Mathematics 2021) changed this picture; they improved 
the upper bound for k=2 by adopting a communication complexity point of 
view.

I will discuss the recent work where the same perspective of 
communication complexity has been employed and obtain the first 
improvement on the upper bound of the size of high-dimensional (k > 2) 
corner-free sets since the original construction of Rankin.

Based on joint work with Lianna Hambardzumyan, Toniann Pitassi, Suhail 
Sherif, and Adi Shraibman.


Jakob Nordström, Professor
University of Copenhagen and Lund University
Phone: +45 28 78 38 11 / +46 70 742 21 98
https://jakobnordstrom.se