Abstracts of Discrete Math Seminars at SFU

This page changes frequently. Press "Reload" on your browser to get the latest information




Event:   Discrete Math/CECM Seminar
Speaker: Reza Naserasr
Affiliation: Simon Fraser University
Email:   rnaseras@math.sfu.NOSPAM.ca (remove NOSPAM.)
Date:    Tuesday, 30 January 2001
Time:    3:30 - 4:20
Place:   K9509, SFU
Title:   On $\Delta$-critical graphs
Abstract:
A graph is  $\Delta$-critical  if it has chromatic number
equal to its maximum degree, and every proper subgraph has
a strictly smaller chromatic number.
In 1977, Borodin and Kostochka conjectured that 
for $\Delta \geq 9$ there is no $\Delta$-critical graph.
If true, this would be an extension of Brooks theorem. 
In 1997 B. Reed proved this conjecture for large $\Delta$,
using the probabilistic method.
Here we show that any counterexample to this conjecture
must have at least $3 \Delta - 6$ vertices.





Event:   Discrete Math/CECM Seminar
Speaker: Brett Stevens
Affiliation: Simon Fraser University
Email:   brett@math.sfu.NOSPAM.ca (remove NOSPAM.)
Date:    Wednesday, 31 January 2001
Time:    3:30 - 4:20
Place:   K9509, SFU
Title:   Packing and Covering Designs
Abstract:
 Not Available








