Computer Science/Discrete Mathematics Seminar II

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.