# Theory and Applications of Matrices described by Patterns

BIRS Workshop 10w5024
Banff International Research Station (BIRS), Banff, Alberta
January 31 - February 5, 2010

organized by
Richard Brualdi, Shaun Fallat, Leslie Hogben, Bryan Shader, Pauline van den Driessche

Updated  February 20, 2010

This page is an ongoing resource for those interested in the topics of the workshop.

OVERVIEW
Three main themes of the workshop are
1. Connections between minimum rank and communication complexity,
2. Spectral graph theory, including applications to extremal problems and spectrally determined graphs,
3. Potential stability
The workshop had overview lectures related to these themes in the mornings and formed focused coolaborative research groups related to the first two themes in the afternoons (for the third theme there was a brainstorming discussion).   On Wednesday evening there were a number of short invited research talks.  However, most participants did not present formal talks.

More information can be found on the BIRS page for this workshop

Due to airline problems, Judi McDonald and Michael Tsatsomeros are not pictured.

More picures (not yet available)

SCHEDULE
Abstracts of talks
Sunday  Meet in Corbett Hall Lounge at 17:45 to walk  dinner together or meet in the Vista Dining Room in the Sally Borden Building.

Monday
Minimum rank and communication complexity
 Start End Place What 7:00 8:15 Sally Borden Breakfast 8:30 9:00 Max Bell 159 Welcome and introduction 9:00 9:45 Max Bell 159 Hogben: minimum rank 9:45 10:30 Max Bell 159 Shader: minimum rank 10:30 11:00 Corbett Lounge break 11:00 11:45 Max Bell 159 Srinivasan: communications complexity 12:00 13:00 Sally Borden lunch 13:00 14:00 Corbett Lounge optional Banff Centre Tour 14:00 14:15 Corbett Lounge group picture 14:15 15:00 Max Bell 159 Forster: communications complexity 15:00 17:00 Max Bell 159 group discussion of  connections between minimum 17:30 19:30 Sally Borden dinner

Tuesday    Spectral graph theory
 Start End Place What 7:00 8:45 Sally Borden Breakfast 9:00 10:15 Max Bell 159 Haemers: spectrally determined graphs 10:15 10:45 Corbett Lounge break 10:45 12:00 Max Bell 159 Nikiforov: spectra of classes of Hermitian matrices 12:15 13:30 Sally Borden lunch 14:00 15:00 Max Bell 159 select problems/form research groups for both Monday and Tuesday topics 15:00 15:15 Corbett Lounge break 15:15 17:45 Max Bell 158, 157, 155 research in groups 18:00 19:30 Sally Borden dinner

Wednesday    Potential stability and research reports
 Start End Place What 7:00 8:45 Sally Borden Breakfast 9:00 10:00 Max Bell 159 Olesky: potential stability 10:00 10:30 Corbett Lounge break 10:30 12:00 Max Bell 159 discussion 12:00 13:30 Sally Borden lunch 13:30 17:30 free time 17:30 18:30 Sally Borden dinner 19:00 19:20 Max Bell 159 Louis Deaett, The rank of a matrix and the girth of its graph 19:20 19:40 Max Bell 159 Jason Grout, Computing bounds for minimum rank with Sage 19:40 20:00 Max Bell 159 Alexander Sherstov, Sign-Rank and the Polynomial Hierarchy in Communication Complexity 20:00 20:20 Max Bell 159 Sebastian Cioaba, On decompositions of complete hypergraphs 20:20 20:40 Max Bell 159 Michael Cavers, On the energy of graphs 20:40 21:00 Max Bell 159 In-Jae Kim , On eventual positivity 21:00 Corbett Lounge reception

Thursday
 Start End Place What 7:00 8:45 Sally Borden Breakfast 9:00 9:10 Max Bell 159 brief whole group meeting 9:10 12:00 Max Bell 158, 157, 155 work in groups, with break 12:00 13:30 Sally Borden lunch 14:00 14:05 Max Bell 159 brief whole group meeting 14:05 15:30 Max Bell 158, 157, 155 work in groups, with break 18:00 19:30 Sally Borden dinner

