A characterization of functions with vanishing averages over products of disjoint sets
Presenter
April 19, 2016
Keywords:
- Computer Science and Discrete Mathematics (CSDM)
Abstract
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.