Sparse Graph Counting and Kelley--Meka Bounds for Binary Systems

Speaker: Esty Kelman , MIT & BU

Date: Wednesday, September 18, 2024

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-G575

Event Type: Seminar

Room Description: 32-G575

Host: Noah Golowich, MIT

Contact: Noah Golowich, nzg@csail.mit.edu

Relevant URL:

Speaker URL: https://people.csail.mit.edu/ekelman/

Speaker Photo:
None

Reminders to: theory-seminars@csail.mit.edu, seminars@csail.mit.edu

Reminder Subject: TALK: Esty Kelman: Sparse Graph Counting and Kelley--Meka Bounds for Binary Systems

Abstract: Graph counting lemma of Chung, Graham, and Wilson (Combinatorica 1988) is a fundamental result in combinatorics, which states that if a large graph is pseudorandom, then the number of copies of any small graph $H$ in $G$ is close to what is expected from a random graph of the same density. However, this result is only nontrivial when $G$ is a dense graph. In this work, we obtain a counting lemma that works in the sparse setting, and it is well-suited for the density increment arguments in additive combinatorics. In a recent remarkable breakthrough, Kelley and Meka (FOCS 2023) obtained a strong upper bound on the density of sets of integers without nontrivial three-term arithmetic progressions. We combine our counting lemma with other ideas to establish Kelley--Meka type bounds for all linear patterns defined by translation-invariant systems of binary linear forms, i.e., each form depends on exactly two variables. In particular, we obtain strong bounds for the Turan problem in Abelian Cayley sum graphs, i.e. an upper bound on the maximum edge density of an Abelian Cayley sum graph with a clique of a given size. To prove our results, we employ some of the recent technology developed by Kelley and Meka and also the follow-up work by Kelley, Lovett, and Meka (STOC 2024). This talk is based on a joint work with Yuval Filmus, Hamed Hatami and Kaave Hosseini.

Research Areas:
Algorithms & Theory

Impact Areas:

See other events that are part of the Algorithms and Complexity Seminar 2024.

Created by Noah Golowich at Monday, September 16, 2024 at 4:26 PM.