- 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{|∑i∈X∑j∈Yaij|: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.