A characterization of functions with vanishing averages over products of disjoint sets

Computer Science/Discrete Mathematics Seminar II
Topic:A characterization of functions with vanishing averages over products of disjoint sets
Speaker:Pooya Hatami
Affiliation:Member, School of Mathematics
Date:Tuesday, April 19
Time/Room:10:30am - 12:30pm/S-101
Video Link:https://video.ias.edu/csdm/2016/0419-Hatami

We characterize all complex-valued (Lebesgue) integrable functions $f$ on $[0,1]^m$ such that $f$ vanishes when integrated over the product of $m$ measurable sets which partition $[0,1]$ and have prescribed Lebesgue measures $\alpha_1,\ldots,\alpha_m$. We characterize the Walsh expansion of such functions $f$ via a first variation argument. Janson and Sos asked this analytic question motivated by questions regarding quasi-randomness of graph sequences in the dense model. We use this characterization to answer a few conjectures from [S. Janson and V. Sos: More on quasi-random graphs, subgraph counts and graph limits]. There it was conjectured that certain density conditions of paths of length 3 define quasi-randomness. We confirm this conjecture by showing more generally that similar density conditions for any graph with twin vertices define quasi-randomness. The quasi-randomness results use the language of graph limits. No back-ground on graph limit theory will be assumed, and we will spend a fraction of the talk introducing the graph limits approach in the study of quasi-randomness of graph sequences. The talk is based on joint work with Hamed Hatami and Yaqiao Li.