Event:   Discrete Math/CECM Seminar
Speaker: Luis Goddyn
Affiliation: Simon Fraser University
Email:   goddyn@math.sfu.NOSPAM.ca (remove NOSPAM.)
Date:    Tuesday, 6 February 2001
Time:    3:30 - 4:20
Place:   K9509, SFU
Title:   Range-restricted flows in regular matroids
Abstract:
A matrix is {\it totally unimodular\/} (TUM) if all
of its subdeterminants equal $0$, $1$ or $-1$.
Let $A$ be TUM, and let $R$ (the `restricted range')
be a finite set of positive real numbers.
An {\it $R$-flow} is a real vector $f$ in the nullspace
of $A$ such that the absolute value of each entry
of $f$ belongs to $R$.

We prove that if $A$ has an $R$-flow, then $A$
has a $\{ 1,2, \ldots, k \}$-flow, where $k = |R|$.

This result generalizes properties of currents and tensions
in graphs.  For example, the vertex-arc incidence matrix $A(G)$
of a directed graph $G$ is TUM.  A circulation of fluid through
the arcs of a $G$ corresponds to an element of the nullspace
of $A(G)$.  Regarding tensions, we have that $G$ has chromatic
number at most $k+1$ if and only if the parity-check matrix
of $A(G)$ has a $\{ 1,2, \ldots, k \}$-flow.

The proof of the theorem relies on Seymour's
decomposition theorem for TUM matrices, along with
two graph-theoretic results -- one of whose proofs is
related to a number-theoretic conjecture of J.~Wills,
and a `gluing lemma' whose proof hinges on an application
of the Tutte polynomial.  This is joint work with Matt DeVos.








Event:   Discrete Math/CECM Seminar
Speaker: Jarik Nesetril
Affiliation: Charles University, Prague
Email:   nesetril@kam.ms.mff.cuni.NOSPAM.cz (remove NOSPAM.)
Date:    Tuesday, 13 February 2001
Time:    3:30 - 4:20
Place:   EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:   On a homomorphism duality for oriented trees
Abstract:
We want to explain the following recent result of C. Tardif and the speaker:
For every (finite) oriented tree T there exists a finite graph H_T such that
for every graph G we have:

    T is not homomorphic to G iff G is homomorphic to H_T.

This generalizes the Gallai-Roy theorem and has relevance to model theory, 
generalized colorings and posets.







Event:   Discrete Math/CECM Seminar
Speaker: Valentine Kabanets
Affiliation: Institute for Advanced Study
Email:
Date:    Tuesday, 20 February 2001
Time:    2:30 - 3:15
Place:   EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:   In search of an easy witness: Exponential time versus probabilistic polytime.
Coauthors: Russell Impagliazzo and Avi Wigderson.

Abstract:
Restricting the search space {0,1\}^n to the set of truth tables
of ``easy'' Boolean functions on log n variables, as well as using some
known hardness-randomness tradeoffs, we establish a number of results
relating the complexity of exponential-time and probabilistic
polynomial-time complexity classes. In particular, we show that NEXP
\subset P/poly iff NEXP=MA; this can be interpreted to say that no
derandomization of MA (and, as a corollary, of promise-BPP) is possible
unless NEXP contains a hard Boolean function. We also prove several
downward closure results for ZPP, RP, BPP, and MA; e.g., we show EXP=BPP
iff EE=BPE, where EE is the double-exponential time class and BPE is the
exponential-time analogue of BPP.







Event:   Discrete Math/CECM Seminar
Speaker: Wayne Broughton    
Affiliation: Okanagan University College
Email:
Date:    Tuesday, 20 February 2001
Time:    3:40 - 4:25
Place:   EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:   Quasi-3 Designs and Hadamard Matrices
Abstract:
 A $(v,k,\lambda)$-symmetric design is an incidence structure consisting of a
set of $v$ points and a collection of $v$ subsets (called {\it blocks}),
such that every block contains exactly $k$ points and any two distinct
points are together contained in exactly $\lambda$ blocks.  A symmetric
design is said to be {\it quasi-3} if there exist two numbers $x$ and $y$ so
that any three distinct points are together contained in either $x$ or $y$
blocks.

A {\it quasi-3 regular Hadamard matrix} is a square matrix $H$ with entries
$\pm 1$, constant row sums, and such that pairs of distinct rows are
orthogonal.  It is also {\it quasi-3} if, given any three distinct rows, the
number of columns in which all three rows have a $-1$ can take one of only
two possible values ($x$ and $y$).  Quasi-3 regular Hadamard matrices are
equivalent to certain kinds of quasi-3 symmetric designs.

In this talk I will go over some of the known results on quasi-3 designs and
an application in coding theory, describe ongoing attempts to construct new
quasi-3 regular Hadamard matrices, and discuss some open problems and the
possibility of classifying quasi-3 symmetric designs.  The talk will
primarily be expository.








Event:   Discrete Math/CECM Seminar
Speaker: Pavol Hell
Affiliation: SFU
Email:   pavol@cs.sfu.NOSPAM.ca (remove NOSPAM.)
Date:    Wednesday, 28 February 2001
Time:    3:30 - 4:20
Place:   K9509, SFU
Title:   List homomorphisms and partitions
Abstract:
I will discuss results on complexity of these
generalizations of colourings, with emphasis
on new results on list homomorphisms of general
graphs.




Event:   Discrete Math/CECM Seminar
Speaker: Steph Durocher
Co-authors:	Ellen Gethner and Alex Brodsky
Affiliation: UBC 
Email:
Date:    Tuesday, 06 March 2001
Time:    3:30 - 4:20
Place:   EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:   The tangled tale of the rectilinear crossing number of K_n.
Abstract:
Scheinerman and Wilfassert that "an important open problem in the study
of graph embeddings is to determine the rectilinear crossing number of the
complete graph $K_n$." A "rectilinear drawing of $K_n$" is an arrangement
of $n$ vertices in the plane, every pair of which is connected by an edge
that is a line segment. We assume that no three vertices are collinear,
and that no three edges intersect in a point unless that point is an
endpoint of all three. The "rectilinear crossing number of $K_n$" is the
fewest number of edge crossings attainable over all rectilinear drawings
of $K_n$. 

For each $n$ we construct a rectilinear drawing of $K_n$ that has
the fewest number of edge crossings and the best asymptotics known to
date. Moreover, we give some alternative infinite families of drawings of
$K_n$ with good asymptotics. Finally, we mention some old and new open
problems. 



Event:   Discrete Math/CECM Seminar
Speaker: Richard Anstee
Affiliation: UBC
Email:   anstee@math.ubc.NOSPAM.ca (remove NOSPAM.)
Date:    Tuesday, 13 March 2001
Time:    3:30 - 4:20
Place:   EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:	 Small Forbidden Configurations
Coauthors: R. Ferguson, J. Griggs and A. Sali
Abstract:
The extremal problem associated with forbidden
configurations is quite basic and yet only parts of the complete answer
are known. In matrix terminology, we consider a chosen
k x p (0,1)-matrix F (the `forbidden configuration') and 
an m x n (0,1)-matrix A with no repeated columns (the `set system')
and we assume A has no submatrix which is a row and column permutation
of F. We then seek bounds on n in terms of m. The general result
of Vapnik and Chervonenkis, Sauer, Perles and Shelah shows that
n is O(m^{k-1}) if F has no repeated columns and Furedi showed that 
n is O(m^k) in general. But what properties of F determine the asymptotically
correct bounds? I'll consider some results for small k=2,3.
Some interesting use of graph theory is made.



Event:   PIMS/Discrete Math Seminar
Speaker: Brett Stevens
Affiliation: SFU
Email:   brett@math.sfu.NOSPAM.ca (remove NOSPAM.)
Date:    Tuesday, 20 March 2001
Time:    3:30 - 4:20
Place:   EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:   Packing Arrays II: Beyond Codes, the Triumphant Return of Designs!
Abstract:
In "Packing Arrays, Matching Packings and Uniform Partition Designs'
(1999 combinatorics seminar) I investigated the adaptation of powerful
coding theory bounds and constraints to packing arrays, their size and
construction.  In this sequel I will briefly re-cap these previous
results but discuss a new bound/construction using more traditional
design theory.  I will show that in its range of applicability, this
bound is either  equal to or better than the coding theory bound and
is constructive in a large number of cases.  I will close with a
connection between existence/non-existence of projective planes and
packing arrays.  Several interesting conjectures will be posed (which
are ideal candidates for student research projects)



Event:   PIMS/Discrete Math Seminar
Speaker: Lou Ibarra
Affiliation: Univ of Victoria
Email:
Date:    Tuesday, 27 March 2001
Time:    2:30 - 3:20
Place:   EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:	 Dynamic algorithms for chordal and interval graphs.
Abstract:
We introduce the "clique-separator graph" representation of a
chordal graph, which provides significantly more information about the
graph's structure than the well-known clique tree representation.
We present fundamental properties of the clique-separator graph and
additional properties when the input graph is interval.  We then
introduce the "train tree" representation of interval graphs and
use it to decide whether there is a certain linear ordering of the
graph's maximal cliques.  This yields a fully dynamic algorithm to
recognize interval graphs in O(n log n) time per edge insertion or
deletion.  The clique-separator graph may lead to dynamic algorithms for
every proper subclass of chordal graphs, and the train tree may lead to
fast algorithms for problems on interval graphs.




Event:   PIMS/MITACS computational algebra  and Discrete Math Seminar
Speaker: Jonathan Jedwab
Affiliation: Mathematics, Cryptography and Security Group
Email:
Hewlett-Packard Labs, Bristol, UK
Date:    Tuesday, 27 March 2001
Time:    3:30 - 4:20
Place:   EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:   Combinatorial Design Theory in an Industrial Research Lab 
Abstract:
Combinatorial design theory - in broad terms the study of the
arrangement of objects subject to constraints - provides a natural
way to express and solve problems in the design of digital communication
devices and systems. I have worked with communications engineers at
Hewlett-Packard for over twelve years, applying methods of combinatorial
design theory to problems of digital design arising in instrumentation,
wired networking, storage, and wireless transmission.

I shall give several examples of the kinds of mathematical objects
studied in combinatorial design theory. I shall then describe two
contrasting digital communication applications, highlighting how
different an industrial approach can be from a purely academic one.



Event:   CECM/Discrete Math Seminar
Speaker: William Evans
Affiliation: UBC
Email:
Date:    Wednesday, 28 March 2001
Time:    2:30 - 3:20
Place:   K9509, SFU
Title:	 Recovering lines with fixed linear probes
Abstract:
Suppose the only access we have to an arrangement of $n$ input lines is
to "probe" the arrangement with vertical lines.  A probe returns a set
of {\em probe points} which are the intersections of the probe's
vertical line with all input lines.  We assume that none of the input
lines is vertical, so a probe line intersects every input line.  Our
goal is to reconstruct the set of input lines using a small number of
probe lines.  Our task is made more difficult by the fact that we want
one set of probe lines that will allow us to reconstruct any input
arrangement of $n$ lines.

I'll talk about two probe models and some of the algorithms for
reconstructing an arrangement from probe points, but I'll spend most of
the time talking about some new bounds on the number of probe lines that
are needed to enable unique reconstruction.



Event:   CECM/Discrete Math Seminar
Speaker: Petr Lisonek
Affiliation: SFU
Email:   plisonek@math.sfu.NOSPAM.ca (remove NOSPAM.)
Date:    Wednesday, 28 March 2001
Time:    3:30 - 4:20
Place:   K9509, SFU
Title:   Classification of Binary Linear Codes with Small Codimension
Abstract:
We will use the natural correspondence between linear codes and
multisets of points in finite projective spaces to develop an
algorithm for the classification of all binary linear codes 
with given length and dimension up to isomorphism.  Special attention
will be paid to the classification of codes with small codimension
and to their applications in statistical experiment design.





Event:   PIMS/Discrete Math Seminar
Speaker: Mateja Sajna
Affiliation: Capilano College
Email:   msajna@math.sfu.NOSPAM.ca (remove NOSPAM.)
Date:    Tuesday, 03 April 2001
Time:    3:30 - 4:20
Place:   EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:	 Decomposition of complete graphs into cycles of a fixed length
Abstract:
This talk examines the conditions under which a 
complete graph admits a decomposition into cycles of some fixed 
length. Since the existence of such a decomposition requires that 
the degrees of all vertices be even, the complete graph must have 
an odd number of vertices. However, it seems natural to extend this 
problem to complete graphs of even order with a 1-factor removed 
since these graphs have even degree and are "almost" complete.

The question thus becomes as follows: When does $K_n$ (the 
complete graph) or $K_n-I$ (the complete graph minus a 1-factor) 
admit a decomposition into cycles of a fixed length $m$? A 
relatively recent result by Alspach, Gavlas, and Sajna shows that 
this is possible whenever the parameters $m$ and $n$ satisfy the 
obvious necessary conditions.

In this talk we present an overview of the constructive proof of this 
result together with a summary of partial and related results 
relevent to the techniques of the proof from the more than 150 year-
long history of this problem.





Event:   CECM/Discrete Math Seminar
Speaker: Veselin Jungic
Affiliation: SFU
Email:   vjungic@math.sfu.NOSPAM.ca (remove NOSPAM.)
Date:    Wednesday, 04 April 2001
Time:    3:30 - 4:20
Place:   K 9509
Title:   Diophantine Ramsey Theory and Recurrence in Dynamical Systems
Abstract:
The main purpose of this talk is to discuss and illustrate the
connection between some problems of van der Waerden type, i.e., problems
of locating patterns that occur monochromatically for an arbitrary finite 
coloring of $\bbf{Z}$ or $\bbf{N}$, on the one hand, and topological
dynamics and ergodic theory on the other hand.

The equivalence between van der Waerden's theorem and its topological
version and the equivalence between the polynomial Szemeredi theorem and
its ergodic version will be given.



Event:   PIMS/Discrete Math Seminar
Speaker: Ladislav Stacho
Coauthors: Luis Goddyn
Affiliation: Simon Fraser University
Email:   lstacho@math.sfu.NOSPAM.ca (remove NOSPAM.)
Date:    Tuesday, 10 April 2001
Time:    3:30 - 4:20
Place:   EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:	 Edge Disjoint Cycles Through Prescribed Vertices
Abstract:
We present a sufficient condition for the existence of several
edge disjoint cycles, each containing a prescribed set of vertices
in a graph.  This generalizes several previously known Ore-type results.
More precicely, we have the following result.

 Let W be a subset of the vertices of a graph G of order n, let k>0.
 Suppose the induced graph G[W] is 2(k+1)-connected.
 Suppose further that for any two vertices having distance two in G[W],
 at least one of the two has degree at least n/2+2k in G.
 Then G contains k+1 pairwise edge disjoint cycles where each cycle
 contains all vertices in W.

A main lemma is a Hamilton-cycle packing result regarding
complements of bipartite graphs.  This lemma may be of greater
interest to practitioners than the main theorem!  This is joint work
with Luis Goddyn.




Event:   PIMS/Discrete Math Seminar
Speaker: Nancy Ann Neudauer
Affiliation: Pacific Lutheran University
Email:   neudauna@plu.NOSPAM.edu (remove NOSPAM.)
Date:    Tuesday, 17 April 2001
Time:    3:30 - 4:20
Place:   EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:   Bicircular Matroids and Transversal Presentations
Abstract:
Matroids are everywhere.  Vector spaces are matroids.
Matroids are useful in situations that are modelled
by both graphs and matrices.  Bicircular
matroids model generalized network flow problems 
whose algorithms are more efficient than those
available for general linear programming codes.

Let $G$ be a graph (loops and parallel edges allowed)
with vertex set $V=\{1,2,\ldots,n\}$ and edge set $E$.
In the classical matroid associated with a graph, a set of edges
is independent in the matroid if it contains no cycles, and 
the circuits of the matroid are the single cycles of $G$.
The {\it bicircular matroid} of $G$ is the matroid $B(G)$ 
defined on $E$ whose circuits are the
subgraphs which are subdivisions of one of the following graphs:
(i) two loops on the same vertex, (ii) two loops joined by an edge, 
(iii) three edges joining the same pair of vertices.

The bicircular matroid is known to be a transversal matroid
and thus can be represented by a family of sets, called a
presentation.  
It has been known for some time that the maximal presentation of
a transversal matroid is unique.  In general, a transversal matroid
has many minimal presentations.  We show how, given a graph $G$, one 
could find a minimal presentation for $B(G)$ and, from that, find all
other minimal presentations.

We demonstrate this with the graph of a wheel on six vertices.  
The problem reduces to searching for trees and single cycles.  This 
example led to the general classification of the minimal presentations
of an arbitrary bicircular matroid.




Event:   PIMS/Discrete Math Seminar
Speaker:  John Mighton
Affiliation: Fields Institute, Toronto
Email:   jmighton@fields.utoronto.NOSPAM.ca  (remove NOSPAM.)
Date:    Thursday, 10 May 2001
Time:    3:30 - 4:20
Place:   EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:   A New Reduction of Graph Theory and Binary Matroids
Abstract:
Matroids and Binary Matroids are powerful
generalizations of graphs. We construct an isomorphism
between binary matroids and bipartite graphs.
Under this mapping, graphs, knots, finite groups and
many infinite groups may be represented as bipartite
graphs: in the case of finite groups and three connected
graphs the reduction is complete. The bipartite graphs
were first used to compute the Jones polynomial and
were subsequently found to give a reduction of knot
theory up to mutation. Viewed as representations of
binary matroids, the graphs have many remarkable
features which reveal new structure in diverse areas
of mathematics.




Event:   PIMS/Discrete Math Seminar
Speaker:  Sergei Bespamyatnikh
Affiliation: Computer Science, U. British Columbia
Email:   besp@cs.ubc.NOSPAM.ca  (remove NOSPAM.)
Date:    Tuesday, 15 May 2001
Time:    3:30 - 4:20
Place:   EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:   Graph of triangulations of convex polytopes in R^3
Abstract:
A triangulation of a finite point set A in R^d is a geometric 
simplicial complex which covers the convex hull of A and whose 
vertices are points of A. We study the graph of triangulations 
whose vertices represent the triangulations and whose edges 
represent geometric bistellar flips.
The main result is that the graph of triangulations in three 
dimensions is connected when the points of A are in convex 
position. We introduce a tree of triangulations and 
present an algorithm for enumerating triangulations
in O(loglogn) time per triangulation.





Event:   Discrete Math Seminar
Speaker: Matt DeVos
Affiliation: Princeton University
Email:   mdevos@math.sfu.NOSPAM.ca (remove NOSPAM)
Date:    Tuesday, 26 June, 2001
Time:    3:30 - 4:20
Place:   K9509, SFU
Title:   Packing T-joins
Abstract:
Several graph concepts such as flows, paths, matchings
and matroid extensions are embraced by the theory of T-joins.
Let T be an even subset of vertices of graph G.
A T-join is (the edge set of) any subgraph of G whose 
odd-degree vertices coincide with T. 
A T-cut is the set of edges having exactly one end in X,
where X is any subset of vertices with |X \cap T| odd.
Let \nu  be the maximum number of pairwise disjoint T-joins in G.
Let \tau be the minimum cardinality of a T-cut.

Since every T-join intersects every T-cut, nu <=     \tau.
Menger's theorem asserts that for |T|=2,    \nu  =     \tau.
However, there are examples (G,T) for which \nu  = 2/3 \tau.
Here we prove that every (G,T) satisfies    \nu >= 1/3 \tau.
And if T is the odd-degree vertices of G,   \nu >= 1/2 \tau.
This is joint work with Paul Seymour.




Event:   PIMS/Discrete Math Seminar
Speaker: Moishe Rosenfeld
Affiliation: University of Washington
Email:   moishe@math.sfu.NOSPAM.ca (remove NOSPAM)
Date:    Tuesday, 10 July, 2001
Time:    3:30 - 4:20
Place:   EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:   Hamiltonian Decomposition of Prisms over cubic graphs
Abstract:
The prism over a cubic graph G is obtained by taking two disjoint
copies of G and adding edges between "same" vertices in the two copies,
or a 1-factor. Alternatively, it is GxK_2, the cartesian product of G and K_2.
If G is cubic then GxK_2 is 4-regular. If G is cubic, 3-connected then GxK_2 is
hamiltonian. B. Alspach and M. Rosenfeld conjectured that if G is cubic
and 3-connected then GxK_2 admits a hamiltonian decomposition.

There are infinitely many classes of cubic graphs for which this conjecture
was verified.

In this talk I'll describe the background, present methods to "inflate"
cubic graphs G for which GxK_2 admit a hamiltoian decomposition to "bigger"
cubic graphs with the same property. We hope to obtain enough "inflations"
to prove at least the original "geometric" problem: prisms over simple
3-polytopes admit a Hamiltonian decomposition or prisms over hamiltonian
3-connected cubic graphs admit a hamiltonian decomposition.

This is joint work with Roman Cada and Zdenek Ryjacek.




Event:       Discrete Math Seminar
Speaker:     Claude Tardif
Affiliation: University of Regina
Email:       ctardif@cs.sfu.NOSPAM.ca (remove NOSPAM)
Date:        Tuesday, 17 July, 2001
Time:        3:30 - 4:20
Place:       K 9509, SFU
Title:       Fractional aspects of Hedetniemi's conjecture
Abstract:
The categorical product $G \times H$ of two graphs $G$ and $H$
is the graph on $V(G) \times V(H)$, where $((u,v),(u',v'))$
is an edge if and only if $uu'$  and $vv'$ are edges in $G$ and $H$.
The chromatic number of a categorical product of graphs
is the object of a long standing conjecture (Hedetniemi, 1966):

$$ \chi(G \times H) = \min \{ \chi(G), \chi(H) \}. $$

We derive a lower bound in terms of fractional chromatic numbers:

$$ \chi(G \times H) \geq 1/2 \min \{ \chi_f(G), \chi_f(H) \}.$$

We discuss the possible impact of this result on Hedetniemi's
conjecture.  In particular, it has long been known that
Hedetniemi's conjecture is false in the case of directed graphs.
However our result also holds for directed graphs, and furthermore
the constant $1/2$ may be best possible in this case. Therefore an
improvement on the constant in the case of undirected graphs would
provide a significant distinction between directed graphs and 
undirected graphs.



Event:       Discrete Math/PiMS Seminar
Speaker:     Luis Goddyn
Affiliation: Simon Fraser University
Email:       goddyn@math.sfu.NOSPAM.ca (remove NOSPAM.)
Date:        Tuesday, 18 September 2001
Time:        3:30 - 4:20
Place:       EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:       Binary Gray Codes with Long Bit Runs
Abstract:
The n-cube has 2^n vertices, and edges which naturally partition
into n `parallel classes'.  Certain applications call for a Hamilton
cycle in the n-cube such that any two edges from the same parallel
class are widely separated along the cycle.  We show how to construct
such a cycle where such edge pairs are at distance at least 
                 n - 2.001 lg(n).
That is, there exists a cyclic ordering of {0,1}^n such that
adjacent words differ in exactly one (coordinate) bit,
and such that no bit changes its value twice
in any subsequence of n - 2.001 lg(n)  consecutive words.
Such Gray codes are `locally distance preserving' in that Hamming
distance equals index separation for nearby words in the sequence.
This joint work with P. Gvozdjak settles a 13-year old conjecture.




Event:       Discrete Math/PiMS Seminar
Speaker:     Louis Ibarra
Affiliation: Simon Fraser University
Email:       ibarra@cs.sfu.NOSPAM.ca (remove NOSPAM.)
Date:        Tuesday, 25 September 2001
Time:        3:30 - 4:20
Place:       EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:       The clique-separator graph for chordal graphs and its subclasses
Abstract:
The clique-separator graph is a new representation of chordal graphs that 
provides more information about the graph's structure than the well known 
clique tree representation.  Moreover, when $G$ is interval, proper 
interval, or split, the clique-separator graph has additional structural 
properties.  The clique-separator graph leads to new characterizations of 
proper interval graphs and split graphs, and it may lead to analogous 
results for other subclasses of chordal graphs.




Event:       Discrete Math/PiMS Seminar
Speaker:     Ladislav Stacho
Affiliation: Simon Fraser University
Email:       lstacho@sfu.NOSPAM.ca (remove NOSPAM.)
Date:        Tuesday, 02 October 2001
Time:        3:30 - 4:20
Place:       EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:       New upper-bound for chromatic number
Abstract:
We prove that the chromatic number of any graph G satisfies
\chi(G) \leq \Delta_2(G)+1, where \Delta_2(G) is the largest degree
that a vertex v can have subject to the condition that v is adjacent
to a vertex whose degree is at least as big as its own.  Moreover, 
we show that the upper bound is best possible in the following sense:
If \Delta_2(G)\geq 3, then to determine whether \chi(G) \leq \Delta_2(G)
is an NP-complete problem. The upper bound and its corollaries extend several
well-known upper bounds for \chi(G), e.g. upper bound by R.L. Brooks
(Proc. Cambridge Phil. Soc, 1941), and by O.V. Borodin, and A.V. Kostochka
(J. Combin Theory, 1977).



Event:       Discrete Math/PiMS Seminar
Speaker:     Amitava Bhattacharya
Affiliation: School of Mathematics, Tata Institute of Fundamental Research, 
             Mumbai, India
Host:        Binay Bhattacharya, Computer Science Department, SFU
Email:       amitava@sfu.NOSPAM.ca (remove NOSPAM.)
Date:        Tuesday, 09 October 2001
Time:        3:30 - 4:20
Place:       EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:       A short proof of a EKR type theorem.
Abstract:
Problem: Given $n$ real numbers $x_1, \ldots x_n$, which satisfies
$\sum_{i=1}^{i=n} \ge 0$ does there exist $\binom(n-1,k-1)$ subsets of size $k$
such that the sum of the elements in each of the k-sets is non negative. 

Conjecture: There does exist $\binom(n-1,k-1)$ subsets of size $k$ with
the desired property, if $n \ge 4k$.

This is true if $k$ divides $n$ and it was shown by N. M. Singhi and
N.  Manickam. I plan to present a short proof for the case $k$ divides $n$
and show that the conjecture  is true when "n" is sufficiently large compared
to $k$.




Event:       Discrete Math/PiMS Seminar
Speaker:     Juan  Montellano
Affiliation: Instituto de Matematicas. UNAM
Email:       josem@sfu.NOSPAM.ca (remove NOSPAM.)
Date:        Tuesday, 16 October 2001
Time:        3:30 - 4:20
Place:       EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:       Anti-Ramsey Problems
Abstract:
In 1973, Erd\"os, Simonovits and S\'os started the investigation of {\it
anti-
Ramsey problems} for graphs. This kind of problems can be described 
as follows: given a graph $G$ and a set $F$ of subgraphs of $G$, 
determine the minimum integer $h(G|F)$ such that every edge colouring 
of  $G$, using exactly $h(G|F)$ colours, leaves at least one {\it totally 
multicolored}  member of $F$, where a  subgraph $H$ of $G$ is said to 
be totally multicoloured  if  $H$ contains no two edges of the same colour. 

This talk is about some recent results concerning that sort of anti-
Ramsey	problems.





Event:       Discrete Math/PiMS Seminar
Speaker:     Ladislav Stacho
Affiliation: Simon Fraser University
Email:       lstacho@sfu.NOSPAM.ca (remove NOSPAM.)
Date:        Tuesday, 23 October 2001
Time:        3:30 - 4:20
Place:       EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:       Spannin trees with bounded number of branch vertices.
Coauthors:   Luisa Gargano, Pavol Hell, and Ugo Vaccaro
Abstract:
A vertex of degree >= 3 in a spanning tree of a graph is called a branch 
vertex. Following this notation, a hamiltonian path is a spanning tree
without branch vertices. A natural generalization of hamiltonian path is
to consider spanning trees with given number of branch vertices. 

We will discuss some applications of spanning trees with bounded number
of branch vertices to modern network technologies. We also present some
lower bounds and upper bounds on the number of branch vertices in a
spanning tree. In particular, we present a sufficient condition for a
K_1,3-free graph to contain a spanning tree with at most k branch vertices.
As a corollary with k=0, we obtain known sufficient condition for the 
existence of a hamiltonian path in a K_1,3-free graph proved by 
Matthews and Sumner in 1985.




Event:       Discrete Math/PiMS Seminar
Speaker:     Bill McCuaig
Affiliation: 
Email:       wmccuaig@attcanada.NOSPAM.ca (remove NOSPAM)
Date:        Tuesday, 30 October 2001
Time:        3:30 - 4:20
Place:       EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:       The hat game.
Abstract:
A team consists of 3 players. Each is given a red or blue hat. The
colour of each hat is determined by a coin toss, with the outcome of one
coin toss having no effect on the others. Each player can see the other
players' hats but not their own. The players are not allowed to
communicate once they are given hats.

Next, some subset of the players guess their own hat colour. All the
guesses have to be made at the same time. The team wins iff at least one
player guesses correctly and nobody guess incorrectly.

	Before being given the hats, the team is allowed to formulate a
strategy. This is what makes the game interesting. What strategies
maximize the chances of winning?




Event:       Discrete Math/PiMS Seminar
Speaker:     Mohammad Ghebleh
Affiliation: Simon Fraser University
Email:       mghebleh@math.sfu.NOSPAM.ca (remove NOSPAM.)
Date:        Tuesday, 06 November 2001
Time:        3:30 - 4:20
Place:       EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:       Uniuqely list colorable graphs.
Abstract:
A graph is said to be uniquely list colorable if it admits an
assignment of some lists of colors (with specified sizes) to
its vertices such that there exists exactly one list coloring
from those lists. This concept naturally arises in the study
of critical sets in latin squares. Another motivation for the
subject is a theorem of Marshal Hall concerning the number of
SDRs of a given finite family of finite sets.





Event:       Discrete Math/PiMS Seminar
Speaker:     Petr Lisonek
Affiliation: Simon Fraser University
Email:       plisonek@math.sfu.NOSPAM.ca (remove NOSPAM.)
Date:        Tuesday, 13 November 2001
Time:        3:30 - 4:20
Place:       EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:       Geometric representations of graphs
Abstract:
We will discuss several results on embedding graphs in Euclidean spaces.
Applications include constructions of large few-distance sets
in Euclidean spaces and graph-theoretic aspects of the Borsuk conjecture.



Event:       Discrete Math/PiMS Seminar
Speaker:     Luis Goddyn
Affiliation: Simon Fraser University
Email:       goddyn@math.sfu.NOSPAM.ca (remove NOSPAM.)
Date:        Tuesday, 20 November 2001
Time:        3:30 - 4:20
Place:       EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:       Using the Nullstellensatz for edge list colouring.
Abstract:
The Combinatorial Nullstellensatz or "polynomial method", introduced by
N. Alon and M. Tarsi, is a nonconstructive algebraic method which can
be used to prove list colouring results in graph and hypergraph theory.
I will present some of my work regarding its application to special cases
of the very difficult "Edge List Colouring Conjecture":
   Every graph which is k-edge colourable
   is also k-edge list colourable.




Event:       Discrete Math/PiMS Seminar
Speaker:     Reza Naserasr
Affiliation: Simon Fraser University
Email:       rnaseras@math.sfu.NOSPAM.ca (remove NOSPAM.)
Date:        Tuesday, 27 November 2001
Time:        3:30 - 4:20
Place:       EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:       On the covering number of graphs.
Abstract:
We consider fractional weight functions of graphs, with 
different type of restrictions. This gives new parameters of graphs.
We study one parameter related to the chromatic number of graphs, we give bounds
and a homomorphism theorem for some special cases. 




Event:       Discrete Math/PiMS Seminar
Speaker:     Roded Sharan
Affiliation: Technion, Haifa
Email:       ??? (remove NOSPAM.)
Date:        Tuesday, 04 December 2001
Time:        3:30 - 4:20
Place:       EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:       Incomplete Directed Perfect Phylogeny.
Abstract:
Perfect phylogeny is one of the fundamental models
for studying evolution. We investigate the following 
variant of the problem: 
The input is a species-characters matrix.
The characters are binary and directed, i.e., a species
can only gain characters. The difference from standard
perfect phylogeny is that for some species the state of
some characters is unknown. The question is whether one
can complete the missing states in a way admitting a 
perfect phylogeny.
The problem arises in classical phylogenetic studies,
when some states are missing or undetermined, and in recent 
studies that infer phylogenies using inserted repeat elements in DNA.
The best extant algorithms for the problem require $O(n^2m)$ time
for $m$ characters and $n$ species. 
We reformulate the problem as a graph sandwich problem,
and provide near optimal $\tilde{O}(nm)$-time algorithms for it.

Joint work with Itsik Pe'er, Tal Pupko and Ron Shamir.




Event:       Discrete Math/PiMS Seminar
Speaker:     Frederic Havet
Affiliation: CNRS, INRIA Sophia, Antipolis,France
Email:       Frederic.Havet@sophia.inria.NOSPAM.fr(remove NOSPAM.)
Date:        Tuesday, 11 December 2001
Time:        3:30 - 4:20
Place:       EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:       Design of fault tolerant on-board networks with priorities
Abstract:
 We consider on-board networks in satellites interconnecting
 entering signals (inputs) to amplifiers (outputs).
 The connections are made via expensive switches with four links available. 
 The paths connecting inputs to outputs should be link-disjoint.
 Among the input signals, some of them, called priorities, 
 must be connected to those amplifiers which provide the best quality
 of service (that is to some specific outputs).
 In practice, amplifiers are subject to faults that cannot be repaired.
 Therefore we need to add extra outputs to ensure the existence 
 of sufficiently many valid ones.
 Given  $n$ inputs, $p$ priorities and $k$ faults, 
 the problem consists in designing a low cost network
 (i.e. with the minimum number of switches)
 where it is possible to route the $p$ priorities
 to the $p$ best quality amplifiers,
 and to route the other inputs to some valid amplifiers,
 for any sets of $k$ faulty and $p$ best quality amplifiers.
 Let $N(n,p,k)$ be the minimum number of switches of such a network.
 We prove here that $N(n,p,k) \leq \frac{7n}{2} + f(p,k)$
 and give exact values of $N(n,p,k)$ for small $p$ and $k$.




Event:       Discrete Math/PiMS Seminar
Speaker:     Mirka Miller
Affiliation: Dept. of CS and SE, Univ. of Newcastle, Australia
Email:       mirka@cs.newcastle.edu.NOSPAM.au(remove NOSPAM.)
Date:        Tuesday, 18 December 2001
Time:        3:30 - 4:20
Place:       EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:       Eccentric Digraphs
Abstract:
The distance from from a vertex $u$ to a vertex $v$
in a directed graph $G$ is the length of a shortest
directed path from $u$ to $v$.
The {\it eccentric digraph } $ED(G)$ of a directed
graph $G$ has the same vertex set as $G$.
There is an arc from $u$ to $v$ in $ED(G)$ iff
$v$ is a vertex of maximum distance from $u$ in $G$.
In this talk, we examine eccentric digraphs
for various families of digraphs.
We also consider the behaviour of an iterated
sequence of eccentric digraphs, and other
questions concerning eccentric digraphs.






Event:       Discrete Math/PiMS Seminar
Speaker:     Reza Naserasr
Affiliation: School of Computing Science, SFU
Email:       rnaseras@cs.sfu.NOSPAM.ca(remove NOSPAM.)
Date:        Tuesday, 05 February 2002
Time:        3:30 - 4:20
Place:       EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:       Homomorphisms from sparse graphs with large girth.
Abstract:
We discuss a recent result on graph homomorphism.  This is joint work with
O.V. Borodin, S.-J. Kim, A.V. Kostochka, and D.B. West.





Event:       Discrete Math/PiMS Seminar
Speaker:     Qianping Gu
Affiliation: School of Computing Science, SFU
Email:       qgu@cs.sfu.NOSPAM.ca(remove NOSPAM.)
Date:        Tuesday, 12 February 2002
Time:        3:30 - 4:20
Place:       EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:       Permutation routing on WDM optical hypercubes I.
Abstract:
There are two results in the talk.
The first one is any permutation can be realized
by two wavelengths on the directed hypercube
(with two directed edges, one in each direction,
between each pair of adjacent nodes).
This work is related to Syzmanski Conjecture.
If the conjecture is true, then any permutation
can be realized by one wavelength.
The second result is on undirected hypercube
(with one undirected edge between each pair
of adjacent nodes). Consider a set of routing
requests as an undirected routing graph on the
same node set of the hypercube. Any routing request
of node degree d can be realized by 4d wavelengths.
A permutation has node degree 2, and thus, can be
realized by 8 wavelengths on the undirected hypercube.



Event:       Discrete Math/PiMS Seminar
Speaker:     Qianping Gu
Affiliation: School of Computing Science, SFU
Email:       qgu@cs.sfu.NOSPAM.ca(remove NOSPAM.)
Date:        Tuesday, 19 February 2002
Time:        3:30 - 4:20
Place:       EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:       Permutation routing on WDM optical hypercubes II.
Abstract:
There are two results in the talk.
The first one is any permutation can be realized
by two wavelengths on the directed hypercube
(with two directed edges, one in each direction,
between each pair of adjacent nodes).
This work is related to Syzmanski Conjecture.
If the conjecture is true, then any permutation
can be realized by one wavelength.
The second result is on undirected hypercube
(with one undirected edge between each pair
of adjacent nodes). Consider a set of routing
requests as an undirected routing graph on the
same node set of the hypercube. Any routing request
of node degree d can be realized by 4d wavelengths.
A permutation has node degree 2, and thus, can be
realized by 8 wavelengths on the undirected hypercube.



Event:       Discrete Math/PiMS Seminar
Speaker:     Luis Goddyn
Affiliation: Mathematics, SFU
Email:       goddyn@math.sfu.NOSPAM.ca(remove NOSPAM.)
Date:        Tuesday, 5 March 2002
Time:        3:30 - 4:20
Place:       EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:       Graph coloring and Matroids.
Abstract:
There are several equivalent definitions of `chromatic number' for graphs.
These definitions refer to various notions including: vertex colourings,
homomorphisms, the Tutte polynomial, circuit-balanced orientations,
group-valued tensions (for finite groups, the rationals, the circle group),
bond reversal procedures, and edge-cut covering. Most of these definitions
make sense in more general matroid settings, especially for orientable
matroids. For matroids the definitions no longer coincide. That is,
non-regular matroids have several distinct `chromatic numbers'
(and `flow numbers'). We outline a few results, several questions
and possible approaches to this relatively unexplored topic.
This work is in collaboration with PhD candidate Laura Chavez.



Event:       Discrete Math/PiMS Seminar
Speaker:     Tom Friedetzky
Affiliation: PiMS, SFU
Email:       tf@pims.math.NOSPAM.ca(remove NOSPAM.)
Date:        Tuesday, 12 March 2002
Time:        3:30 - 4:20
Place:       EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:       The Natural Work-Stealing Algorithm is Stable
Abstract:
We analyse a very simple dynamic work-stealing algorithm.  In the
work-generation model, there are n generators which are arbitrarily
distributed among a set of n processors.  The distribution of generators
is arbitrary --- generators may even move at the beginning of each time
step.  During each time-step, each generator may generate a unit-time
task which it inserts into the queue of its host processor.  It
generates such a task independently with probability lambda.  After the
new tasks are generated, each processor removes one task from its queue
and services it.  Clearly, the work-generation model allows the load to
grow more and more imbalanced, so, even when lambda<1, the system load
can be unbounded.  

The natural work-stealing algorithm that we analyse is widely used in
practical applications and works as follows.  During each time step,
each  empty processor (with no work to do) sends a request to a randomly
selected other processor.  Any  non-empty processor having received at
least one such request in turn decides (again randomly) in favour of one
of the requests.  The number of tasks which are transferred from the
non-empty processor to the empty one is determined by the so-called
work-stealing function f.  In particular, if a processor that accepts a
request has l tasks stored in its queue, then f(l) tasks are transferred
to the currently empty one.  A popular work-stealing function is
f(l)=floor(l/2), which transfers (roughly) half of the tasks.  
  
We analyse the  long-term behaviour of the system as a function of
lambda and f.  We show that the system is  stable for any constant
generation rate lambda<1 and for a wide class of functions f.  Most
intuitively sensible functions are included in this class (for example,
every function f(l) which is omega(1) as a function of l is included).
We give a quantitative description of the functions f which lead to
stable systems.  Furthermore, we give  upper bounds on the average
system load (as a function of f and n).  Our proof techniques combine
Lyapounov function arguments with domination arguments, which are needed
to cope with dependency.



Event:       Discrete Math/PiMS Seminar
Speaker:     Petr Lisonekky
Affiliation: Mathematics, SFU
Email:       plisonek@.math.sfu.NOSPAM.ca(remove NOSPAM.)
Date:        Tuesday, 19 March 2002
Time:        3:30 - 4:20
Place:       EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:       Caps and Binary Linear Codes
Abstract:
A cap in the finite projective space PG(m,q) is a set S of points 
no three of which are collinear.  Taking the coordinates of points in S
as columns of a parity check matrix defines a q-ary linear code with minimum
distance at least 4.  We will survey some results about caps
in cases m=2 (arcs in classical finite projective planes)
and q=2 (binary codes).  We will discuss the method and results 
of the isomorph-free classification of caps in PG(m,2) for m<=6.
In the second half of the talk we will discuss properties of those
binary linear codes that have optimal minimum distance (for given length 
and dimension) and at the same time they minimize the number 
of minimum-weight words.  This is joint work with Mahdad Khatirinejad
Fard.



Event:       Discrete Math/PiMS Seminar
Speaker:     Petra Berenbrink
Affiliation: Computing Science, SFU
Email:       petra@cs.sfu.NOSPAM.ca(remove NOSPAM.)
Date:        Tuesday, 26 March 2002
Time:        3:30 - 4:20
Place:       EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:       Simple routing strategies for Adversarial networks.
Abstract:
In this talk I present and analyze distributed algorithms for
the delivery of dynamically changing input streams in dynamically
changing networks where both the topology and the input streams can
change in an unpredictable way. In particular, I present two simple
distributed balancing algorithms (one for packet injections and one
for flow injections) and show that for the case of a single receiver
these algorithms will always ensure that the number of packets in
the system is bounded at any time step, even for an injection
process that completely saturates the capacities of the available
edges, and even if the network topology changes in a completely
unpredictable way. I will also show that the maximum number of packets
or flow that can be in the system at any time is best possible by
providing an (essentially) matching lower bound that holds for {\em
any} online algorithm, whether distributed or not.  Interestingly,
our balancing algorithms do not only behave well in a completely
adversarial setting. We show that also in the other extreme of a
static network and a static injection pattern the algorithms will
converge to a point in which they achieve an average routing time
that is close to the best possible average routing time that can be
achieved by any strategy.  This demonstrates that there are
simple algorithms that can be efficient at the same time for very
different communication scenarios.  These algorithms will be of
particular importance for communication in wireless mobile ad hoc
networks (or short MANETs), in which at some time the connections
between mobile nodes and/or the rates of input streams may change
quickly and unpredictably and at some other time may be quasi
static.
Joint Work with Baruch Awerbuch, Andre Brinkmann, Christian Scheideler



Event:       Discrete Math/PiMS Seminar
Speaker:     Pavol Hell
Affiliation: Computing Science, SFU
Email:       pavol@cs.sfu.NOSPAM.ca(remove NOSPAM.)
Date:        Tuesday, 02 April 2002
Time:        3:30 - 4:20
Place:       EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:       The effect of degree-bounding on the complexity of generalized
             list-colourings.
Abstract:
The complexity of several versions of H-colouring and list 
H-colouring problems has been classified. Motivated by problems 
in frequency assignment and in statistical physics, we are reviewing
these classifications to see the extent to which bounding the 
maximum degree of the input graphs affects them. A typical
example well known to all graph theorists is the following fact,
implied by the theorem of Brooks: While three-colouring is
NP-complete in general, it is polynomial time solvable for graphs
with degrees bounded by three, but NP-complete again if the degree
bound is changed to four. Some similar overall trends will be
identified, and many open problems presented. As a byproduct of
the algorithms we obtain several Brooks-type theorems for list
colourings.

This talk includes joint work with:
A. Galluccio, J. Nesetril, T. Feder, and J. Huang.



Event:       Discrete Math/PiMS Seminar
Speaker:     Laco Stacho
Affiliation: Mathematics, SFU
Email:       lstacho@math.sfu.NOSPAM.ca(remove NOSPAM.)
Date:        Tuesday, 09 April 2002
Time:        3:30 - 4:20
Place:       EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:       Edge-disjoint spanners in the Cartesian product of graphs.zed
Abstract:
A spanning subgraph S=(V,E') of a connected simple graph G=(V,E) is an 
f(x)-spanner if for any pair of vertices u and v, d_S(u,v) \leq f(d_G(u,v)) 
where d_S and d_G are the usual distance functions in graphs S and G, 
respectively. The delay of the f(x)-spanner is f(x)-x. 
  
In the talk, we will present motivations for the study of spanners with small 
delay, and known results on this subject. Further, we will investigate the 
existence of edge-disjoint spanners in the Cartesian product of graphs with 
emphasis on the hypercubes.



Event:       Discrete Math/PiMS Seminar
Speaker:     Rados Rodoicic
Affiliation: Mathematics, MIT
Email:       rados@math.mit.NOSPAM.edu (remove NOSPAM.)
Host:        Veso Jungic
Date:        Tuesday, 14 May 2002
Time:        3:30 - 4:20
Place:       EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:       Rainbow Arithmetic Progressions
Abstract:
The van der Waerden theorem in Ramsey theory states that for every
$k$ and $t$ and sufficiently large $N$, every $k$-coloring of $[N]$
contains a monochromatic arithmetic progression of length $t$. Motivated
by this result, I conjectured that every equinumerous $3$-coloring
of $[3n]$ contains a $3$-term rainbow arithmetic progression, i.e., an
arithmetic progression whose terms are colored with distinct colors.
In this talk, we will prove that every $3$-coloring of the set of
natural numbers for which each color class has density more than $1/6$,
contains a $3$-term rainbow arithmetic progression.
We also prove similar results for colorings of $\Z_n$.
Finally, we give a general perspective on other
{\em anti-Ramsey-type} problems that can be considered.
This is a joint work with V. Jungi\'c, J. Licht, M. Mahdian and
J. Ne\v set\v ril.               




Event:       Discrete Math/PiMS Seminar
Speaker:     Sean McGuinness
Affiliation: University of Umea, University of Montana
Email:       sean@abel.math.umu.NOSPAM.se (remove NOSPAM.)
Host:        Luis Goddyn
Date:        Tuesday, 28 May 2002
Time:        3:30 - 4:20
Place:       EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:       Circuits intersecting cocircuits in graphs and matroids.
Abstract:
A problem related to graphs and matroids is finding a circuit which
intersects every cocircuit of maximum size. For 2-connected graphs it
is known that there is a bond (ie. cocircuit) which intersects every circuit of
maximum length.  The 'dual' formulation of this result (ie. finding a circuit
intersecting every maximum size bond) does not hold, however one can show
the following:  for any k-connected graph having have maximum bond size c',
there is a circuit which intersects every bond of size c'-k+2 or greater.
This result can be used to show that for every 2-connected graph, there is
a family of at most c' circuit which cover each edge of the graph at least twice.
This settles a question posed by Oxley.

We prove the dual of the above result namely, for any k-connected graph
having largest circuit of length c >= 2k, there is a bond which intersects
every circuit of length c-k+2 or greater.  We discuss various possible
extensions of these results to matroids.







Event:       Discrete Math/PiMS Seminar
Speaker:     Claude Tardif
Affiliation: Mathematics, University of Regina
Email:       tardif@math.uregina.NOSPAM.ca (remove NOSPAM.)
Host:        Pavol Hell
Date:        Tuesday, 11 June 2002
Time:        3:30 - 4:20
Place:       EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:       The projectivity of the graphs $G_k^d$
Abstract:
The graphs $G_k^d, 1 \leq d \leq k/2$ are the well-known
``target graphs'' for the circular chromatic number.
We prove that these graphs are projective, that is, 

  any homomorphism 
  $\phi: G_k^d \times G_k^d \times \ldots \times G_k^d \mapsto G_k^d$
  satisfying $\phi( x,x, \ldots, x ) = x$ is a projection.
	
Here `$\times$' is the categorical (direct) graph product.
This result has the following consequences:

(1) The independent sets of maximum cardinality in 
    $G_k^d \times G_k^d \times \ldots \times G_k^d$ are precisely those
    obtained by pulling up an independent set of maximum cardinality in
    a factor.

(2) An analogue of the Duffus-Sands-Woodrow theorem holds for the
    circular chromatic number: If G and H are connected graphs such that 
    $\chi_c(G) \geq \chi_c(H) > k/d$ and $G_k^d$ admits homomorphisms
    to both $G$ and $H$, then $\chi_c(G \times H) > k/d$.

More generally, Zhu has conjectured that for any graphs $G$ and $H$
we have $\chi_c(G \times H) = \min \{chi_c(G), \chi_c(H)\}$;
this is a stronger statement even than Hedetniemi's conjecture.

This is joint work with Benoit Larose.







Event:       Discrete Math/PiMS Seminar
Speaker:     Joergen Bang-Jensen
Affiliation: Computer Science, University of Southern Denmark, Odense Campus.
Email:       jbj@math.uvic.NOSPAM.ca (remove NOSPAM.)
Host:        Pavol Hell
Date:        Tuesday, 18 June 2002
Time:        3:30 - 4:20
Place:       K 9509, NOTE UNUSUAL ROOM
Title:       Steiner type problems in tournament-like digraphs
Abstract:
Let D be a digraph with real-valued costs on the vertices and let the cost
of a cycle be the sum of the costs of its vertices. Clearly, if we allow
negative costs then it is NP-hard to find a minimum cost cycle since the
hamiltonian cycle problem can be posed in this way.

In this talk we show how to solve the problem of finding a minimum cost
cycle in polynomial time for some classes of digraphs that are
structurally related to tournaments. This includes well studied classes of
digraphs such as extended semicomplete digraphs and quasi-transitive
digraphs. As will be clear from the talk, the solution for
quasi-transitive digraphs relies heavily on their nice decomposition
properties and their strong relation to extended semicomplete digraphs.

We also consider the so-called directed Steiner problem. Here we are given
a strongly connected digraph D and subset X of its vertices and the goal
is to find a strong subdigraph which covers X and has a few arcs as
possible. 

Finally we discuss the related problem of finding in a strong digraph with
real-valued costs on the vertices, a strong subdigraph of minimum cost.

This is joint work with Gregory Gutin and Anders Yeo of Royal Holloway,
University of London. The work was done while the speaker was visiting
Department of Mathematics, Univerisity of Victoria on his sabatical. 








Event:       Discrete Math/PiMS Seminar
Speaker:     Winfried Hochstaettler
Affiliation: Brandenburg U. of Tech.
Email:       hochst@math.tu-cottbus.NOSPAM.de (remove NOSPAM.)
Host:        Luis Goddyn
Date:        Tuesday, 25 June 2002
Time:        3:30 - 4:20
Place:       K 9500, NOTE UNUSUAL ROOM
Title:       Enumerations of Oriented Matroids
Abstract:
J. Bukowski et. al developed an algorithm to enumerate uniform
oriented matroids using a new cryptomorphic characterization
of orineted matroids called hyperline sequences. We extend
this approach to net necessarily uniform oriented matroids.
We give a full axiomatic description of hyperline sequences
and prove that it is cryptomorphic to oriented matroids.
Furthermore, we discuss how it can be used to generate exactly
one representative of each geometric class of oriented matroids.
(This is joint work with Oliver Klein)
NOTE:  THIS TALK HAS BEEN REPLACED WITH THE FOLLOWING








Event:       Discrete Math/PiMS Seminar
Speaker:     Winfried Hochstaettler
Affiliation: Brandenburg U. of Tech.
Email:       hochst@math.tu-cottbus.NOSPAM.de (remove NOSPAM.)
Host:        Luis Goddyn
Date:        Tuesday, 25 June 2002
Time:        3:30 - 4:20
Place:       K 9500, NOTE UNUSUAL ROOM
Title:       Max-flow min-cut duality for a paint shop problem
Abstract:
Motivated by a problem from car manufacturing, we consider the following:
 Given a word where each letter occurs exactly twice, colour the letters
 in red and blue such that each letter occurs in both colours and the
 number of colour changes between adjacent letters is minimized.
This turns out to be the dual problem of a min-cut problem for binary
one-point extensions of a certain class of regular matroids.  We discuss
consequences of max-flow-min-cut duality and algorithmic approaches.
This research in progress is joint work with Th. Epping and M. Luebbecke.







Event:       Discrete Math/PiMS Seminar
Speaker:     Luis Goddyn
Affiliation: Simon Fraser University
Email:       goddyn@math.sfu.NOSPAM.ca (remove NOSPAM.)
Date:        Tuesday, 2 July 2002
Time:        3:30 - 4:20
Place:       K9505, SFU   Note unusual room.
Title:       Circular flows and tensions on maps of high edge width.
Abstract:
The classical dual relation between flows and colourings in
plane graphs breaks down for maps on higher surfaces.
Specifically, if $\Sigma$ is a surface different from the sphere,
then the circular chromatic number of a map $G$ on $\Sigma$
may be strictly greater than the circular flow number of the
surface dual map $G^{\Sigma *}$. 
We show that these two parameters are nearly equal
provided that $G$ has {\it edge width} at least $f(\Sigma)$
for some (astronomical) function $f$, for any orientable
surface $\Sigma$.

Conversely, we use orientations and a new invariant,
the {\it local tension number}, to derive lower bounds
on the circular chromatic numbers of certain nonorientable maps,
Together, the results imply that there are gaps in the range of
possible circular chromatic numbers for certain maps of high edge width.
For example any triangulation $G$ has circular chromatic number
either at least $4$ or at most $3+\epsilon$ where $\epsilon$
depends only on $\Sigma$ and on the edge width of $G$.
A similar behaviour is exhibited by maps in which every face
boundary has even length.
This is joint work with M.~DeVos, B.~Mohar, D.~Vertigan and X.~Zhu.










Event:       Discrete Math/PiMS Seminar
Speaker:     Peter Higgins
Affiliation: University of Essex
Email:       peter@essex.ac.NOSPAM.uk (remove NOSPAM.)
Host:        Norman Reilly, 3-week visit.
Date:        Tuesday, 9 July 2002
Time:        3:30 - 4:20
Place:       EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:       Sur une Th\'eor\`eme de Sierpi\'nski
Abstract:
In 1936 W. Sierpi\'nski proved that each member of any countable collection
of functions on an infinite set can be written as a product of a fixed
pair of functions.  This remarkable result, less well known that it ought
to be, was immediately reproved by Stephan Banach, in the same journal,
in a two-page paper with the above title.

In this talk I show Banach's elegant proof and will explain how we came
by the result ourselves in the course of some recent research.










Event:       Discrete Math/PiMS Seminar
Speaker:     Khee-Meng Koh
Affiliation: National University of Singapore
Email:       matkohkm@nus.edu.NOSPAM.sg (remove NOSPAM.)
Host:        Luis Goddyn,  2 month visit.
Date:        Tuesday, 16 July 2002
Time:        3:30 - 4:20
Place:       EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:       On the Chromaticity of Graphs
Abstract:
Given a graph G, we shall denote by P(G,\lambda)
the chromatic polynomial of G.
Two graphs G and H are said to be \chi-equivalent,
if P(G,\lambda) = P(H,\lambda).
In this talk, we shall introduce Whitney's Broken-Cycle Theorem
on P(G,\lambda), and discuss its applications in determining
the \chi-equivalence class [G], and whether [G]= {G}.















Event:       Discrete Math/PiMS Seminar
Speaker:     Marnie Mishna
Affiliation: National University of Singapore
Email:       mishna@math.uqam.NOSPAM.ca (remove NOSPAM.)
Host:        Luis Goddyn
Date:        Tuesday, 30 July 2002
Time:        3:30 - 4:20
Place:       EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:       Enumeration via D-finite Symmetric Functions
Abstract:
 Several enumeration problems of a particular type such as graphs (or
multigraphs or hypergraphs) with a given degree pattern or Young
tableaux with a particular content pattern can be phrased as problems
involvihng coefficients of symmetric functions. We will examine
problems of this type and recent results which give algebraic
algorithms for finding the differential equations of certain
generating functions.




















Event:       Discrete Math/PiMS Seminar
Speaker:     Luis Goddyn
Affiliation: Simon Fraser University
Email:       goddyn@math.sfu.NOSPAM.ca (remove NOSPAM.)
Date:        Tuesday, 6 August 2002
Time:        3:30 - 4:20
Place:       EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:       Chromatic numbers of matroids
Abstract:
There are several equivalent definitions of `chromatic number' for graphs.
These definitions refer to various notions including: vertex colourings,
homomorphisms, the Tutte polynomial, circuit-balanced orientations,
group-valued tensions (for various groups), bond reversal procedures,
and cocircuit covering. Most of these definitions make sense in more
general matroid settings, especially for orientable matroids.
However the various definitions no longer coincide. That is, non-regular
matroids have several distinct `chromatic numbers' (and `flow numbers').
We outline a few results, several questions and possible approaches to this
relatively unexplored area.
This is joint work with Larua Chavez.












Event:       Discrete Math/PiMS Seminar
Speaker:     Bill McCuaig
Affiliation: Simon Fraser University
Email:       wmccuaig@attcanada.NOSPAM.ca (remove NOSPAM)
Date:        Tuesday, 6 August 2002 
Time:        3:30 - 4:20
Place:       EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:       Edmonds' arc-disjoint arborescences theorem
Abstract:
We state and prove Edmonds' theorem which characterizes
those rooted directed graphs (G,r) for which one
can find $k$ arc-disjoint spanning arborescences
directed away from r.






Modified: 2002.5.25 by goddyn@sfu.ca (Luis Goddyn)