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.