test Browse by Author Names Browse by Titles of Works Browse by Subjects of Works Browse by Issue Dates of Works

Advanced Search
& Collections
Issue Date   
Sign on to:   
Receive email
My Account
authorized users
Edit Profile   
About T-Space   

T-Space 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: 1-Mar-2010
Abstract: Inspired by the definition of Gowers norms we study integrals of products of multi-variate 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 Blakley-Roy 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

Files in This Item:

File Description SizeFormat
Hatami_Hamed_200908_PhD_thesis.pdf548.71 kBAdobe PDF

This item is licensed under a Creative Commons License
Creative Commons

Items in T-Space are protected by copyright, with all rights reserved, unless otherwise indicated.