Matrix cut-norms and their relations to graphs

Series
Graph Theory Seminar
Time
Thursday, April 29, 2010 - 12:05pm for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Vladimir Nikiforov – University of Memphis
Organizer
Xingxing Yu
In 1997 Kannan and Frieze defined the \emph{cut-norm} A of a p×q matrix A=[aij] as%A=1pqmax{|iXjYaij|:X[p],Y[q], X,Y}.More recently, Lov\'{a}sz and his collaborators used the norm \left\VertA\right\Vert _{\square} to define a useful measure of similarity between anytwo graphs, which they called \emph{cut-distance. }It turns out that the cut-distance can be extended to arbitrary complexmatrices, even non-square ones. This talk will introduce the basics of thecut-norm and \ cut-distance for arbitrary matrices, and present relationsbetween these functions and some fundamental matricial norms, like theoperator norm. In particular, these relations give a solution to a problem of Lov\'{a}sz.Similar questions are discussed about the related norm\left\Vert A\right\Vert _{\boxdot}=\max\left\{  \frac{1}{\sqrt{\left\vertX\right\vert \left\vert Y\right\vert }}\left\vert \sum_{i\in X}\sum_{j\inY}a_{ij}\right\vert :X\subset\left[  p\right]  ,Y\subset\left[  q\right],\text{ }X,Y\neq\varnothing\right\}  .which plays a central role in the \textquotedblleft expander mixinglemma\textquotedblright.