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 Bordendinner
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 Bordendinner

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:
The editor-in-chief responsible for this special issue is Richard A. Brualdi.