Introduction to additive combinatorics lecture 3.7 --- using dependent random selection

Показать описание

The Balog-Szemerédi theorem states (in qualitative terms) that if A is a set with many quadruples (x,y,z,w) such that x+y=z+w, then A has a large subset A' such that the sumset |A' + A'| is not too large. Dependent random selection is a technique that can be used (together with a little extra adjustment) to pick out such a subset. In this video I prove a lemma that forms part of a proof of the Balog-Szemerédi theorem. It says that if G is a dense bipartite graph with vertex sets X and Y, then there is a large "well-connected" subset X' of X, in the sense that almost any two vertices x and x' of X' are joined by many paths of length 2.

0:00 Introduction
1:02 The notion of additive energy
7:03 Sets with small sumset have large additive energy
13:20 Sets with large additive energy can have large sumsets
16:23 Informal statement of the Balog-Szemerédi theorem
17:14 Some notation concerning bipartite graphs
22:35 Statement of the main result about paths of length 2
26:11 Quick discussion of dependent random selection
29:26 Proof of the main result
41:17 Quick preview of next video

Timothy Gowers

Рекомендации по теме

Комментарии

Professor Gowers,

First, thank you for making these lectures public! They're characteristically lucid, and it's fun to follow along.

Second, I see you have timestamps with labels in the description. If you add a timestamp for 0:00, called "introduction", etc., then youtube will show the labels as "chapter titles" in the progress bar, which makes it easy to jump around to rewatch certain sections.

HallaSurvivor

How are the ordinal numbers [1.0, 1.8, 2.7...] of the lectures being chosen?

anuragsahay

Introduction to additive combinatorics lecture 3.7 --- using dependent random selection

Introduction to additive combinatorics lecture 1.0 --- What is additive combinatorics?

Peter Varju: Additive combinatorics methods in fractal geometry - lecture 1

Pablo Shmerkin: Additive combinatorics methods in fractal geometry - lecture 1

Information Theory and Additive Combinatorics

MathSoc Galois LS - 'A short introduction to additive combinatorics' by Borys Kuca

Introduction to additive combinatorics lecture 10.1 --- the structure and properties of Bohr sets.

Introduction to additive combinatorics lecture 8.7 --- Bohr sets and Bogolyubov's lemma.

Introduction to additive combinatorics lecture 7.3 -- dual groups and the discrete Fourier transform

Pablo Shmerkin: Additive combinatorics methods in fractal geometry - lecture 2

1. A bridge between graph theory and additive combinatorics

Sumfree Sets (Lecture 1) by Jean-Marc Deshouillers

Introduction to additive combinatorics lecture 13.0 --- The U2 norm and progressions of length 3.

Introduction to additive combinatorics lecture 15.8 -- Using earlier tools, and a symmetry argument.

Fourier Analysis in Additive Problems

Introduction to additive combinatorics lecture 3.7 --- using dependent random selection

Peter Varju: Additive combinatorics methods in fractal geometry - lecture 2

Sumfree Sets by R. Balasubramanian

Introduction to additive combinatorics lecture 14.6 --- The U3 norm is a norm

Introduction to additive combinatorics lecture 14.0 --- The U3 norm and progressions of length 4

Peter Varju: Additive combinatorics methods in fractal geometry - lecture 3

Introduction to additive combinatorics lecture 11.2 --- Part of the proof of Roth's theorem

What is...additive combinatorics?

Introduction to additive combinatorics lecture 7.9 --- Basic Fourier transform properties

Introduction to additive combinatorics lecture 12.1 --- Finishing the proof of Roth's theorem