Francesco Barioli, Carleton
University, Canada e-mail: fbarioli at math.carleton.ca
Title: Minimum Rank Problem
for unicyclic graphs and decomposable graphs
Abstract: Given a certain
class of matrices, the Minimum Rank Problem consists on determining the
minimum rank of matrices within that class. In particular we will consider
classes of symmetric matrices with a prescribed zero-pattern. Since a zero-pattern
defines in a natural way an undirected graph, an interesting problem is
to investigate the relation between minimum rank and some quantities strictly
related to the graph. For instance, for acyclic graphs, the minimum rank
is determined by the path cover number of the graph. In this talk we will
present a complete characterization of minimum rank for unicyclic graphs
and decomposable graphs.
Leslie Hogben, Iowa State
University, U.S.A. e-mail: lhogben at iastate.edu slides
Title: A variant on the
graph parameters of Colin de Verdiere:
Implications to the minimum rank
of graphs
Abstract: For a given undirected
graph G, the set of all real symmetric matrices having nonzero off-diagonal
entries exactly where the graph G has edges is denoted by S(G). The minimum
rank of G is defined to be the smallest possible rank over all matrices
in S(G). There has been considerable interest recently in the minimal rank
problem and its equivalent formulation, the question of maximal multiplicity
of an eigenvalue of a graph. Building upon work in graph theory involving
maximal nullity of a subclass of S(G), we introduce a new parameter xi
which is based on the maximal nullity of a larger subclass of S(G). For
this new parameter we verify some properties analogous to the ones possessed
by the existing parameters mu, nu. In addition, we apply these properties
associated with xi to learn more about the minimum rank of graphs.
Hein van der Holst, Eindhoven
University of Technology, Netherlands e-mail: H.v.d.Holst at tue.nl
slides
Title: Graphs whose positive
semi-definite matrices have nullity at most three.
Abstract: For any graph
G=(V, E) with n vertices, let M_G be the set of all real valued symmetric
n x n matrices M=[m_i,j] with m_ij = 0 if i not equal to j and i and j
are not connected, m_ij not 0 if i not j and i and j are connected by exactly
one edge, m_ij in R if i not j and i and j are connected by parallel edges,
and m_ii in R for i=1, 2, ..., n. So we allow G to have parallel edges
but no loops. Define mnull+(G) as the maximum nullity attained by any positive
semi-definite matrix in M_G. The problem is to characterize for a fixed
nonnegative integer k the class of graphs G with mnull+(G) <= k. This
has been done for k=1, 2. We present some results for the case k=3.
Wayne Barrett, Brigham Young
University, U.S.A. e-mail: wayne at math.byu.edu slides
Title: The Minimal Rank
Problem for Finite Fields
Abstract: Given a finite
field F and an undirected graph G on n vertices, let S(F, G) be the set
of all symmetric n ¥n matrices over F whose nonzero off-diagonal entries
occur in exactly the positions corresponding to the edges of G. Let mr(F,
G) be the minimum rank of all matrices in S(F, G). The graphs for which
mr(F, G) <= 2 have been characterized in two ways and the description
depends on whether or not char F = 2. There are important similarities
and differences between the results for finite fields and an earlier classification
for infinite fields. Prospects for a description of graphs for which mr(F,
G) <= 3 for any field F will also be discussed.
Dale Olesky, University of
Victoria, Canada e-mail: dolesky at cs.uvic.ca slides
Title Inertially and Spectrally
Arbitrary Sign Patterns
Abstract: Recent results
about inertially and spectrally arbitrary signs patterns are surveyed,
and several examples are given. Techniques that have been used to identify
such sign patterns are discussed and some conjectures are considered.
Pauline van den Driessche,
University of Victoria, Canada e-mail: pvdd at math.uvic.ca
Title: Spectrally arbitrary
star sign patterns
Abstract: An n x n sign
pattern S_n is spectrally arbitrary if, for any given real monic polynomial
g_n(x) of degree n, there is a real matrix having sign pattern S_n and
characteristic polynomial g_n(x). All n x n star sign patterns that are
spectrally arbitrary, and all minimal such patterns, are characterized.
This subsequently leads to an explicit characterization of all n x n star
sign patterns that are potentially nilpotent. It is shown that any super-pattern
of a spectrally arbitrary star sign pattern is also spectrally arbitrary.
Zhongshan Li, Georgia State
University, U.S.A. e-mail: matzli at langate.gsu.edu preprint
Title: Can the minimum rank
of a sign pattern be achieved by a rational matrix?
Abstract: A sign pattern
matrix is a matrix whose entries are from the set {+, -, 0}. The minimum
rank of a sign pattern matrix A is the minimum of the ranks of the real
matrices whose entries have signs equal to the corresponding entries of
A. It is conjectured that the minimum rank of every sign pattern matrix
can be realized by a rational matrix. The equivalence of this conjecture
to several seemingly unrelated statements are established. For some special
cases, such as when A is entrywise nonzero, or the minimum rank of A is
at most 2, or the minimum rank of A is at least n-1 (where A is m x n),
the conjecture is shown to hold. Connections between this conjecture and
the existence of positive rational solutions of certain systems of homogeneous
quadratic polynomial equations with all coefficients equal to ±1
are investigated.
Daniel Hershkowitz, Technion,
Israel e-mail: hershkow at techunix.technion.ac.il slides
Title: The relationship
between the height characteristic of a matrix and its digraph
| Leslie Hogben's
Homepage
Leslie Hogben's Research |
  |
14-Jul-05 |