Friday    wrap up day
 Start End Place What 7:00 8:15 Sally Borden Breakfast 8:30 10:00 Max Bell group reports 10:00 10:30 Corbett break (luggage pick-up 10:15) 10:30 11:00 Max Bell wrap up discussion and plan for future 12:00 13:00 Sally Borden lunch 13:00 Professional Development Center check out

ABSTRACTS

Monday minimum rank and communication complexity

Leslie Hogben   Introduction to minimum rank problems
Abstract

Bryan Shader   Connections between minimum rank problems and communication complexity

Venkatesh Srinivasan   Introduction to Communication Complexity
Abstract

Jurgen Forster   Bounds on the Dimension and the Margin of Embeddings in Half Spaces
Abstract
First, I will define embeddings of pattern matrices in Euclidean half spaces. These embeddings have a dimension and a margin, and I will show how an upper bound on the margin and a lower bound on the dimension can be proven.

Tuesday sepctral graph theory

Willem Haemers   Spectral characterizations of graphs
Abstract

Vladimir Nikiforov   The spectra of Hermitian matrix properties
Abstract

Wednesday potential stability and research reports

Dale Olesky
Potential Stability
Abstract     SLIDES

Research reports

Michael Cavers
On the energy of graphs
Abstract

Sebastian Cioaba       On decompositions of complete hypergraphs
Abstract: In this talk, I will study the minimum number of complete /r/-partite
/r/-uniform hypergraphs needed to partition the edges of the complete
/r/-uniform hypergraph on /n/ vertices. This problem is the hypergraph
extension of the classical Graham-Pollak theorem.

Louis Deaett              The rank of a matrix and the girth of its graph
Abstract: In the case of a positive semidefinite matrix, a result of Moshe Rosenfeld provides a lower bound on the rank when the graph of the matrix is triangle-free.  We'll show a new proof of this bound.
We also consider the possibility of generalizing the bound under a stronger condition on the girth of the graph.

Jason Grout                Computing bounds for minimum rank with Sage
Abstract: I will explain and give examples of a suite of functions in Sage that use a number of bounds from literature to compute minimum rank bounds in Sage.  The suite also includes a lookup table of minimum ranks for all graphs with fewer than 8 vertices.  This program is currently being formatted for inclusion in Sage, and will then be in every copy of Sage, enhancing Sage's comprehensive graph functionality.  These functions are a collaborative work between Laura DeLoss, Tracy Hall, Josh Lagrange, Tracy McKay, Jason Smith, Geoff Tims, and myself, and were initially developed in Leslie Hogben's early graduate research class at Iowa State University.  For an earlier version of the program, see \url{http://arxiv.org/abs/0812.1616}.

In-Jae Kim  On eventual positivity
Abstract: An $n \times n$ real matrix $A$ is said to be eventually positive if there exists a positive integer $k_0$ such that $A^{k} > 0$ (entrywise positive) for all positive integer $k \geq k_0$. An $n \times n$ sign pattern $\mathcal{A}$ is potentially eventually positive (PEP) if $\mathcal{A}$ has a realization that is eventually positive. In this talk, some necessary or sufficient conditions for a sign pattern to be PEP are given.  In addition, it is shown that the minimum number of positive entries in a PEP sign pattern is $n+1$.

Alexander Sherstov
Sign-Rank and the Polynomial Hierarchy in Communication Complexity
Abstract

LINEAR ALGEBRA AND ITS APPLICATIONS

Special Issue on the occasion of the Workshop at the Banff International Research Station titled:
"Theory and Applications of Matrices described by Patterns" (January 31 - February 5, 2010).

The themes of this workshop are:
1. Connections between minimum rank and communication complexity.
2. Spectral graph theory, including applications to extremal problems and spectrally determined graphs.
3. Potential stability.
Papers within the scope of the Workshop are solicited from all interested whether or not a participant in the Workshop. The deadline for submission of papers is October 1, 2010.  Papers for submission should be sent to one of the four special editors, preferably as PDF files in e-mail attachments. They will be subject to normal refereeing procedures according to LAA standards.

Special Editors:
• Shaun Fallat, University of Regina, SK (Canada) <sfallat@math.uregina.ca>
• Leslie Hogben, Iowa State University, IA (USA) <lhogben@iastate.edu>