
TSpace at The University of Toronto Libraries >
School of Graduate Studies  Theses >
Doctoral >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1807/19191

Title:  On Generalizations of Gowers Norms 
Authors:  Hatami, Hamed 
Advisor:  Molloy, Michael 
Department:  Computer Science 
Keywords:  combinatorics Gowers norms 
Issue Date:  1Mar2010 
Abstract:  Inspired by the definition of Gowers norms we study integrals of products of multivariate functions. The $L_p$ norms, certain trace norms, and the Gowers norms are all defined by taking the proper root of one of these integrals. These integrals are important from a combinatorial point of view as inequalities between them are useful
in understanding the relation between various subgraph densities.
Lov\'asz asked the following questions: (1) Which integrals correspond to norm functions? (2) What are the common properties of the corresponding normed spaces? We address these two questions.
We show that such a formula is a norm if and only if it satisfies a H\"older type inequality. This condition turns out to be very useful: First we apply it to prove various necessary conditions on the structure of the integrals which correspond to norm functions.
We also apply the condition to an important conjecture of Erd\H{o}s, Simonovits, and Sidorenko. Roughly speaking, the conjecture says that among all graphs with the same edge density, random graphs contain the least number of copies of every bipartite graph. This had been verified previously for trees, the $3$dimensional cube, and a few other families of bipartite graphs. The special case of the conjecture for paths, one of the simplest families of bipartite
graphs, is equivalent to the BlakleyRoy theorem in linear algebra.
Our results verify the conjecture for certain graphs including all hypercubes, one of the important classes of bipartite graphs, and thus generalize a result of Erd\H{o}s and Simonovits. In fact, for hypercubes we can prove statements that are surprisingly stronger than the assertion of the conjecture.
To address the second question of Lov\'asz we study these normed spaces from a geometric point of view, and determine their moduli of smoothness and convexity. These two parameters are among the most important invariants in Banach space theory. Our result in particular determines the moduli of smoothness and convexity of Gowers norms. In some cases we are able to prove the Hanner
inequality, one of the strongest inequalities related to the concept
of smoothness and convexity. We also prove a complex interpolation theorem for these normed spaces, and use this and the Hanner
inequality to obtain various optimum results in terms of the constants involved in the definition of moduli of smoothness and
convexity. 
URI:  http://hdl.handle.net/1807/19191 
Appears in Collections:  Doctoral Department of Computer Science  Doctoral theses

This item is licensed under a Creative Commons License
Items in TSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
