Rutgers Discrete Mathematics Seminar

Title: A Characterization of Functions with Vanishing Averages Over Products of Disjoint Sets

Speaker: Pooya Hatami, IAS

Date: Monday, April 11, 2016 2:00 pm

Location: Hill Center, Room 425, Rutgers University, Busch Campus, Piscataway, NJ


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 setting. 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 defines quasi-randomness, we confirm this conjecture by showing more generally that similar density conditions for any graph with twin vertices defines 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.