Abstracts of Discrete Math Seminars at SFU (and sometimes UBC)
This page changes frequently. If you see this message,
then 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.)A 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:
This is actually a reading seminar.
We discuss a recent result on graph homomorphism with authors
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 Lisonek
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 oriented 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: Marni Mishna
Affiliation: UQAM
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.
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Juan Jos\'e Montellano-Ballesteros
Affiliation: Instituto de Matem\'aticas, UNAM. M\'exico
Email: josem@sfu.NOSPAM.ca (remove NOSPAM.)
Date: Tuesday, 10 September 2002
Time: 2:00 - 2:50
Place: EAA 1100, SFU (Just North of B-lot by pedestrian
stop-light)
Title: Polychromatic cliques
Abstract:
Given an edge colouring $\Gamma$ of a graph $G$, a subgraph $M$ of $G$
will be called {\it totally multicoloured} if no two edges of $M$
receive
the same colour. An edge colouring $\Gamma$ of a graph $G$ will be
called
$k$-{\it bounded} if no colour appears more that $k$ times in $G$.
In this talk we show new bounds of the following problem:
Given $n\geq 3$ and $k\geq 2$, determine the minimum integer $ m$ such
that
for every $k$-bounded edge colouring of $K_m$ there is a totally
multicoloured
copy of $K_n$.
This is a joint work with Pavol Hell.
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Ladislav Stacho
Affiliation: SFU
Email: lstacho@sfu.NOSPAM.ca (remove NOSPAM.)
Date: Tuesday, 17 September 2002
Time: 2:00 - 2:50
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: Edge-disjoint spanners in multi-dimensional torus
Abstract:
A spanner of a graph is a spanning subgraph in which the distance
between any pair of vertices approximates the distance in the original
graph. Spanners are interesting graph theoretical structure with
application to many problems in interconnection networks. For such
applications, one has to find as many edge-disjoint spanners of a given
network as possible.
Let $c$ be a constant. A delay $c$ spanner $S$ of a graph $G$ is a
spanning subgraph of $G$ such that the distance $d_S(x,y) \leq
d_G(x,y)+c$ for any pair of vertices $x,y$ of $G$. Given a constant $c$,
we are interested in maximum number of edge-disjoint delay $c$ spanners
that can be found in $G$. We let $EDS(G,c)$ to denote this number.
The function $EDS$ has been studied for complete bipartite graphs [2],
complete graphs [3], and hypercubes [1]. In this talk, I will discuss
results on $EDS(G,c)$ when G is a multi-dimensional torus.
This is a joint work with Art Liestman and Tom Shermer.
[1] Fertin, G, A. L. Liestman, T. C. Shermer, and L. Stacho,
Edge-disjoint spanners in hypercubes, manuscript.
[2] Laforest, C., A. L. Liestman, T. C. Shermer, and D. Sotteau,
Edge-disjoint spanners of complete bipartite graphs, Discrete Math. 234,
2001, pp. 65--76.
[3] Laforest, C., A. L. Liestman, D. Peleg, T. C. Shermer, and D.
Sotteau,
Edge Disjoint Spanners of Complete Graphs and Complete Digraphs,
Discrete Math. to appear.
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Jan Manuch
Affiliation: SFU
Email: manuch@pims.math.NOSPAM.ca (remove NOSPAM.)
Date: Tuesday, 24 September 2002
Time: 2:00 - 2:50
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: On the Descriptional and Computational Complexities of Infinite Words
Abstract:
The talk concentrates on the descriptional and computational complexities
of infinite words. We will give definitions, summarize the known results,
and formulate interesting problems in this area. We will also show the
following results:
We show that the problem whether all infinite words generated by
iterating dgsm's have logarithmic space complexity is equivalent to
the open problem asking whether the unary classes of languages in
P and in DLOG are equivalent.
Similarly, the problem to find a concrete infinite word
which cannot be generated in logarithmic space is equivalent to
the problem to find a concrete language which does not belong to
DSPACE(n).
Finally, we separate classes of infinite words generated
by double and triple D0L TAG systems.
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Tom Brown
Affiliation: Mathematics, SFU
Email: tbrown@sfu.NOSPAM.ca (remove NOSPAM.)
Date: Tuesday, 1 October 2002
Time: 2:00 - 2:50
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: On the Canonical Version of a Simple Theorem in Ramsey Theory
Abstract:
One of the central results of Ramsey theory is van der
Waerden's theorem on arithmetic progressions:
Let N denote the set of positive integers. Let f be any
function from N to a finite set. Then there are arbitrarily large
(finite) arithmetic progressions P = {a, a+d, a+2d, ..., a+kd} such
that f is constant on P.
There is a "canonical version" of this theorem, which says:
If f is *any* coloring of N (which means that f is a function
from N to an infinite set), then there are arbitrarily large (finite)
arithmetic progressions P such that either f is constant on P or f is
1-1 on P.
We discuss these results and another simple theorem, which
(1) has the same flavor as van der Waerden's theorem,
(2) is much easier to prove than van der Waerden's theorem,
(3) does not directly imply, and is not directly implied by,
van der Waerden's theorem,
(4) does not have a "density version" (as van der Waerden's
theorem does)
(5) does not (yet) have a canonical version.
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Petr Lisonek
Affiliation: Mathematics, SFU
Email: plisonek@cecm.sfu.NOSPAM.ca (remove NOSPAM.)
Date: Tuesday, 8 October 2002
Time: 2:00 - 2:50
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: A Family of Complete Caps in PG(n,2)
Abstract:
We give a combinatorial construction of a one-parameter and
a two-parameter family of complete caps in finite projective
spaces over GF(2). As an application of our construction
we find, for each $\alpha \in [1.89,2]$, a sequence of complete caps
in PG(n,2) whose sizes grow as $\alpha^n$.
We also discuss the relevance of our caps to the problem of finding
the least dependent caps of a given cardinality in a given dimension.
This is joint work with Mahdad Khatirinejad Fard.
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Riste Skrekovski
Affiliation: PIMS/SFU
Email: skreko@pims.NOSPAM.math.ca (remove NOSPAM.)
Date: Tuesday, 15 October 2002
Time: 2:00 - 2:50
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: Cyclic, Diagonal, and Facial Colorings
Abstract:
A cyclic coloring of a graph (on a surface) is a coloring
of its vertices such that every two vertices incident with
the same face receive distinct colors. The diagonal coloring
is a generalization of the cyclic coloring. In the talk, we
introduce the facial coloring, which is also generlization of
the cyclic coloring. We present some new results and problems
about these kinds of colorings.
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Veselin Jungic
Affiliation: Mathematics, SFU
Email: vjungic@sfu.NOSPAM.ca (remove NOSPAM.)
Date: Tuesday, 22 October 2002
Time: 2:00 - 2:50
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: Radoicic's Conjecture and Tight Graphs
Abstract:
There is a possibility of a connection between Radoicic's
conjecture that each 3-regular coloring of $[1,3n]$ yields a rainbow
solution of the equation $x+y=2z$ and tight graphs, $k$-regular hypergraphs
with the property that any $n$-coloring, $n\geq k$, of its vertices yields a
rainbow hyper edge.
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Colloquium
Speaker: Bruce Reed, Canada Research Chair in Graph Theory
Affiliation: School of Computer Science, McGill University
Email: breed@NOSPAM.jeff.cs.mcgill.ca (remove NOSPAM.)
Date: Tuesday, 29 October 2002
Time: 2:00 - 2:50
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: Tree Width and Excluded Minors
Abstract:
We discuss structure theorems obtained from
excluding graph minors. We survey this area
and then present some recent results joint
with E. Birmele and A. Bondy on excluding
small grid minors.
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Richard Anstee
Affiliation: Department of Mathematics, University of British Columbia
Email: anstee@NOSPAM.math.ubc.ca (remove NOSPAM.)
Date: Tuesday, 5 November 2002
Time: 2:00 - 2:50
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: Forbidden Configurations
Abstract:
We define a simple matrix to be a (0,1)-matrix with no
repeated columns. Such matrices can be thought of a set system.
Consider a (0,1)-matrix F (`the forbidden configuration') and an mxn
simple matrix A that has no repeated columns, where A also has no
submatrix which is a row and column permutation of F. We denote the best
possible bound on n in terms of m and F as forb(m,F). How do we determine
forb(m,F), either asymptotically or exactly? The main focus of this
talk is recent joint work with Attila Sali that conjectures a way to
derive the asymptotic bound forb(m,F) by examining a limited number
of constructions. We derive the results for all cases of 3xl forbidden
configurations F and for example show that
c_1(m^2) < forb(m,F) < c_2(m^2) for the following F:
110000
001100
000011
The proof techniques use the standard decompositions for directed graphs.
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Qianping Gu
Affiliation: Computing Science, SFU
Email: qgu@cs.NOSPAM.sfu.ca (remove NOSPAM.)
Date: Tuesday, 12 November 2002
Time: 2:00 - 2:50
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: A 1.8-Approximation Algorithm for Embedding Hypergraphs in a Cycle
Abstract:
The problem of Minimum Congestion Hypergraph Embedding
in a Cycle (MCHEC) is to embed the hyperedges of a
hypergraph as paths in a cycle on the same number of
nodes such that the maximum congestion is minimized,
where the congestion of a link in the cycle is the number
of paths that use the link. The problem is NP-hard. We give
a 1.8-approximation algorithm for the problem. This improves
the previous 2-approximation results. The algorithm has the
optimal $O(mn)$ time for the hypergraph with $m$ hyperedges
and $n$ nodes. The MCHEC problem has applications in parallel
computation, network communication, electronic design automation,
and so on.
This is a joint work with Yong Wang.
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Daniel Kral
Affiliation: Charles University
Email: kral@kam.mff.NOSPAM.cuni.cz (remove NOSPAM.)
Date: Tuesday, 19 November 2002
Time: 2:00 - 2:50
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: Channel Assignment Problem
Abstract:
A channel assignment problem is determined by a triple (V,E,w)
where V is a vertex set, E an edge set and w is a function
whcih assigns edges positive integer weights. An assignment c of
integers between 1 and K to the vertices is proper if
w(uv)<=|c(u)-c(v)| for each edge uv; the smallest K for which
there is a proper assignment is the span of the problem.
We show Brooks' theorem both for the channel assignment problem and
its list version. The connection to a conjecture of Griggs and Yeh
on L(2,1)-labelings of graphs is explored. We also present
an algorithm for computing the span of a channel assignment problem
in time O((l+2)^n) where l is the maximum weight of an edge and
some corollaries of it which are interested from the theoretical point
of view will be derived.
This is joint work with Riste Skrekovski.
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Vadim V. Lozin
Affiliation: RUTCOR, Rutgers University
Email: lozin@rutcor.NOSPAM.rutgers.edu (remove NOSPAM.)
Date: Thursday (!) 21 November 2002
Time: 2:00 - 2:50
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: Boundary Classes of Graphs for NP-hard Problems
Abstract:
Typically, a problem, which is NP-hard in general graphs,
become tractable (solvable in polynomial time) when restricted to graphs
in some particular classes. A helpful tool for classification of graph
classes according to the time complexity of a given NP-hard problem is
the notion of a boundary class. In this talk we first introduce this
notion and then apply it to several NP-hard graph problems.
Specifically, we obtain one boundary class for the independent set problem,
two boundary classes for the independent dominating set problem,
and three boundary classes for the dominating set problem.
This is a joint work with V.E. Alekseev and D.V. Korobitsyn (Nizhny
Novgorod University, Russia).
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Ron Ferguson
Affiliation: PiMS/SFU
Email: rferguson@pims.NOSPAM.math.ca (remove NOSPAM.)
Date: Tuesday 26 November 2002
Time: 2:00 - 2:50
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: Polyphase Sequences with Low Autocorrelation
Abstract:
Finding optimal examples of sequences with low autocorrelation is
recognized as a hard combinatorial problem. Barker sequences, whose
autocorrelation coefficients have absolute value less than or equal to 1,
are known only for lengths 2,3,4,5,7,11, and 13 where coefficients are
restricted to values +/- 1. Simulated annealing type algorithms have been
used to find Barker sequences up to length 45 for polyphase sequences
where coefficients ar restricted to modulus 1. We describe an algorithm
using both stochastic methods and methods of calculus which was used to
extend this known list to length 63 and fairly exhaustively investigate
low autocorrelation for lengths up to 45.
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Cindy Loten
Affiliation: Mathematics, SFU
Email: coloten@math.NOSPAM.sfu.ca (remove NOSPAM.)
Date: Tuesday, 3 December 2002
Time: 2:00 - 2:50
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: Retractions and a Generalization of Chordal Graphs
Abstract:
Given a graph H and a supergraph G of H, we are interested in
guaranteeing the existence of a retraction from G to H. One particular
necessary condition for the existence of a retraction is the success of
the Arc Consistency Algorithm. If H is chordal, then the success of the Arc
Consistency Algorithm is also sufficient for the existence of a retraction
(Feder and Hell). On the other hand, the success of the Arc Consistency
Algorithm implies nothing when H is a cycle. We will described a new class
of graphs, generalizing chordal graphs, that have induced cycles which are
embedded in a particular way so that the success of the Arc Consistency
Algorithm will guarantee the existence of a retraction whenever H is a member -------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Reza Naserasr
Affiliation: Mathematics, SFU
Email: rnaseras@math.sfu.NOSPAM.ca (remove NOSPAM.)
Date: Tuesday, 7 January 2003
Time: 3:30 - 4:20
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: Homomorphisms of Planar Graphs
Abstract:
P. Seymour has conjectured that every k-regular planar graph with
no odd cut smaller than k has edge chromatic number k (type I). It is
well known that k=3 of this conjecture is equivalent to 4CT.
We introduce another generalization of 4CT as a conjecture and we
show it is equivalent to the conjecture of Seymour. This combined
with a recent result of Guenin who proved the Seymour's conjecture
for k=4 & 5 will result following Theorem:
Every triangle free planar graph admits a homomorphism to a graph called
Greenwood-Gleason in some text or Clebsch graph in some other
texts this is Cayley graph on 16 vertices and no triangle.
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Pavol Hell
Affiliation: Mathematics/Comp. Sci., SFU
Email: pavol@cs.sfu.NOSPAM.ca (remove NOSPAM.)
Date: Tuesday, 14 January 2003
Time: 3:30 - 4:20
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: Interval Bigraphs and Circular Arc Graphs
Abstract:
Interval bigraphs are one of a number of variants
of interval graphs, which have recently received
a lot of attention. I will describe a surprising
new connection these graphs have with circular arc
graphs, another natural generalization of interval
graphs. As a consequence of this connection, one
obtains counterexamples to a conjecture of Miller,
postulating a forbidden structure characterization
of interval bigraphs. These techniques may prove
useful to find another possible forbidden structure
characterization, and a more efficient algorithm for
the recognition of interval bigraphs.
This is joint work with Huang Jing of University
of Victoria.
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Romeo Rizzi
Affiliation: University of Trento (Italy)
Date: Tuesday, 21 January 2003
Time: 3:30 - 4:20
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: Permutation Routing on POPS Networks
Abstract:
In this short informal talk we will show that
a Partitioned Optical Passive Stars (POPS) network
with $g$ groups and $d$ processors per group can route
any permutation among the $n=dg$ processors in one slot when $d=1$
and $2\lceil d/g\rceil$ slots when $d>1$.
This is joint work with Alessandro Mei.
--------------------------------------------------------------------------
Event: CECM Colloquium / Discrete Math Seminar
Speaker: Nantel Bergeron, Canada Research Chair
Affiliation: Mathematics and Statistics, York University
Email: bergeron@mathstat.NOSPAM.yorku.ca (remove NOSPAM.)
Date: Tuesday, 28 January 2003
Time: 3:30 - 4:20
Place: K 9509 (!)
Title: Quasi-symmetric Polynomials and Temperley-Lieb Invariants and Covariants
Abstract:
Quasi-symmetric polynomials were introduced in enumerative
combinatorics by Gessel and Stanley for the enumeration of
P-partitions. Recent developments show that these polynomials can be
view as Temperley-Lieb polynomials invariants. We will recall the
basic facts on quasi-symmetric polynomials and survey some of the
striking recent developments concerning them. We will also look at the
Temperley-Lieb analogue of the diagonally symmetric polynomials and
the diagonally symmetric harmonics.
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Tom Friedetzky
Affiliation: Computing Science, SFU
Email: tf@pims.math.NOSPAM.ca (remove NOSPAM.)
Date: Tuesday, 11 February 2003
Time: 3:30 - 4:20
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: A Proportionate Fair Scheduling Rule with Good Worst-case Performance
Abstract:
This is joint work of
Micah Adler; UMass, Amherst, US
Petra Berenbrink & Tom Friedetzky; SFU
Leslie Ann Goldberg & Paul Goldberg & Mike Paterson; Warwick, UK
In this paper we consider the following scenario. A set of $n$ jobs with
different threads is being run concurrently. Each job has an associated
weight, which gives the proportion of processor time that it should be
allocated. In a single time quantum, $p$ threads of (not necessarily
distinct) jobs receive one unit of service, and we require a rule that
selects those $p$ jobs, at each quantum. Proportionate fairness means that
over time, each job will have received an amount of service that is
proportional to its weight. That aim cannot be achieved exactly due to the
discretisation of service provision, but we can still hope to bound the
extent to which service allocation deviates from its target. It is important
that any scheduling rule be simple since the rule will be used frequently.
We consider a variant of the Surplus Fair Scheduling (SFS) algorithm of
Chandra, Adler, Goyal, and Shenoy. Our variant, which is appropriate for
scenarios where jobs consist of multiple threads, retains the properties
that make SFS empirically attractive but allows the first proof of
proportional fairness. We show that when the variant is run, no job lags
more than $p H(n)-p-1$ steps below its target number of services, where
$H(n)$ is the Harmonic function. Also, no job is over-supplied by more than
$O(1)$ extra services. This analysis is tight and it also extends to an
adversarial setting, which models some situations in which the relative
weights of jobs change over time.
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Jan Manuch
Affiliation: SFU
Email: jmanuch@sfu.NOSPAM.ca (remove NOSPAM.)
Date: Tuesday, 18 February 2003
Time: 3:30 - 4:20
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: Equations on Words and Defect Theorems
Abstract:
I give a short introduction to Combinatorics on words, after
which I will focus on the topic of word equations and defect theorems.
Informally, defect theorems state that an equation causes a decrease
of dimension of the space of unknowns. While the set of unknows is a set
of words, it is not obvious how to define the dimension of such a set.
It turns out that it can be define in several meaningful ways.
In the end of the talk, I will show some of my results concerning
a special case of defect theorems -- defect theorems for bi-infinite words.
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Wendy Myrvold
Affiliation: University of Victoria
Email: wendym@cs.uvic.NOSPAM.ca (remove NOSPAM.)
Date: Tuesday, 25 February 2003
Time: 10:30 - 11:20 (!)
Place: K 9509 (!)
Title: Hunting for Torus Obstructions
Abstract:
A graph is embeddable on a surface if it can be drawn
on the surface with no crossing edges. This talk will
begin by introducing the basic theory and algorithmic
issues for embedding graphs on surfaces.
A torus is a surface shaped like a doughnut.
A topological obstruction for the torus is a graph
G with minimum degree three that is not embeddable on
the torus but for all edges e, G-e embeds on the torus.
A minor order obstruction has the additional property
that for all edges e, G contract e embeds on the torus.
The aim of our research is to find all the obstructions to the torus
(both minor order and topological). To date, we have found
239,322 topological obstructions and 16,629 minor order obstructions.
Previously, only a few thousand had been determined. This
talk discusses the techniques used to find these obstructions.
Keywords: topological graph theory, embedding graphs on the torus,
algorithms for graph embedding
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Jaroslav Nesetril
Affiliation: Charles University, Prague
Email: nesetril@kam-enterprise.ms.mff.cuni.NOSPAM.cz (remove NOSPAM.)
Date: Tuesday, 25 February 2003
Time: 3:30 - 4:20
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: Ramsey Classes and Homogeneous Graphs
Abstract:
I will describe and relate the two notions in the title.
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Veselin Jungic
Affiliation: Mathematics, SFU
Email: vjungic@sfu.NOSPAM.ca (remove NOSPAM.)
Date: Tuesday, 04 March 2003
Time: 3:30 - 4:20
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: Colorings of Plane Graphs with No Rainbow Faces
Abstract:
A vertex coloring of a plane graph is valid if no face is rainbow.
R. Ramamurthi (UC - San Diego) and D. West (UI - Urbana) conjectured
that if $G$ is an $n$-vertex triangle free plane graph, then
$$\chi _f(G)\geq \left\lceil n/2 \right\rceil +1,$$
where $\chi _f(G)$ is the maximum number of colors used in a valid coloring
of $G$. We answer the conjecture in affirmative.
Moreover, we prove that for a plane graph with girth $g\geq 5$ there is a
valid coloring with at least
$\left\lceil \frac{g-3}{g-2}n-\frac{g-7}{2(g-2)}\right\rceil$
colors, if $g$ is odd, and with at least
$\left\lceil \frac{g-3}{g-2}n- \frac{g-6}{2(g-2)}\right\rceil$
colors, if $g$ is even. The bounds are tight for all pairs $n$ and $g$,
$g\geq 4$ and $n\geq 5g/2-3$.
Joint work with
Daniel Kral (Charles University - Prague) &
Riste Skrekovski (PIMS & University of Ljubljana)
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Jessie Zhu
Affiliation: SFU
Email: czhu@cs.NOSPAM.sfu.ca (remove NOSPAM.)
Date: Tuesday, 11 March 2003
Time: 3:30 - 4:20
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: Phylogenetics Incorporating Stratophenetics
Abstract:
The question of how to adequately use fossil data in phylogenetic analysis
has received considerable attention. In my talk, I propose two new
techniques for incorporating fossil taxa into character based phylogenetic
tree construction.
Our techniques are based on finding tree minor embeddings of labeled trees.
Three generalizations of the "tree minor" are defined, "rooted tree minor",
"relax-minor", and "pseudo-minor". Two new metrics, "bag cost" and "arc
cost", are also introduced as the target scoring functions of the problem.
We show that the problem of finding minimum bag cost under relax-minor is
NP-complete, however the problems of finding minimum bag cost and minimum
arc cost under pseudo-minor can both be solved in polynomial time.
Co-authors: Arvind Gupta, and Ladislav Stacho
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Riste Skrekovski
Affiliation: PIMS/SFU
Email: skreko@pims.NOSPAM.math.ca (remove NOSPAM.)
Date: Tuesday, 18 March 2003
Time: 3:30 - 4:20
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: Coloring 1001 Maps on Surfaces
Abstract:
I will speak about two results on coloring maps on surfaces.
Both results are joint work with M. Stiebitz (TU - Ilmenau, Germany).
The second result is joint work also with Z. Furedi, A. Kostochka,
and D. West (UI - Urbana, USA).
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Stephanie van Willigenburg
Affiliation: Mathematics, U. British Columbia
Email: steph@math.NOSPAM.ubc.ca (remove NOSPAM.)
Date: Tuesday, 25 March 2003
Time: 3:30 - 4:20
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: Acyclic Orientations and Excedence Permutations
Abstract:
The cardinality of a set of certain directed bipartite graphs is
equal to that of a set of permutations that satisfy certain criteria. In this
talk we decribe both the set of graphs and the set of permutations, what
their cardinality has to do with the chromatic polynomial, and whether we can
find a natural bijection between the sets.
This is joint work with Richard Ehrenborg.
--------------------------------------------------------------------------
Event: Computational Logic / Discrete Math Seminar
Speaker: Yuri Gurevich
Affiliation: Microsoft Research
Date: Tuesday, 15 April 2003
Time: 10:30 - 11:20
Place: ASB 9896 - notice the room!
Title: What is Polynomial Time Anyway?
About the speaker:
Yuri Gurevich is a senior scientist heading the
Foundations of Software Engineering group at Microsoft Research in
Redmond, WA (research.microsoft.com/~gurevich).
He is the 2003 PIMS Distinguished Chair.
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Joel Friedman
Affiliation: Mathematics, U. British Columbia
Email: jf@math.ubc.NOSPAM.ca (remove NOSPAM.)
Date: Tuesday, 15 April 2003
Time: 3:30 - 4:20
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: A Proof of Alon's Second Eigenvalue Conjecture
Abstract:
In this talk we (1) give a brief explanation of the importance of the
second eigenvalue (of the adjacency matrix) of a regular graph, (2)
explain Alon's conjecture, (3) introduce some ideas behind our proof of
this conjecture, and (4) indicate some possible generalizations of
Alon's conjecture and/or some connections to physics (involving
different random matrix models).
Alon's conjecture states that for any integer, d > 2, and any real
epsilon > 0, for n large we have that "most" "random"
d-regular graphs on n vertices have second eigenvalue at most 2
sqrt(d-1) + epsilon . Here the words "most" and "random" have to be
made precise; we do so for a number of models of "random" regular
graphs, and our estimates of what "most" means depends on the model.
The starting point of our work is the Broder-Shamir result, which is a
beautiful analogue of Wigner's trace method for the random regular graph
model. Far less is understood for random regular graphs than for the
random matrix models in physics studied first by Wigner.
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Michael Molloy
Affiliation: Microsoft Research and University of Toronto
Email: molloy@cs.NOSPAM.toronto.edu (remove NOSPAM.)
Date: Tuesday, 29 April 2003
Time: 3:30 - 4:20
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: Random Constraint Satisfaction Problems,
aka Homomorphisms of Random Hypergraphs
Abstract:
A constraint satisfaction problem is a generalization of a satisfiability
problem. We are given a set of variables, and a domain of values that
the variables can take. Some subsets of the variables have ``constraints''
which restrict the value-assignments that can be made to those variables.
A problem is satisfiable if there is an assignment of values to the
variables which does not violate any of the constraints.
For example, one special case is k-SAT. Here the domain only has two
values, {True and False}, and the constraints come in the form of
clauses, for example (x1 or not(x4) or x7) which says that
(x1, x4, x7) cannot be assigned the k-tuple (F,T,F). Another
special case is k-colourability of a graph. The domain is the set of
k colours, the variables are the vertices of the graph, and each
edge forms a constraint which says that the two vertices it is joining
cannot be assigned a pair of identical values.
Constraint satisfaction problems are known to be equivalent
to hypergraph homomorphism problems. We wish to find
a homomorphism from a directed hypergraph G to a directed hypergraph H.
We model this as a CSP by placing a constraint on each hyperedge
which specifies that the mapping of the vertices of that hyperedge
must respect H. More generally, there may be a variety of target
graphs, and for each hyperedge we specify which target graph
its mapping must respect. This means that we may have different constraints
on different edges.
In this talk, we discuss models of random constraint satisfaction problems.
The main issue is the following: if we form a random problem by adding
random constraints one-at-a-time, how does the probability of the
problem being satisfiable change? It is clear that this probability
is monotonically decreasing as the number of constraints increases,
but how suddenly
does it decrease? How many constraints must be added before the
decrease is significant? (In formal terms, these questions can
be rephrased as "does the problem have a sharp threshold of
satisfiability?" and "how many constraints must be added before it is
no longer almost surely satisfiable?") These questions generalize
the well-studied notions of the threshold of satisfiability for
a random instance of k-SAT and the threshold of k-colourability
for a random graph.
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Jan Manuch
Affiliation: Simon Fraser University
Email: jmanuch@NOSPAM.sfu.ca (remove NOSPAM.)
Date: Tuesday, 30 September 2003
Time: 3:30 - 4:20
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: On f-wise Arc Forwarding Index and Wavelength Allocations in Faulty
All-optical Networks
Abstract:
Motivated by the wavelength division multiplexing in all-optical networks,
we consider the problem of finding an optimal (with respect to the least
possible number of wavelengths) set of f+1 internally node disjoint dipaths
connecting all pairs of distinct nodes in various networks. In particular, we
consider hypercubes, complete and complete bipartite graphs. This system of
dipaths constitutes a routing protocol that remains functional in the presence
of up to f faults (of nodes and/or links).
We compute precise values of f-wise arc forwarding indexes and give (describe
dipaths and color them) nearly optimal all-to-all f-fault tolerant protocols
for the hypercube network. Further, we show that the problem of finding the precise
values of f-wise arc forwarding indexes of complete and complete bipartite networks
is connected to combinatorial problems in design theory (Latin squares, graceful
labelings, etc).
This is a joint work with Arvind Gupta and Ladislav Stacho.
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Luis Goddyn
Affiliation: Simon Fraser University
Email: goddyn@NOSPAM.sfu.ca (remove NOSPAM.)
Date: Tuesday, 07 October 2003
Time: 3:30 - 4:20
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: Packing Group-non-vanishing A-paths
Abstract:
Given a graph G and a subset A of its vertices, how many pairwise
disjoint A-paths does G have? (An A-path is a nontrivial path whose
two endpoints lie in A.)
If A=V(G), then this is just maximum matching. We derive an exact min-max
formula for the following generalization of this problem:
Suppose G comes additionally with an orientation D whose arcs are weighted
by elements of a group. A path P in G is *non-vanishing* if the product
of the group elements along P is not the group identity. (Backward D-arcs
along P contribute the inverse group element). How many pairwise disjoint
non-vanishing A-paths does G have?
One corollary of the min-max formula is that either one can pack at least
k non-vanishing A-paths, or there exists a set of at most 2k-2 vertices
which meets all non-vanishing A-paths in G.
This result unifies many special cases, problems such as Mader's S-paths,
Menger's, Matchings, and has consequences for surface-embedded graphs.
This is joint work with M. Chudnovski, J. Geelen, A. Gerrards, and
P. Seymour, performed during a PiMS workshop this summer.
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Ladislav Stacho
Affiliation: Simon Fraser University
Email: lstacho@NOSPAM.sfu.ca (remove NOSPAM.)
Date: Tuesday, 14 October 2003
Time: 3:30 - 4:20
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: Closure for the Property of Having a Hamiltonian Prism
Abstract:
We prove that a graph $G$ of order $n$ has a hamiltonian prism if and only if
the graph $\cl_{4n/3-4/3}(G)$ has a hamiltonian prism where $\cl_{4n/3-4/3}(G)$
is the graph obtained from $G$ by sequential adding edges between non-adjacent
vertices whose degree sum is at least $4n/3-4/3$. We show that this cannot be
improved to more than $4n/3-5$. The main method used is discharging.
This is joint work with Daniel Kral.
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Petr Lisonek
Affiliation: Simon Fraser University
Email: plisonek@math.sfu.NOSPAM.ca (remove NOSPAM.)
Date: Tuesday, 21 October 2003
Time: 3:30 - 4:20
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: A New Application of the Linear Programming Method in Coding Theory
Abstract:
The linear programming method in coding theory is typically used to obtain upper bounds
on the size of any code of the given length and given minimum distance. After a brief
review of this method we present its novel application to obtaining structural information
about a linear code, such as bounding the dual distance or bounding the number of words
of weight 2 in the dual code. Applications to classifying certain linear codes, such as
optimal codes for error detection and codes used in statistical experiment design, are presented.
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker:
Affiliation:
Email:
Date: Tuesday, 28 October 2003
Time: 3:30 - 4:20
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title:
Abstract:
SEMINAR CANCELLED
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Russell Martin
Affiliation: U. of Warwick
Email: martin@dcs.warwick.ac.NOSPAM.uk(remove NOSPAM.)
Date: Tuesday, 04 November 2003
Time: 3:30 - 4:20
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: Rapidly Mixing Markov Chains for Sampling Contingency Tables with a
Constant Number of Rows
Abstract:
We consider the problem of sampling almost uniformly from the set of
contingency tables with given row and column sums, when the number of
rows is a constant. Cryan and Dyer have recently given a fully
polynomial randomized approximation scheme (\emph{fpras}) for the
related counting problem, which employs Markov chain methods
indirectly. They leave open the question as to whether a natural
Markov chain on such tables mixes rapidly. Here we show that the
``$2\times 2$ heat-bath'' Markov chain is rapidly mixing. We prove
this by considering first a heat-bath chain operating on a larger
window. Using techniques developed by Morris and Sinclair for the
multidimensional knapsack problem, we show that this chain mixes
rapidly. We then apply the comparison method of Diaconis and
Saloff-Coste to show that the $2\times 2$ chain is
also rapidly mixing.
(Joint work with Mary Cryan, Martin Dyer, Leslie Goldberg, and Mark
Jerrum.)
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Zdenek Ryjacek
Affiliation: Mathematics, U of West Bohemia
Email: ryjacek@kma.zcu.NOSPAM.cz(remove NOSPAM.)
Date: Thursday, 13 November 2003
Time: 3:30 - 4:20
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: Closure Concepts, Stable Properties and Forbidden Subgraphs for Hamiltonicity
Abstract:
Let cl(G) denote the closure of a claw-free graph G. We fully characterize all connected
graphs A such that the class of all CA-free graphs (where C denotes the claw) is stable
under the closure operation (i.e., G being CA-free implies cl(G) is CA-free). Using this
characterization, we extend some known forbidden subgraph results on hamiltonicity by
characterizing classes of all exceptional graphs. We then show that, although the classes
of CA-free graphs in which 2-connectedness implies hamiltonicity (by the Bedrossian's
characterization) are independent in general, this is not the case for their closures.
By introducing a strenhthening of the closure concept, we fully describe the structure
of the (strong) closures of graphs from these classes. Several open questions and problems
will be discussed.
--------------------------------------------------------------------------
Event: The Alan Mekler Lecture
Speaker: Helaman and Claire Ferguson
Date: Tuesday, 18 November 2003
Time: 3:30 - 4:20
Place: AQ 3149, followed by a reception in K 9509
Title: Mathematics in Stone and Bronze
Abstract:
Helaman Ferguson's mathematical sculptures in stone and bronze celebrate ancient
and modern mathematical discoveries, melding the universal languages of sculpture
and mathematics. Using slides and video, Helaman and Claire trace Helaman's
creations from initial concept, mathematical design, computer graphics, diamond
cutting and final form. Their lectures have fascinated audiences worldwide, bringing
together multiple disciplines and stimulating dialogue among them.
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Alireza Hadj Khodabakhshi
Affiliation: Computing, SFU
Email: ahadjkho@cs.sfu.NOSPAM.ca (remove NOSPAM.)
Date: Tuesday, 25 November 2003
Time: 3:30 - 4:20
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: A fast algorithm for finding a Global Alignment between two Genomes
Abstract:
Finding the Global Alignment for two DNA or Protein sequences is one of the fundamental
problems in the field of Computational Molecular Biology. The most well known algorithm
in this regard is the Needleman-Wunsch global alignment algorithm, which finds the
optimal global alignment between two sequences. The algorithm is basically using the
Dynamic Programming method and requires O(n) space and O(n.m) time , in which n and m
are the length of the sequences. The main flaw of this algorithm is its time complexity
that makes it inefficient for aligning the whole genomes of length a few Mega Bases.
A number of algorithms have been introduced to deal with this problem. They basically
use some heuristics to find Approximate Alignments for long sequences. In my talk,
we will talk about a fast algorithm for finding such kind of alignments. In the first
step of this algorithm we try to find the Maximal Exact Matches in the given sequences
using a nice and efficient data structure called suffix tree. Then we find a maximal
set of noncrossing matches using an efficient algorithm for finding Planar matching in
a bipartide graph. These matches are used as anchors to build the desired global
alignment. We fill the gaps between each two matches by recursively invoking the
algorithm with modified parameters or using the Needleman-Wunsch algorithm if the
length of the gap is short enough. This algorithm can align two genomes of length
4-6 mega bases in 3-5 minutes on an ordinary PC with 256 Mb of RAM.
This is joint work with Arvind Gupta, and Ladislav Stacho
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Jim Davis
Affiliation: Math & CS, U of Richmond
Email: jdavis@richmond.NOSPAM.edu (remove NOSPAM.)
Date: Tuesday, 20 January 2004
Time: 3:30 - 4:20
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: Polynomial arithmetic behind the IEEE 802.12 standard
for 100Mbit/s data transmission
Abstract:
In 1995 the Institute of Electrical and Electronic
Engineers (IEEE) approved the 802.12 international
standard for data transmission at 100Mbit/s over
copper telephone cabling. The coding scheme for this
standard was designed to interact favourably with the
IEEE 802 polynomial of degree 32. This ensured that a
large class of burst errors, corrupting information
transmitted simultaneously over four parallel cables,
could be reliably detected.
We show how one aspect of the code design problem can
be expressed and solved in terms of polynomial
arithmetic and linear algebra, demonstrating that
clever encoding choices enhance the detecting
capability of the system significantly beyond the 32
consecutive data bits guaranteed by the IEEE 802 polynomial.
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Jeffrey Farr
Affiliation: Mathematics, SFU
Email: jfarr@cecm.NOSPAM.sfu.ca (remove NOSPAM.)
Date: Tuesday, 27 January 2004
Time: 3:30 - 4:20
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: A New Polynomial Construction for some Linear Codes
Abstract:
We present a new construction of linear codes using mulitivariate polynomials
and Grobner basis theory. The construction is valid for any field size and for
any code length. The class of codes from this construction is rich in the sense
that it includes most of the currently known good codes, e.g. the algebraic
geometry one-point codes, as special cases. We can also search for good codes
over fields where the algebraic geometry approach is hard to apply. For example,
the construction of the well-known Hermitian codes works for fields whose sizes
are perfect square, but if the field size is not a square then it is not known
\in general how to get good codes using algebraic curves over this field. Our
construction enables us to search for good codes over finite fields of any size.
Joint work with Shuhong Gao and Daniel Noneaker
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Petr Lisonek
Affiliation: Simon Fraser University
Email: plisonek@math.sfu.NOSPAM.ca (remove NOSPAM.)
Date: Tuesday, 03 February 2004
Time: 3:30 - 4:20
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: Binary caps with many free pairs of points
Abstract:
A cap in PG(n,q) is a set S of points such that no three points
of S are collinear. We say that two points x,y of S form a "free pair"
if any plane containing x and y intersects S in at most three points.
In the language of coding theory (viewing S as a parity check matrix
of a q-ary linear code of distance at least 4) this condition means
that {x,y} is not a subset of the support of any codeword of weight 4.
Given m, n and q we ask what is the maximum number of free pairs
of points in a cap of cardinality m in PG(n,q). In this talk
we are concerned with the case q=2. We review the known lower bounds
and we improve the lower bound for certain combinations of m and n
using a construction based on BCH codes. The motivation for studying this
problem comes from statistical experiment design where free pairs
of points are called "clear 2-factor interactions".
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Jan Manuch
Affiliation: Simon Fraser University
Email: jmanuch@NOSPAM.sfu.ca (remove NOSPAM.)
Date: Tuesday, 10 February 2004
Time: 3:30 - 4:20
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: Inverse protein folding in 2D HP model
Abstract:
The inverse protein folding problem is that of designing an amino acid
sequence which has a particular native protein fold. This problem
arises in drug design where a particular structure is necessary to
ensure proper protein-protein interactions. In this talk, we show
that in the 2-D HP model of Dill it is possible to solve this problem
for a broad class of structures. These structures can be used to
closely approximate any given structure. One of the most important
properties of a "good" fold is its stability---the aptitude not to fold
simultanously into other structures. This is a necessary condition in
for drug design, for example. We show that for a number of basic structures,
our sequences have a unique fold.
This is a joint work with A. Gupta and L. Stacho
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Ladislav Stacho
Affiliation: Simon Fraser University
Email: lstacho@NOSPAM.sfu.ca (remove NOSPAM.)
Date: Tuesday, 24 February 2004
Time: 3:30 - 4:20
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: Traversal of quasi-planar subdivisions without using mark bits
Abstract:
The problem of traversal of planar subdivisions or other graph-like
structures without using mark bits is central to many real-world
applications. First such algorithms developed were able to traverse
triangulated subdivisions. Later these algorithm were extended to
traverse vertices of an arrangement or a convex polytope. The research
progress culminated to an algorithm that can traverse any planar
subdivision. In this talk, we extend the notion of planar subdivision
to quasi-planar subdivision in which we allow many edges to cross each
other. We generalize the algorithm for planar subdivision traversal to
traverse any quasi-planar subdivision that satisfies a simple requirement.
The worst case running time of our algorithm is $O(|E|\log|E|)$
which matches with the running time of the traversal algorithm for
planar subdivisions.
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Chris Mitchell
Affiliation: Royal Holloway, University of London, UK
Email: C.Mitchell@NOSPAM.rhul.ac.uk (remove NOSPAM.)
Date: Monday, 01 March 2004
Time: 3:30 - 4:20
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: Universal cycles of permutations
Abstract:
In 1992, Chung, Diaconis and Graham proposed the notion of a universal cycle.
Let A be a fixed (finite) alphabet, say |A|=m, and let S be some subset of all
possible k-tuples of elements of A. Then a universal cycle for S is a periodic
sequence of elements of A (of period s=|S|) such that each element of S occurs
at a unique position in a period of the sequence. If S is the set of all
possible k-tuples, i.e. s=m^k, then universal cycles are simply m-ary de Bruijn
sequences of span k. There are many unanswered questions about universal cycles.
In this talk we briefly mention some of the outstanding research problems.
We then consider the case where S is the set of all ordered k-subsets of
A (then s=m!/(m-k)!). The existence of such 'k-permutation' sequences for all
m and k (k < m) was demonstrated by Jackson in 1993. In this talk we describe two
novel (unpublished) methods of construction for such universal cycles, both
inspired by well-known constructions for de Bruijn sequences.
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Mahdad Khatirinejad Fard
Affiliation: Simon Fraser University
Email: mahdad@NOSPAM.sfu.ca (remove NOSPAM.)
Date: Tuesday, 02 March 2004
Time: 3:30 - 4:20
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: IC-Colorings and IC-indices of graphs
Abstract:
Given a coloring $f:V(G)\to \{ 1, 2, \ldots} of graph $G$ and any subgraph
$H$ of $G$ we define $f(H) = sum_{v \in V(H)} f(v)$. The coloring $f$ is
called an IC-coloring if for any integer $k\in [1, f(G)]$ there is a
connected subgraph $H$ of $G$ such that $f(H) = k$. Also, we define the
IC-index of $G$ to be $M(G)=\max\{ f(G): f is an IC-coloring of G \}$. We
examine some well-known classes of graphs and determine their IC-indices.
In addition, several conjectures are proposed.
This is joint work with E. Salehi and S. M. Lee.
--------------------------------------------------------------------------
Event: Discrete Math Colloquium
Speaker: Juergen Bierbrauer
Affiliation: Michigan Technological University
Email: jbierbra@mtu.NOSPAM.edu (remove NOSPAM.)
Date: Thursday, 11 March 2004
Time: 11:30 - 12:20
Place: K 9509
Title: Cyclic Codes and Their Applications
Abstract:
The traditional application of error-correcting codes is in the
transmission of messages over noisy channels. Another vast area
of applications is obtained when the dual code is interpreted
as a family of random variables with statistical independence properties.
Cyclic codes are a particularly well-studied family of linear codes.
We give an introduction to cyclic codes based on the action
of the Galois group. This direct approach is particularly easy to handle
and allows generalizations, for example to additive codes
and to constacyclic codes. Applications include the
construction of cyclic quantum codes, codes for deep-space communication
and computer-memory systems. Another link leads to finite geometries:
a linear code is a set of points in projective space. We present
a construction of caps based on cyclic codes. A close link
to the Kloosterman codes allows the determination of the weight distribution,
using certain class numbers of elliptic curves.
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Veselin Jungic
Affiliation: Simon Fraser University
Email: vjungic@sfu.NOSPAM.ca (remove NOSPAM.)
Date: Tuesday, 16 March 2004
Time: 3:30 - 4:20
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: Rainbow Ramsey Theory
Abstract:
An overview of the current state in research directions in the rainbow
Ramsey theory will be presented. A list of results, problems, and conjectures
related to existence of rainbow arithmetic progressions in $[n]$ and
$\N$ will be given. A general perspective on other rainbow Ramsey type
problems will be mentioned.
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Van Vu, Mathematics, UCSD
Affiliation: Simon Fraser University
Email: (remove NOSPAM.)
Date: Tuesday, 23 March 2004
Time: 3:30 - 4:20
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: Erdos-Folkman conjecture
Abstract:
In the 60's Erdos and Folkman made the following conjecture: Let A be a
sequence of positive integers with density at least Cn^{1/2} , where C is a
sufficiently large constant. (Namely, for all large n, A contains at least
Cn^{1/2} integers between one and n.) Then the partial sums of A contains
an infinite arithmetic progression.
Partial results have been obtained by several researches including Erdos
(62), Folkman (66), Hegyvari (94), Luczak and Schoen (94).
Recent Szemeredi and I proved the conjecture. I will give a brief review
about our approach and emphasize the connection between this problem
and Freiman's inverse theorem in additive number theory.
--------------------------------------------------------------------------
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Luis Goddyn
Affiliation: Simon Fraser University
Email: goddyn@math.sfu.NOSPAM.ca (remove NOSPAM.)
Date: Tuesday, 30 March 2004
Time: 3:30 - 4:20
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: From graceful labelings to Heawood embeddings.
Abstract:
Heawood's map colour theorem is the analogue of the Four Colour Theorem for
graphs embedded on higher surfaces. Part of the proof involves showing that
K_n embeds as a triangulation of an orientable surface, for every n = 12k +7.
We describe a construction which results in such an embedding for every
graceful labeling of a path of order 2k+1. Moreover, the construction is
injective: distinct graceful labelings give non-isomorphic triangulations.
Aldred et al have shown that there are asymtotically at least (5/3)^(2k)
distinct graceful labelings of the path. Therefore, there are exponetially
many minimal-genus embeddings of K_n, when n is congurent to 7 modulo 12.
This is joint work with J. Siran and B. Richter.
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Jozsef Solymosi
Affiliation: University of British Columbia
Email: solymosi@math.ubc.NOSPAM.ca (remove NOSPAM.)
Date: Tuesday, 06 April 2004
Time: 3:30 - 4:20
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: Applications of hypergraph regularity
Abstract:
An old conjecture of Erdos, Frankl and Rodl has been proved recently by B. Nagle,
V. Rodl, M. Schacht and J. Skokan and, independently, by W.T. Gowers. Roughly
speaking, the conjecture states that if every edge of an r-uniform hypergraph,
H_n, is an edge of precisely one clique in the graph, then the number of cliques
in H_n is o(n^{r+1}). The main tool in both proofs is a new, efficient Hypergraph
Regularity Lemma. We will formulate simplified, but still useful versions of this
new hypergraph regularity lemma, with some applications to geometry, number theory,
and graph theory.
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Daniel Kral
Affiliation: Charles University
Email:
Date: Tuesday, 18 May 2004
Time: 3:30 - 4:20
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: Circular edge-colorings of graphs with large girth
Abstract:
A circular (p/q)-edge-coloring is a coloring of edges of a graph
by colors 0, ..., p-1 such that the difference modulo p of colors
assigned to two incident edges is not among -(q-1), -(q-2), ...,
q-1. A circular (p/q)-edge-coloring can also be viewed as a coloring
by points on a circle of circumference p in such a way that a pair of
incident edges receive colors which are at distance at least q
on the cycle. The smallest ratio p/q for which there is a proper
circular (p/q)-edge-coloring is called the circular chromatic
index of G.
In the first part of the talk, we show that for each t>0, there
exists a number g such that the circular chromatic index of every
cubic bridgeless graph with girth at least g is at most 3+t.
This contrasts to the result of Kochol (who disproved the Girth
Conjecture) that there are snarks of arbitrarily large girth.
We also show that every cubic bridgeless graph with girth at least
14 has the circular chromatic index at most 7/2.
In the second part of the talk, we further generalize this result
and obtain the following: for each t>0 and each integer D>=1,
there exists a number g such that the circular chromatic index of
every graph of maximum degree at most D whose girth is at least g
is bounded by D+t.
(joint work Tomas Kaiser and Riste Skrekovski)
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Peter Pleasants
Affiliation: University of Queensland
Email: peterpleasants@iprimus.NOSPAM.com.au (remove NOSPAM.)
Date: Friday, 28 May 2004
Time: 11:30-12:20
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: Almost disjoint families of 3-term arithmetic progressions
Abstract:
I shall talk about joint work with Tom Brown and Hayri Ardal on
Tom's problem of the maximal number $A(n)$ of 3-term arithmetic
progressions of integers that can be packed into the interval $[0,n-1]$
when no two are allowed to overlap in more than one place. This is
the simplest possible example of introducing an arithmetic constraint
to an extremal problem in set theory, but nevertheless exhibits some
surprisingly rich structure. We show that $A(n)$ is asymptotic to
$Cn^2$ with $1.89 < C < 1.94$ A byproduct of estimating $C$ is a remarkable
identity relating a sum of functions of binary numbers to a sum
involving the Riemann zeta-function at integer values.
--------------------------------------------------------------------------
Event: Colloquium
Speaker: Nantel Bergeron
Affiliation: York University
Date: Friday, 28 May 2004
Time: 2:30-4:00
Place: K 9509
Title: Combinatorial Hopf algebras
Abstract:
A combinatorial Hopf algebra is a graded connected Hopf algebra equipped
with a singled out character. These algebraic structures are very useful to
study. Combinatorial objects can often be combined to create more complicated
structures, or decomposed into simpler components. Enumeration and
classification of these structures often give rise to associated
graded Hopf algebra where multiplication and comultiplication encode
association and decomposition of the combinatorial objects. These Hopf
algebras of combinatorial objects (combinatorial Hopf algebras) often
possess important structures that relate to other areas of science such
as mathematical physics, geometry, topology, etc.
We introduce the category of combinatorial Hopf algebra and discuss some of
its properties. As one particular application, we use this to expand the
theory of generalized Dehn-Somerville relations for polytopes to any
combinatorial Hopf algebra.
--------------------------------------------------------------------------
Event: Colloquium
Speaker: Bojan Mohar
Affiliation: University of Ljubljana
Host: Dept. of Mathematics
Date: Monday, 31 May 2004
Time: 2:30-4:00
Place: K 9509 (NOTE UNUSUAL TIME AND PLACE)
Title: Graph minors and graphs on surfaces
Abstract:
Robertson-Seymour's theory of graph minors is one of the highlights among
recent achievements in graph theory. Theory of graph minors is
fundamentally interconnected with the theory of graphs embedded in
surfaces. Robertson and Seymour used graph minors to prove a generalization
of the Kuratowski Theorem to arbitrary surfaces, while they also need
surface embeddings in their Excluded Minor Theorem. In the talk, this
interplay of two theories together with demonstration of some recent
results related to graph minors and graphs on surfaces will be presented.
--------------------------------------------------------------------------
Event: Colloquium
Speaker: Marni Mishna
Affiliation: LaBRI, University of Bordeaux
Host: Dept. of Mathematics
Date: Tuesday, 29 June 2004
Time: 2:30 - 3:20
Place: K 9509 (NOTE UNUSUAL TIME AND PLACE)
Title: On the utility of effective D-finite symmetric functions in combinatorics
Abstract:
Symmetric functions can be useful to express a number of different
kind of enumerative combinatorics problems. In particular, using a
scalar product one can extract generating series of sub-classes of
families so encoded. Here, we shall illustrate how to make
this product effective, (owing to the fact that it preserves a
property called D-finiteness); we generalize to scalar products of
other kinds of symmetric functions made effective in a similar way;
and we group families of enumerative results that are now consequences
of this technique. We conclude with musings about if the algebraic
framework developed in the course of this investigation may be
applied to NP-complete problems.
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Bruce Reed, Canada Research Chair in Graph Theory
Affiliation: School of Computer Science, McGill University
Email: breed@NOSPAM.cs.mcgill.ca (remove NOSPAM.)
Date: Tuesday, 13 July 2004
Time: 3:30 - 4:20
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: Vertex Colouring Edge Weightings
Abstract:
We discuss degree constrained subgraph problems.
Amongst other results, we show that the edges of any graph
can be assigned weights between 1 and 50 so that the
weighted vertex degrees give a proper colouring. I.e.
for every edge $uv$, the sum of the weights of the edges
incident to u differs from the sum of the weights of
the edges incident to v.
This is joint work with a number of coauthors.
--------------------------------------------------------------------------
Event: Mathematics Department Colloquium
Speaker: Nadya Shirokova
Affiliation: Institut Des Hautes Etudes Scientifique
Date: Tuesday, 20 July 2004
Time: 2:30pm
Place: K 9509
Title: Space approach to invariants for families
Abstract:
We construct spaces of manifolds of various dimensions generalizing
Vassiliev's approach to the theory of knots. These are infinite-dimensional
spaces with hypersurface, corresponding to manifolds with Morse
singularities. We show that the connected components of the complement
to this discriminant are homotopy equivalent to the covering spaces
of BDiff(M). These spaces appear to be a natural base over which one
can consider parametrized versions of Floer and Seiberg-Witten theories.
--------------------------------------------------------------------------
Event: Discrete Math Colloquium
Speaker: Roman Nedela
Affiliation: Slovak Academy of Sciences
Host: Pavol Hell
Date: Tuesday, 27 July 2004
Time: 10:00am
Place: Halpern Centre, Room 126 (CECM Day)
Title: Regular maps - combinatorial objects relating different fields of mathematics
Abstract:
Regular maps and hypermaps are cellular decompositions
of closed surfaces exhibiting the highest possible number of symmetries.
The five Platonic solids present the most familiar examples of regular maps.
The great dodecahedron, a 5-valent pentagonal regular map on the
surface of genus 5 discovered by Kepler,
is probably the first known non-spherical regular map.
Modern history of regular maps goes back at least to Klein (1878)
who described a regular map of type $(3,7)$ on the
orientable surface of genus $3$. In its early times, the study of
regular maps was closely connected with group theory as one can
see in Burnside's famous monograph, and more recently in
Coxeter's and Moser's book (Chapter~8). The present-time
interest in regular maps extends to their connection to Dyck's
triangle groups, Riemann surfaces, algebraic curves, Galois
groups and other areas. Many of these links are nicely surveyed in
the recent papers of Jones, and Jones and Singerman.
The presented survey talk is an upgrade version of the talk given
at the conference ``Mathematics in the New Millenium'' held in
Seoul, October 2000. The idea is, on one hand side, to show the
relationship of (regular) maps and hypermaps to the above
mentioned fields of mathematics. On the other hand, we want to
stress some ideas and results that are important for understanding
of the nature of these interesting mathematical objects.
--------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Moshe Rosenfeld
Affiliation: University of Washington
Date: Tuesday, 10 August 2004
Time: 3:30 - 4:20
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: Prisms over graphs
Abstract:
The prism over a graph G is the cartesian product GxI_2 (that is two disjoint copies of
G plus a perfect matching between the two copies). In this talk I'll discuss; 1. Why Prisms
2. How? Prisms over graphs provide a good measure of closeness to being hamiltonian. Our
latest result (with Peter Horak, Tomas Kaiser and Zdenek Ryjacek) is that the prism over
the notorious middle-level graph is hamiltonian.
As usual, related open problems will be discussed.
---------------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Tomas Kaiser
Affiliation: University of West Bohemia
Date: Tuesday, 17 August 2004
Time: 3:30 - 4:20
Place: EAA 1100, SFU (Just North of B-lot by pedestrian stop-light)
Title: Eulerian colorings of graphs
Abstract:
We discuss the Bipartizing matchings conjecture of H. Fleischner, which is closely
related to several fundamental problems in graph theory, such as Tutte's 5-flow
conjecture or the Cycle double cover conjecture. We introduce a setting that allows
for a natural generalization of the conjecture and inspires new questions.
(joint work with Z. Dvorak and D. Kral)
--------------------------------------------------------------------------
Event: Colloquium
Speaker: Abraham P. Punnen
Affiliation: University of New Brunswick
Host: Dept. of Mathematics
Date: Tuesday, 21 September 2004
Time: 2:30 - 3:20
Place: K 9509 (note unusual place and time!)
Title: The number of distinct tour values for the traveling salesman problem: one, two, three, all
Abstract:
Polynomially testable characterization of cost matrices associated
with a complete digraph on $n$ nodes such that all Hamiltonian
cycles (tours) have the same cost is well known.
Tarasov (1981) obtained a characterization of cost matrices
where tour costs take two distinct values. We provide a simple
alternative characterization of such cost matrices that can be
tested in $O(n^2)$ time. We also provide analogous results where
tours are replaced by Hamiltonian paths. When the cost matrix is
skew-symmetric, we provide polynomially testable characterizations
such that the tour costs take three distinct values. Corresponding
results for the case of Hamiltonian paths are also given. Testing if
the tour values are distinct is observed to be NP-hard. Using
these results, special instances of the asymmetric travelling
salesman problem (ATSP) are identified that are solvable in
polynomial time and that have improved $\epsilon$-approximation
schemes. In particular, we observe that the 3/2 performance
guarantee of the Christofides algorithm extends to all metric
Hamiltonian symmetric matrices. Further, we identify special
classes of ATSP for which polynomial $\epsilon$-approximation
algorithms are available for $\epsilon \in \{3/2, 4/3, 4\tau,
\frac{3\tau^2}{2},
\frac{4+\delta}{3}\}$ where $\tau > 1/2$ and $\delta \geq 0$
Some related open problems will be discussed.
------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Arash Rafiey
Affiliation: University of London
Host: Dept. of Computer Science
Date: Tuesday, 28 September 2004
Time: 3:30 - 4:20
Place: EAA 1100 (Just North of B-lot by pedestrian stop-light)
Title: Characterization of edge-colored complete graphs with properly colored Hamilton paths
Abstract:
An edge-colored graph $H$ is properly colored if no two adjacent
edges of $H$ have the same color. In 1997, J. Bang-Jensen and G.
Gutin conjectured that an edge-colored complete graph $G$ has a
properly colored Hamilton path if and only if $G$ has a spanning
subgraph consisting of a properly colored path $C_0$ and a
(possibly empty) collection of properly colored cycles
$C_1,C_2,\ldots ,C_d$ such that $V(C_i)\cap V(C_j)=\emptyset$
provided $0\le i < j\le d.$ We prove this conjecture.
This is joint work with Gregory Gutin and Tommy Jensen
-------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Frank Fiedler
Affiliation: Simon Fraser University
Date: Tuesday, 5 October 2004
Time: 3:30 - 4:20
Place: EAA 1100 (Just North of B-lot by pedestrian stop-light)
Title: On the Degree of Mathon Maximal Arcs
Abstract:
Let $\pi$ be a projective plane of order $q$. Let $K$ be proper subset
consisting of $k$ points of $\pi$. Then $K$ is called a $\{k;n\}$-arc if
every line of $\pi$ meets $K$ in at most $n$ points. It is called a maximal
arc of degree $n$ if every line of $\pi$ meets $K$ in either $0$ or $n$ points.
Constructions for maximal arcs in planes of even order have been given by
Denniston (1969), Thas (1974, 1980), and, most recently, by Mathon (2001).
The latter uses a pair of certain polynomials $p(x)$ and $q(x)$ over $GF(q)$
to construct maximal arcs in $PG(2,2^m)$. It includes Denniston's arcs as
a special case.
We study the problem of determining the largest degree of a Mathon maximal
arc which is not a Denniston maximal arc. When $m\ge 5$ and $m\neq 9$, we
prove that Mathon maximal arcs generated by $\{p; 1\}$-maps have degree at
most $2^{\lfloor\frac{m}{2}\rfloor+1}$ if they are not Denniston maximal arcs.
We also prove theit existence. For general $\{p; q\}$-maps we prove that,
when $m\ge 7$ and $m\neq 9$, the largest degree of a non-Denniston maximal
arc generated by a $\{p; q\}$-map is either $2^{\lfloor\frac{m}{2}\rfloor+1}$
or $2^{\lfloor\frac{m}{2}\rfloor+2}$.
(joint work with K.H. Leung and Q. Xiang)
---------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Jonathan Jedwab
Affiliation: Simon Fraser University
Date: Tuesday, 12 October 2004
Time: 3:30 - 4:20
Place: EAA 1100 (Just North of B-lot by pedestrian stop-light)
Title: A Survey of the Merit Factor Problem for Binary Sequences
Abstract:
A classical problem of digital sequence design, first studied in the
1950s but still not well understood, is to determine those binary
sequences whose aperiodic autocorrelations are collectively small
according to some suitable measure. The merit factor is an important
such measure, and the problem of determining the best value of the merit
factor of long binary sequences has resisted decades of attack by
mathematicians and engineers. In equivalent guise, the determination of
the best asymptotic merit factor is an unsolved problem in complex
analysis proposed by Littlewood in the 1960s that until recently was
studied along largely independent lines. The same question also occurs
in theoretical physics and theoretical chemistry, where it is studied as
a notorious problem of combinatorial optimisation.
The best known value for the asymptotic merit factor has remained
unchanged since 1988. However recent experimental and theoretical
results strongly suggest a possible improvement. I shall describe from
first principles the merit factor problem and show how it arises in
multiple disciplines. I shall use this to place the recent results
within their historical and scientific framework.
---------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Ladislav Stacho
Affiliation: Simon Fraser University
Date: Tuesday, 19 October 2004
Time: 3:30 - 4:20
Place: EAA 1100 (Just North of B-lot by pedestrian stop-light)
Title: Asymptotics of random RNA
Abstract:
Motivated by computer experiments concerning the expected number of base pairs
in optimal secondary structure for random RNA, we study the asymptotics of the
expected maximum number of base pairs in secondary structures for random RNA
sequences of length n, both for the usual alphabet of A,C,G,U as well as for
the binary alphabet 0,1. After proving a general limit result, we obtain a
precise estimate of this aymptotic value for the binary alphabet with threshold
0, and prove an upper and lower bound for the arbitrary (constant) threshold
case. We relate this value to D(p), the ``dual'' of the well-known constant
L(p); here, n L(p) is asymptotically the expected length of the longest common
subsequence (LCS) of two random sequences of length n, each generated by
independently appending random bits, 1 with probability p and 0 with probability 1-p.
This is joint work with Peter Clote, Evangelos Kranakis, and Danny Krizanc.
---------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Jeffrey FARR
Affiliation: Simon Fraser University
Date: Tuesday, 26 October 2004
Time: 3:30 - 4:20
Place: EAA 1100 (Just North of B-lot by pedestrian stop-light)
Title: Large Caps with Free Pairs in PG(N,q)
Abstract:
A collection of points, C, in PG(N,q) is called a cap if no three points
in C are collinear. The study of caps in both affine and projective
geometries is well established yet still holds many interesting open
problems. In particular, outside of the projective (and affine) plane
and 3-space, very little is known about the size of the largest caps
possible in these spaces.
Motivated by an application in statistics, we present a new twist on
this old problem. A pair of points in C is said to form a free pair
if every plane through xy intersects C in at most three points. In
this talk we present an upperbound for the size of a cap with at least
one free pair in PG(N,q), and we give geometric and combinatorial
constructions to meet the bound exactly for N=3,4 and asymptotically
for N=5,6.
Joint work with Petr Lisonek.
---------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Mohammad Ghebleh
Affiliation: Simon Fraser University
Date: Tuesday, 2 November 2004
Time: 3:30 - 4:20
Place: EAA 1100 (Just North of B-lot by pedestrian stop-light)
Title: Circular chromatic number of even-faced torus graphs
Abstract:
By a torus graph we mean a graph which is embedded in the torus. We call a
torus graph even-faced if all the faces have even lengths. It is well-known
that the circular chromatic number of a graph with odd-girth 2k+1 is at
least 2+1/k. We show that for fixed odd-girth, this bound is tight for
even-faced torus graphs having high enough edge-width. We define a parameter
r=r(G) for any even-faced torus graph G which depends on the circuits of G
and we show that the circular chromatic number of G is at most 2+2/(r-1).
We show that r is equal to the odd-girth of G when G has large enough
edge-width. We also give several examples where r is not equal to the
odd-girth of G, yet our bound is tight.
---------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Petr Lisonek
Affiliation: Simon Fraser University
Date: Tuesday, 9 November 2004
Time: 3:30 - 4:20
Place: EAA 1100 (Just North of B-lot by pedestrian stop-light)
Title: Variable rate linear codes with an application to steganography
Abstract:
In the ``defective memory channel'' the memory consists of n bits, but only
certain k bits can be changed (overwritten) by the sender. The remaining n-k
bits are ``stuck'' at either 0 or 1. The location of the defective bits is
known to the sender, but it is not known to the receiver. Asymptotically,
the capacity of the defective memory channel is k bits, and there exist
codes of fixed rate about k/n realized in this channel. However, the
construction of such codes is quite involved.
Using the well-known formula for the probability of a rectangular matrix
of a given shape having a given rank over GF(q), we develop a variable
rate binary linear code realized in the defective memory channel, which
asymptotically achieves the optimal capacity of about k bits. We mention
an application to steganography (information hiding). We also discuss
a generalization to q-ary linear codes with q > 2.
This is joint work with J. Fridrich and M. Goljan.
---------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Luis Goddyn
Affiliation: Simon Fraser University
Date: Tuesday, 16 November 2004
Time: 3:30 - 4:20
Place: EAA 1100 (Just North of B-lot by pedestrian stop-light)
Title: Two results for the Lonely Runner
Abstract:
At noon, $n$ runners begin to run laps on a circular track, starting at the origin.
Each runner maintains a constant, distinct speed for many laps. A runner is
``lonely'' if no other runner is within 1/n of a lap in front or behind. The
Lonely Runner Conjecture of J. Wills asserts that each runner is, at some time, lonely.
First:
This problem is connected to the following property of a totally unimodular matrix
M: Let v be a vector in the nullspace of M such that no entry of v is zero and the
number of distinct entries in v is < k. Then the nullspace contains a vector whose
entries have magnitudes which lie in {1,2,...,k-1}. The proof uses flows, colourings,
matroid decompositions and a deletion/contraction argument. This is joint work with
several authors in two papers.
Second:
We investigate instances of the Lonely Runner Conjecture for which the proposed
bound (1/n) is attained. We find three sporatic instances, and characterize an
infinite family. The characterization motivates the following number-theoretic
question: Find the least positive integer which is not relatively prime to any
integer in a given interval [s,t].
Erick Wong and I solve this when t/s > 1 + epsilon.
---------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Pavol Hell
Affiliation: Simon Fraser University
Date: Tuesday, 23 November 2004
Time: 3:30 - 4:20
Place: EAA 1100 (Just North of B-lot by pedestrian stop-light)
Title: Matrix partitions of perfect graphs
Abstract:
Given a matrix M, an M-partition of a graph G partitions the vertices of G
into cliques, independent sets, and aribtrary sets, with edges between the
parts governed by the entries (0, 1, or *) of the matrix M. Matrix partitions
generalize graph colourings and homomorphisms, and also naturally arise in
the theory of graph perfection. I will focus on matrix partition problems
restricted to perfect graphs. While many problems, like colourings and
homomorphisms become polynomial for perfect graphs, there remain NP-complete
matrix partition problems, even when restricted to split graphs. The results
are joint with Feder, Huang, Klein, Nogueira, Protti, Cameron, and others.
---------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Xuding Zhu
Affiliation: National Sun Yat-sen University
Date: Tuesday, 30 November 2004
Time: 3:45 - 4:30
Place: EAA 1100 (Just North of B-lot by pedestrian stop-light)
Title: Circular coloring of Kneser graphs, Schrijver graphs
and cones over graphs
Abstract:
The circular chromatic number of a graph is a refinement
of its chromatic number. In this talk, I will define the concept and try
to explain the motivation for defining this parameter. Then I will
survey some results concerning the circular chromatic number of
Kneser graphs, Schrijver graphs and cones over graphs. A common
feature of these graphs is that their chromatic number and fractional
chromatic number are usually far apart, which makes it difficult to
prove good lower bounds for their chromatic number and circular
chromatic number.
---------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Victor Dalmau
Affiliation: Universitat Pompeu Fabra
Date: Tuesday, 7 December 2004
Time: 3:30 - 4:20
Place: EAA 1100 (Just North of B-lot by pedestrian stop-light)
Title: Constraint Satisfaction Problems and Expressiveness
Abstract:
Constraint satisfaction problems arise in a wide variety of domains, such
as combinatorics, logic, and artificial intelligence. In recent years, much
effort has been directed towards classifying the complexity of all families
of constraint satisfaction problems. It has been shown that it is possible
to associate to every subclass of the CSP an algebra ${\bf A}$ such that
the complexity the corresponding CSP is completely determined by the
properties of ${\bf A}$.
Let ${\bf A}$ be any algebra over a finite universe. We define the
{\em expressiveness} of ${\bf A}$ as the mapping
$\hbox{ex}_{\bf A}:{\cal N}\rightarrow{\cal N}$ that given a natural number
$n$ returns the number subuniverses of ${\bf A}^n$. Some algebras ${\bf A}$
that lead to tractable cases of the CSP such as Mal'tsev algebras, or
algebras containing a near-unanimity operations among their term operations,
satisfy the following property: $\log \hbox{ex}_{\bf A}(n)\leq p(n)$, for
some polynomial $p$. We call any such algebra {\em polynomially expressible}.
We conjecture that all polynomially expressible algebras give rise to
families of constraint satisfaction problems solvable in polynomial time.
In this talk we shall present some initial results in this direction.
---------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Colin Percival
Affiliation: University of Oxford
Date: Tuesday, 18 January 2005
Time: 3:30 - 4:20
Place: EAA 1100 (Just North of B-lot by pedestrian stop-light)
Title: Matching with mismatches
Abstract:
Given two strings S, T of lengths n >> m over some fixed alphabet, the problem
of "matching with mismatches" is to enumerate the positions x_i in S where the
string T matches with the fewest mismatching characters. It is a far more
restricted problem than most problems of approximate string matching, in that
no insertions, deletions, or permutations are permitted.
I will present a randomized algorithm which, given some assumptions about the
randomness of the strings S, T and some linear-time preprocessing of the string
S, operates O(m / log(n)) times faster than existing algorithms for constant
mismatch rates.
---------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Peter Horak
Affiliation: University of Washington
Date: Thursday, 10 February 2005
Time: 3:30 - 4:20
Place: EAA 1100 (Just North of B-lot by pedestrian stop-light)
Title: Completing Latin squares
Abstract:
Some new and old problems concerned with completing Latin squares will be
discussed. First we will focus on variations on P. Hall's theorem, e.g.
completing Latin parallelepipeds, orthogonal Latin squares. Recent results
on largest and smallest critical sets in Latin squares will be given.
Finally we mention a problem on approximation of Latin squares by
polynomials. Such Latin squares are used as a part of block cipher
algorithms.
---------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Binay Bhattacharya
Affiliation: Simon Fraser University
Date: Tuesday, 15 February 2005
Time: 3:30 - 4:20
Place: EAA 1100 (Just North of B-lot by pedestrian stop-light)
Title: Collection depots problem on networks
Abstract:
We investigate the problem of locating service facilities that need to
service customers on a network. In order to provide service, a server
has to visit both the customer node and one of several collection depots.
We will discuss the various issues involved and provide efficient solutions
to locate one service station when the network is a tree or the customers
and the depots are points in the plane.
---------------------------------------------------------------------------
Event: Discrete Math/PiMS Seminar
Speaker: Evangelos Kranakis
Affiliation: Carleton University
Date: Tuesday, 22 February 2005
Time: 3:30 - 4:20
Place: EAA 1100 (Just North of B-lot by pedestrian stop-light)
Title: The Mobile Agent Rendezvous Problem
Abstract:
In the rendezvous search problem, two mobile agents must move
along the nodes of a network so as to minimize the time required
to meet or rendezvous. This simple optimization problem has
applications in P2P networking and information retrieval. In this
talk we survey recent results and models on rendezvous for a variety
of networks.
---------------------------------------------------------------------------
Event: Computer Algebra and Discrete Math Seminar
Speaker: Chris Mitchell
Affiliation: Royal Holloway, University of London
Date: Monday, 28 February 2005
Time: 4:00 - 5:00
Place: K9509
Title: Cryptanalysis of methods for combining confidentiality and integrity
Abstract:
Traditionally, the recommended approach for using a block cipher to provide
both integrity and confidentiality protection for a message has been to
compute a CBC-MAC and also encrypt the data, using two distinct block cipher
keys. This approach is rather unattractive for some applications because it
requires each block of data to be processed twice. This observation has given
rise to a number of proposals for combining encryption and integrity protection,
including a well-established family of encryption modes known as PCBC, dating
back to the early 1980s, and a number of much more recent modes, including OCB,
EAX and CCM. In this talk we examine two different variants of PCBC. We first
examine a variant we call PCBC+, which was one of the first ever proposals for
a block cipher mode of operation designed to provide both integrity and
confidentiality protection; despite the fact that it has been described in two
well known textbooks, this mode has never previously been attacked. However,
we show that this variant is subject to a known plaintext attack, and hence
does not provide adequate integrity protection. We go on to show that a more
recently proposed block cipher mode of operation called MPCBC, which is also
claimed to provide both integrity and confidentiality protection, is also very
weak.
---------------------------------------------------------------------------
Event: Discrete Math Seminar
Speaker: Nathaniel Linial
Affiliation: Microsoft Corporation & Hebrew Universioty
Date: Tuesday, 1 March 2005
Time: 3:30 - 4:20
Place: EAA 1100 (Just North of B-lot by pedestrian stop-light)
Title: Finite Metric Spaces - a quick overview
Abstract:
During the last ten years, we saw great interest and
wonderful progress in the study of finite metric spaces.
The investigations in this area combine methods from
combinatorics and geometry, in particular incorporating
important ideas from the classical study of
finite-dimensional normed spaces. Much of the motivation
and some of the most beautiful results come from
the field of algorithm design. Thus some of the most
surprising recent advances in the design of approximation
algorithms for NP-hard problems rely on concepts and ideas
that have emerged in the study of finite metric spaces.
A comprehensive coverage of this area already requires
a semester-long course, but I hope to convey in this
seminar some of the main findings, the open questions and
the great excitement offered by this field.
The talk is self-contained and no particular previous
background in this area is necessary to follow it.
---------------------------------------------------------------------------
Event: Discrete Math Seminar
Speaker: Frank Fiedler
Affiliation: Simon Fraser University
Date: Tuesday, 15 March 2005
Time: 3:30 - 4:20
Place: EAA 1100 (Just North of B-lot by pedestrian stop-light)
Title: The Search for More Golay Sequences
Abstract:
In 1999 Davis and Jedwab gave a direct construction of Golay complementary
sequences over $Z_{2^h}$ of length $2^m$. Recently Li and Chu found more
examples of quaternary Golay complementary sequences of length 16 by
exhaustive computer enumeration. These sequences could not be obtained
with the construction in [DavJed99]. We explain these newly-found Golay
sequences. We also investigate methods to find more examples that cannot
be constructed directly with [DavJed99].
---------------------------------------------------------------------------
Event: Discrete Math Seminar
Speaker: Petr Lisonek
Affiliation: Simon Fraser University
Date: Tuesday, 22 March 2005
Time: 3:30 - 4:20
Place: EAA 1100 (Just North of B-lot by pedestrian stop-light)
Title: Enumeration of Codes of Fixed Cardinality up to Isomorphism
Abstract:
We say that sequence (a_n) is quasi-polynomial in n
if a_n=P(n) where P is a polynomial with periodically
varying coefficients. A q-ary non-linear code
with block size n and r codewords is a subset of A^n
of cardinality r, where A is an alphabet of q symbols.
Two such codes are isomorphic if one can be obtained
from the other by permuting the n coordinates
and then in each coordinate independently permuting
the alphabet symbols. This isomorphism relation
is induced by the group action of the wreath product
$S_A \wr S_n$ on $A^n$.
Let c(q,r,n) denote the number of isomorphism classes
of q-ary codes with block size n and r codewords.
We prove that, when the values of q and r are fixed,
the sequence c(q,r,n) is quasi-polynomial in n.
The main idea of the proof is to express,
for any fixed q and r, the value c(q,r,n)
as the lattice point count in the union of a finite set
of polytopes parameterized by n.
We also discuss strategies for computing closed forms
for the generating function for c(q,r,n) when q,r are fixed.
Besides counting lattice points in polytopes we also
use G-partitions, which are orbits of number compositions
with k parts under a subgroup G of symmetric group S_k.
---------------------------------------------------------------------------
Event: SFU Computing Science Distinguished Lecture Series
Speaker: Laszlo Lovasz
Affiliation: Microsoft Research and Eotvos Lorand University
Date: Tuesday, 29 March 2005
Time: 4:30 - 5:30
Place: AQ 3182
Title: Graph homomorphisms, statistical physics, and limits of graph
sequences
Abstract:
Counting homomorphisms between graphs has a surprising number of applications.
Many models in statistical mechanics and many questions in extremal graph
theory can be phrased in these terms. We introduce a matrix, which we call
the connection matrix, and show that this is positive semidefinite (in
statistical mechanics, a related fact is called "reflection positivity").
This fact contains many results in extremal graph theory and in the theory
of quasirandom graphs. Using properties of this matrix, one can define and
characterize "convergence" for a sequence of graphs whose size tends to
infinity, and construct a limit object from which the limiting values of
many graph parameters can be read off. This is closely related to
"property testing" in computer science, and to "mean field theories"
in statistical physics. This is joint work with many people, including
Christian Borgs, Jennifer Chayes, Mike Freedman, Jeff Kahn, Lex Schrijver,
Vera Sos, Balazs Szegedy, Kati Vesztergombi and Dominic Welsh.
---------------------------------------------------------------------------3
Event: Discrete Math Seminar
Speaker: Boaz Benmoshe
Affiliation: Simon Fraser University
Date: Tuesday, 05 April 2005
Time: 3:30 - 4:20
Place: EAA 1100 (Just North of B-lot by pedestrian stop-light)
Title: Guarding 1.5D terrains
Abstract:
In this talk I will address guarding problems, visibility graphs, and
geometric structures implied by 1.5D terrains. During the talk a set of
open questions will be presented.
A first constant-factor approximation algorithm for a non-trivial instance
of the optimal guarding (coverage) problem in polygons will be presented.
In particular, an O(1)-approximation algorithm for placing the fewest point
guards on a 1.5D terrain, so that every point of the terrain is seen by at
least one guard. Note that poly-logarithmic-factor approximations follow from
set cover results.
This talk requires no computational geometry background.
---------------------------------------------------------------------------
Event: Discrete Math Seminar
Speaker: Cedric Chauve
Affiliation: Université du Québec À Montréal
Date: Tuesday, 03 May 2005
Time: 3:30 - 4:20
Place: EAA 1100 (Just North of B-lot by pedestrian stop-light)
Title: Conservation of combinatorial structure in genome rearrangement
scenarios
Abstract:
We investigate the problem of conservation of combinatorial structures in
genome rearrangement scenarios. We characterize an interesting class of
signed permutations, called perfect permutations, for which one can compute
in polynomial time a reversal scenario that conserves all common intervals
and is parsimonious among such scenarios. The general problem has been shown
to be NP-hard (Figeac & Varre, 2004) We show that there exists a class of
permutations, called commuting permutations, for which this computation can
be done in linear time, while in the larger class of perfect permutations,
the computation can be achieved in quasi-linear time. Our algorithms rely
on an interesting relation between common intervals and the theory of modular
decomposition of permutation graphs.
---------------------------------------------------------------------------
Event: Discrete Math Seminar
Speaker: Rados Radoicic
Affiliation: Rutgers University
Date: Tuesday, 17 May 2005
Time: 3:30 - 4:20
Place: EAA 1100 (Just North of B-lot by pedestrian stop-light)
Title: Intersection patterns of geometric objects
Abstract:
Not every graph can be obtained as the intersection graph
of, say, straight-line segments (or other geometric objects) in the
plane. These graphs have many nice structural properties. In
particular, they contain much larger homogeneous subgraphs than
guaranteed by Ramsey's theorem. It seems that this phenomenon is
related to some basic topological facts, including the Borsuk-Ulam
theorem. But does it have anything to do with algebra? We discuss this
question and as a byproduct, we prove a conjecture of Erdos about
distance distributions in d-space. Our proof uses Szemeredi's
regularity lemma.
This is a joint work with N. Alon, J. Pach, R. Pinchasi, M. Sharir,
and J. Vondrak.
---------------------------------------------------------------------------
Event: Discrete Math Seminar
Speaker: Danny Dyer
Affiliation: University of Regina
Date: Tuesday, 31 May 2005
Time: 3:30 - 4:20
Place: EAA 1100 (Just North of B-lot by pedestrian stop-light)
Title: Digraphs with small sweep number
Abstract:
Clearing a network of intruders is an interesting problem that has several
applications. When intruders can be located at vertices of along edges, we
speak of a sweeping a network (or graph). Sweeping has been studied almost
exclusively for graphs. We study the problem of sweeping digraphs for
different sweeping models. The sweep number is the minimum number of
sweepers needed to capture intruders in a digraph. We characterize those
digraphs with sweep number 1, and characterize those digraphs with sweep
number 2 for most models.
This is joint work with Brian Alspach, Denis Hanson, and Boting Yang.
---------------------------------------------------------------------------
Event: Discrete Math Seminar
Speaker: Anna Galluccio
Affiliation: IASI-CNR, Roma, Italy
Date: Tuesday, 21 Jun 2005
Time: 3:30 - 4:20
Place: EAA 1100 (Just North of B-lot by pedestrian stop-light)
Title: Regular Join Graphs
Abstract:
We consider the following 1-Factorization Conjecture:
Let G be a k-regular simple graph with an even number of vertices n.
If k is greater than or equal to n/2, then G is k-edge-colourable.
We show that this conjecture holds true for the class of join graphs.
The proof of the result is constructive and provides a polynomial time
algorithm to find a k-edge-colouring of k-regular join graphs of even size.
---------------------------------------------------------------------------
Event: Joint Discrete Math/Computing Science Seminar
Speaker: Mordecai Golin
Affiliation: Hong Kong University of Science and Technology
Date: Tuesday, 28 Jun 2005
Time: 3:30 - 4:20
Place: IRMACS Lecture Theatre (Note unusual veniue)
Title: The Knuth-Yao Quadrangle-Inequality & Total-Monotonicity
Abstract:
There exist several general techniques for speeding up naive
implementations of dynamic programming. Two of the best known are the
Knuth-Yao quadrangle inequality speedup and the SMAWK algorithm for
finding the row-minima of totally monotone matrices. Although both of
these techniques use a quadrangle inequality and seem similar, they
are actually quite different and have been used differently in the
literature.
In this talk we show that the Knuth-Yao technique is actually a direct
consequence of total monotonicity. As well as providing new
derivations of the Knuth-Yao result, this permits showing how to solve the
Knuth-Yao problem directly using the SMAWK algorithm. It also
give a method for solving online versions of problems with the
Knuth-Yao property using algorithms that are as fast as the
best previously known static ones. All of these observations are
not just restricted to the classic Knuth-Yao technique but
also hold for various generalizations developed later in the literature.
This is joint work with Wolf Bein, Larry Larmore and Yan Zhang.
---------------------------------------------------------------------------
Event: CECM Colloquium in Discrete Math
Speaker: Ebad Mahmoodian
Affiliation: Sharif University, Tehran, Iran
Date: Wednesday, 06 July 2005
Time: 3:30 - 4:20
Place: IRMACS Lecture Theatre (Note unusual veniue)
Title: Problems and Motivations
Abstract:
We present as examples, some problems which motivate
undergraduates, or even high school students, to do research
in mathematics. These problems are related to the speaker's
research activity. They have been presented in the past
to recruit very bright students.
---------------------------------------------------------------------------
Event: Discrete Math Seminar
Speaker: Ron Aharoni
Affiliation: Technion Institute, Haifa, Israel
Date: Tuesday, 19 Jul 2005
Time: 3:30 - 4:20
Place: EAA 1100 (Just North of B-lot by pedestrian stop-light)
Title: Topological methods in matching theory
Abstract:
In 1912 two fundamental theorems were proved: Frobenius' theorem,
which was the precursor of Hall's theorem, and the Brower's fixed point
theorem.
In a paper with Haxell, from 2000, we discovered a surprising connection
between the two: Hall's theorem can be proved using the Brower's fixed point
theorem. Moreover, this proof goes far beyond the combinatorial proofs, and
yields far reaching generalizations, like matchings in hypergraphs and
matroids. The talk will describe the basic idea behind this approach.
---------------------------------------------------------------------------
Event: (First!) Joint SFU/UBC Discrete Math Seminar
Speaker: Gabor Tardos
Affiliation: Simon Fraser University
Date: September 13, Tuesday
Time: 3:30-4:30pm
Place: WMAX 216 PIMS at UBC (www.pims.math.ca)
Address: 1933 West Mall, UBC
itle: Toward an Extremal Theory of Ordered Graphs
Abstract:
Pattern avoidance raises very interesting extremal enumerative
and structural problems in many different contexts from Turan-type
extremal graph theory to Davenport-Schinzel theory. This survey
talk concentrates to 0-1 matrices and (the closely related
concepts of) ordered graphs. An ordered graph is simple graph
together with a linear order on its vertices.
---------------------------------------------------------------------------
Event: Discrete Math Seminar
Speaker: Brian Alspach
Affiliation: University of Regina, SK
Date: Tuesday, 20 Sep 2005
Time: 3:30 - 4:20
Place: ASB 10908 (IRMACS Seminar Room), SFU
Title: Time constrained searching and sweeping
Abstract:
Attempting to capture an intruder in a graph when the intruder
may be located at vertices or along edges is known as sweeping.
When the intruder may be located only at vertices, the process is known
as searching. I shall discuss several models for searching and sweeping.
I'll then move to some new work on searching and sweeping when there
are time constraints present.
---------------------------------------------------------------------------
Event: Joint SFU/UBC Discrete Math Seminar
Speaker: Richard Anstee
Affiliation: University British Columbia
Date: Tuesday, 27 Sep 2005
Time: 3:30 - 4:20
Place: ASB 10908 (IRMACS Seminar Room), SFU
Title: Forbidden Configurations: An update
Abstract:
Forbidden configurations are a kind of forbidden induced 'pattern' in
matrices (for those who attended Gabor Tardos' lecture). We say a
(0,1)-matrix is simple if it has no repeated columns. Let F be a k x l
(0,1)-matrix. We say that a simple matrix A has no F-configuration if
no submatrix of A is a row and column permutation of F. We are interested
in the extremal function forb(m,F) which is the maximum number of columns
in an m-rowed simple matrix that has no F-configuration.
A conjecture of Sali and A. predicts the assymptotic behaviour of forb(m,F)
for fixed F as m tends to infinity. With Keevash, we develop a stability
result for k-uniform t-intersecting set systems that determines forb(m,F)
for F being k x 2. With Fleming, Furedi and Sali, we have a linear algebra
argument for all but `one' k x l F where forb(m,F) is O(m^{k-1}).
This is joint work with Peter Keevash, Balin Fleming, Zoltan Furedi, and
Attila Sali
---------------------------------------------------------------------------
Event: Discrete Math Seminar
Speaker: Matt DeVos
Affiliation: Simon Fraser University
Date: Tuesday, 04 Oct 2005
Time: 3:30 - 4:20
Place: EAA 1100 (Just North of B-lot by pedestrian stop-light)
Title: Pentagon Colouring
Abstract:
Graph homomorphisms provide a natural and interesting generalization
of graph colouring. In this talk, we will discuss two open problems
concerning homomorphisms to a pentagon - or "pentagon colouring".
The first is a conjecture of Nesetril that every cubic graph
of sufficiently high girth has a pentagon colouring. For this
problem, we outline a recent computer based proof (joint with
Robert Samal) that every cubic graph of girth 17 has a type of
weak pentagon colouring.
The second problem is a conjecture of Jaeger that every planar
graph with no odd cycles of length <8 has a pentagon colouring.
For this problem we will sketch some recent work (joint with
Adam Deckelbaum) which verifies the conjecture for graphs with
no odd cycle of length <10.
---------------------------------------------------------------------------
Event: Joint SFU/UBC Discrete Math/Theory CS Seminar
Speaker: Bojan Mohar
Affiliation: Simon Fraser University
Date: Tuesday, 11 Oct 2005
Time: 3:30 - 4:20
Place: IRMACS Theatre, ASB 10900, SFU
Title: Quadrangulations, Eulerian triangulations, and 5-critical graphs
Abstract:
Quadrangulations of the projective plane (and of other nonorientable
surfaces) have interesting properties in relation to graph colorings.
Some of them will be uncovered in this talk and applied to the
study of colorings of locally 3-colorable triangulations.
---------------------------------------------------------------------------
Event: Joint SFU/UBC Discrete Math/Theory CS Seminar
Speaker: David Kirkpatrick
Affiliation: University of British Columbia
Date: Tuesday, 25 Oct 2005
Time: 3:30 - 4:30
Place: WMAX 216 PIMS at UBC (www.pims.math.ca)
Address: 1933 West Mall, UBC
Title: Minimizing precision/input in the evaluation of geometric primitives
Abstract:
Suppose that $S$ is a collection of $n$ points, each specified by $k$-bit
coordinates. We want to determine some property of $S$: for example, does one
distinguished point in $S$ lie in the interior of the convex hull of the rest.
For some instances $S$, all (or most) of the bits of all (or most) of the points
need to be examined in order to determine the property; for other instances the
property can be established by examining only a (relatively) small number of bits.
In general we would like to devise algorithms whose cost (number of bits examined)
adapts to the intrinsic cost (shortest "proof" of the property) for a particular input.
The problem of constructing such algorithms for certain simple geometric primitives
was posed by Leo Guibas. I will describe some preliminary results concerning
certain very basic questions of this type, based on joint work with Raimund Seidel.
---------------------------------------------------------------------------
Event: Joint SFU/UBC Discrete Math/CS Theory Seminar
Speaker: Luis Goddyn, Simon Fraser University
Affiliation: Simon Fraser University
Date: Tuesday, November 8
Time: 3:30 - 4:20
Place: WMAX 216 PIMS at UBC (www.pims.math.ca)
Address: 1933 West Mall, UBC
Title: An Optimization Problem Arising from Video-on-Demand Broadcasting
Abstract:
A common protocol (FDPB) for video-on-demand specifies that a
large document (a movie) be divided into consecutive time segments
$s_1, \dots, s_n$. The segments are continually broadcast through
a single channel according to a specified periodic schedule
such as $s_1, s_5, s_2, s_1, s_3, s_4, s_1, s_2, s_3, \dots$.
A client may, at any time, decide to watch the movie.
Segments $s_i$ with a small subscript $i$ should appear frequently
in the schedule, so the viewer does not have to wait long for the
movie to begin. Segments with large $i$ may appear less frequently
since they can be loaded while the movie is already playing.
An optimal schedule minimizes the initial delay time while guaranteeing
that the movie does not have to pause to await a missing segment.
A (patented) solution to this problem involves a "round-robin tree".
To implement their protocol efficiently, one must solve the following
optimization problem. Given a large positive integer $n_0$,
we seek a positive integer $d$ which maximizes $n_d$, where
$n_1, n_2, \dots, n_d$ are defined by
$ n_{i+1} = n_i + \floor( n_i / d ) $, $ 0 \le i < d$.
For a fixed $n_0$, the value of $n_d$ behaves erratically as a
function of $d$. We show that the optimal value of $d$
can be determined by examining a small interval centred
at $1.2578 \sqrt{ n_0 }$. This greatly improves the linear-time
search proposed by the patent holders (Hollmann et al, 1995).
This is joint work with T. Kameda and Y. Sun.
---------------------------------------------------------------------------
Event: Discrete Math Seminar
Speaker: Dr. Santosh Kabadi
Affiliation: University of New Brunswick
Date: Wednesday Nov 9 (Note unusual date)
Time: 3:30 - 4:20
Place: ASB 10908 (IRMACS seminar room), SFU
Host: Abraham Punnen
Title: Integer Exact Network Synthesis Problem
Abstract:
Given an $n x n$, integer, non-negative, symmetric matrix $R = (r_{ij})$,
we consider the problem of synthesizing an undirected network G on node set
$V=\{1, 2, ... , n\}$ with non-negative, integer edge capacities such that
(i) for any pair $\{i,j\}$ of distinct nodes in $V$, the value of
maximum flow between $i$ and $j$ in $G$ equals exactly $r_{ij}$; and
(ii) the sum of capacities of edges in $G$ is minimum.
In their 1970 paper, Chou and Frank claim to give an algorithm for
this problem. But, in his recent seminal book on Combinatorial Optimization,
Schrijver gives a counter-example to their claim. We present an $O(n^2)$
algorithm for the problem.
---------------------------------------------------------------------------
Event: Discrete Math Seminar
Speaker: Jonathan Jedwab
Affiliation: Simon Fraser Universtiy
Date: Tuesday Nov 15
Time: 3:30 - 4:20
Place: ASB 10908 (IRMACS Seminar Room), SFU
Title: Proof of the Barker array conjecture
Abstract:
A Barker array is a two-dimensional array of \pm 1 elements all of whose
non-trivial aperiodic autocorrelation coefficients take values in {-1, 0, 1}.
Using only elementary methods, we prove Alquaddoomi and Scholtz's conjecture
of 1989, that no s \times t Barker array having s, t > 1 exists
except when s = t = 2. (Joint work with Jim Davis and Ken Smith)
---------------------------------------------------------------------------
Event: 2005 Combinatorial Potlach
Date: Saturday, 19 Oct 2005
Time: 11:00 - 4:20
Place: Seattle University
Schedule:
10:00 AM Registration, Coffee and Donuts
11:00 AM Bojan Mohar, Small Separations in Symmetric Graphs
12:00 PM Lunch
2:00 PM Jenny Quinn, Determinants Via Determined Ants
3:00 PM Cookies, Coffee and Cokes ( = "Pop", for Canadians)
3:30 PM John Caughman, How Distance-Regular Graphs Got All Tangled Up with the Theory of Knots
4:30 PM Happy Hour, Dinner
Description:
Combinatorial Potlatches have been held for many years at various locations
around Puget Sound and southern British Columbia, and are an opportunity
for combinatorialists in the region to gather informally for a day of
invited talks and conversation. All are welcome.
Local Arrangements Committee: David Neel, Seattle University,
Program Committee: Nancy Neudauer, Pacific University
Communications Committee: Rob Beezer, Univ of Puget Sound
See Official Potlach Page for more information.
---------------------------------------------------------------------------
Event: Joint SFU/UBC Discrete Math Seminar
Speaker: Maria Chudnovsky
Affiliation: Princeton University
Date: Tuesday Jan 24, 2006
Time: 3:30 - 4:20
Place: ASB 10900 (IRMACS Lecture Theatre), SFU
Title: The Structure of bull-free graphs
Abstract:
A {\em bull} is a graph consisting of a triangle and two pendant edges.
A graph is said to be {\em bullfree} if it contains no induced subgraph
isomorphic to a bull. An obvious example of a bull free graph is a graph with
no triangle, or a graph with no stable set of size three; but there are others.
It turns out, however, that all bullfree graphs can be built starting from
graphs that belong to a few basic classes, and gluing them together by certain
operations; and this is the main topic of this talk. Using this structure
theorem, in joint work with S. Safra, we prove that every bullfree graph
has either a stable set or a clique containing at least $|V(G)|^(1/4)$ vertices,
thus settling the Erdos-Hajnal conjecture for the bull.
---------------------------------------------------------------------------
Event: Joint SFU/UBC Discrete Math Seminar
Speaker: Luis Goddyn
Affiliation: Simon Fraser University
Date: Tuesday Feb 14, 2006
Time: 3:30 - 4:20
Place: ASB 10900 (IRMACS Lecture Theatre), SFU
Title: Silver Cubes
Abstract:
An n by n matrix is *silver* if, for i=1,...,n, every symbol in
{1,2,...,2n-1} appears as an entry in either row i or column i.
An IMO 1997 question introduced this definition, and asked
whether a silver matrix of order 1997 exists.
(In fact, one exists if and only if n=1 or n is even.)
In this paper we investigate higher dimensional analogs,
silver cubes.
Finding the correct generalization is the first challenge.
The cells on the main diagonal of a silver matrix are treated
specially. What should serve as a "diagonal" in a d-dimensional
n x n x ... x n silver cube?
We propose that a "diagonal" should be a "maximum independent set
in the d'th cartesian power of the complete graph of order n."
This definition is motivated by "minimal defining sets" for
colouring such graphs. The goal is to label the cells
with symbols {1,2,...,d(n-1)+1} so that, for each cell c on
the "diagonal", every symbol appears once in one of the d(n-1)+1
cells orthogonally translated from c. We present constructions,
nonexistence proofs and connections with coding theory
and projective geometry.
This is joint work with M. Ghebleh, E. Mahmoodian and M. Verdian-Rizi.
---------------------------------------------------------------------------
Event: Joint SFU/UBC Discrete Math Seminar
Speaker: Shakhar Smorodinsky
Affiliation: Courant Institute
Date: Tuesday Feb 28, 2006
Time: 3:30 - 4:30
Place: WMAX 216 (PIMS UBC)
Title: On K-Sets in dimensions 2,3 and 4
Abstract:
Let $P$ be a set of $n$ points in the Euclidean $d$ dimensional space.
A subset $P'$ of $P$ is called a k-set if its cardinality is $k$
and there exists a half-space $H$ such that $P' = H\cap P$ (that is, $P'$
can be separated from its complement by a hyperplane). The problem of
determining the asymptotic of $f_d(n,k)$, the maximum number of distinct
$k$ sets that an $n$ element point set in $R^d$ can have (for a fixed $d$)
was posed more than 30 years ago by Lovasz and Erdos et al. Solution to
this problem remains elusive even in the plane (i.e., $d = 2$). We survey
the recent results that achieve the best known upper bounds in dimensions
two 2, 3 and 4. This problem has many applications in computational
geometry and some examples will be discussed.
---------------------------------------------------------------------------
Event: Joint SFU/UBC Discrete Math Seminar
Speaker: Arie Bialostocki
Affiliation: University of Idaho
Date: Tuesday Mar 14, 2006
Time: 3:30 - 4:20
Place: IRMACS Theatre, ASB 10900, SFU
Title: Some Problems in View of Recent Developments of the Erdos Ginzburg Ziv theorem
Abstract:
Two conjectures concerning the Erd¨os Ginzburg Ziv theorem were
recently confirmed. Reiher and di Fiore proved independently the two
dimension analogue of the EGZ theorem, as conjectured by Kemnitz, and
Grynkiewicz proved the weighed generalization of the EGZ theorem as
conjectured by Caro. These developments trigger some further problems.
First, we will present computer experiments that at least for small numbers
reveal very simple phenomena of zero sum theorems that seem to be difficult
to prove. Next, we will examine the notion of generalization of Ramsey type
theorems in the sense of a given zero sum theorem in view of the new
developments.
---------------------------------------------------------------------------
Event: Joint SFU/UBC Discrete Math Seminar
Speaker: Arie Bialostocki
Affiliation: University of Idaho
Date: Tuesday March 14, 2006
Time: 3:30 - 4:20
Place: IRMACS Theatre, ASB 10900, SFU
Title: Some Problems in View of Recent Developments of the Erdos Ginzburg Ziv theorem
Abstract:
Two conjectures concerning the Erd¨os Ginzburg Ziv theorem were
recently confirmed. Reiher and di Fiore proved independently the two
dimension analogue of the EGZ theorem, as conjectured by Kemnitz, and
Grynkiewicz proved the weighed generalization of the EGZ theorem as
conjectured by Caro. These developments trigger some further problems.
First, we will present computer experiments that at least for small numbers
reveal very simple phenomena of zero sum theorems that seem to be difficult
to prove. Next, we will examine the notion of generalization of Ramsey type
theorems in the sense of a given zero sum theorem in view of the new
developments.
---------------------------------------------------------------------------
Event: SFU Discrete Math Seminar
Speaker: Dr. Susan Barwick
Affiliation: University of Adelaide
Date: Tuesday March 21, 2006
Time: 3:30 - 4:20
Place: IRMACS Theatre, ASB 10900, SFU
Title: The geometry of linear perfect hash families
Abstract:
Perfect hash families were introduced in 1984 as part of compiler
design. Recently they have proved useful in a variety of applications,
including cryptography. Linear perfect hash families have a geometric
interpretation in a projective plane and so geometric techniques can be
used to study them. This talk will focus primarily on linear perfect hash
families that have a geometric representation in the classical projective
plane PG(2,q). We use some elementary plane geometry techniques to
construct optimal linear perfect hash families with small parameters.
---------------------------------------------------------------------------
Event: Joint SFU/UBC Discrete Math/CS Theory Seminar
Speaker: Kee Yuen Lam
Affiliation: University of British Columbia
Date: Tuesday March 28, 2006
Time: 3:30 - 4:20
Place: PIMS WMAX 216, UBC
Title: The combinatorics of sums of squares as studied via topology
Abstract:
Historically, the well-known identity
(x_1^2+x_2^2)(y_1^2+y_2^2 )=(x_1y_1-x_2 y_2)^2+(x_1y_2+x_2y_1)^2
had led to a sums of square problem, namely to determine all identities
of the type
(x_1^2 +..+ x_r^2 )(y_1^2 +..+ y_s^2 ) = f_1^2 +..+ f_n^2
where f1,.., fn belong to a polynomial ring Q[ x1,.., xr ; y1,., ys].
In this generality the problem remains wide open. For the case when the
commutative ring Q is Z, it reduces to a question of discrete mathematics,
involving signed intercalate matrices. In this talk I shall explain what
intercalate matrices are, and show how ideas from algebraic topology can
be used in the study of the combinatorics of such matrices.
---------------------------------------------------------------------------
Event: SFU Discrete Math Seminar
Speaker: Aidan Roy
Affiliation: University of Waterloo
Date: Tuesday April 4, 2006
Time: 3:30 - 4:20
Place: ASB 10908 (IRMACS Seminar Room), SFU
Title: Equiangular lines, mutually unbiased bases, and difference sets
Abstract:
In 1975, Delsarte, Goethals and Seidel found an upper bound
for the size of a "system of complex lines": a set of vectors whose
scalar products have only a small number of distinct absolute values.
Recently, applications in quantum computing have renewed interest in
constructing systems of maximal size. We consider two particular
problems: equiangular lines, which are sets in which only one
absolute value occurs; and mutually unbiased bases, in which two
values occur and the lines are partitioned into orthonormal bases.
For real vector spaces, these systems are closely related to regular
two-graphs and Hadamard matrices. However, the complex versions are
not nearly as well understood.
In this talk, we will see that combinatorial structures such as
difference sets and Cayley graphs can also be used for constructions
in complex case. In particular, we use difference sets in abelian
groups to produce equiangular lines, and we use relative difference
sets to produce maximal sets of mutually unbiased bases.
This talk is based on joint work with Chris Godsil.
---------------------------------------------------------------------------
Event: SFU Discrete Math Seminar
Speaker: Winfried Hochstaettler
Affiliation: University of Fern University at Hagen
Date: Tuesday May 7, 2006
Time: 3:30 - 4:20
Place: ASB 10908 (IRMACS Seminar Room), SFU
Title: Online matching on a line
Abstract:
We consider the task of matching a sequence of real numbers
(requests) to a prespecified set S of numbers.
It had been conjectured that there exists a 9-competitive
online algorithm for this problem, similar to the
so-called ``cow path'' problem. We disprove this conjecture
and show that no online algorithm can achieve a
competitive ratio strictly less than 9.001.
--------
Event: SFU Discrete Math Day at IRMACS
Date: June 22, 2006
Place: IRMACS Presentation Studio, Room 10900
Description:
The talks are each 30 minutes long.
Schedule:
9:40 Jaroslav Nesetril, Charles University,
"Local, global and tree Depth"
10:20 Fan Chung, UC San Diego,
"Random graphs with given expected degrees"
11:20 Matthew Geoffrey Parker, U of Bergen,
"Equivalence between certain mathematical Objects"
12:00 Daniel Kral, Charles U and Georgia Tech,
"Real number graph labelings"
12:30 Lunch (In the IRMACS Atrium)
2:15 Ron Graham, UC San Diego,
"Archimedes, combinatorics and the stomachion"
2:55 Maria Axenovich, Iowa State University,
"Edit distance of graphs"
3:25 Martin Klazar, Charles University,
"Non holonomic sequences"
6:00 Reception (In the IRMACS Atrium)
--------
Event: SFU Discrete Math Seminar
Speaker: Winfreid Hochstaettler
Affiliation: Fern University - Hagen, Germany
Date: Thursday June 29, 2006
Time: 2:30 - 3:20
Room: AQ 3149 (Note unusual room)
Title: On the game chromatic index of trees
Abstract:
We study the so-called game chromatic index of a tree.
We show that the game chromatic index of trees with
maximum degree D at least 6 is at most D+1.
This is joint work with Peter L. Erdos, U. Faigle, & W. Kern
--------
Event: Discrete Math Seminar
Speaker: Brian Lucena
Affiliation: American University in Cairo
Date: Tuesday July 4, 2006
Time: 3:30 - 4:20
Room: K 9509
Title: Constructions and Properties of Minimal Forbidden Minors for Treewidth
Abstract:
One consequence of the Graph Minor Theorem of Roberston and Seymour is that for
every $k$ there exists a finite obstruction set $Obs(TW\leq k)$ (the minimal
forbidden minors for having treewidth $\leq k$). These sets are known for
k=1,2 and 3 (and possibly 4), but few general properties of the graphs in these
sets are known. Moreover, other than cliques and graphs that are "nearly"
cliques, no general constructions for treewidth obstructions have been
identified. This talk will present some new such constructions. Also, I'll
discuss some work in progress on general properties of minimal forbidden minors
for treewidth.
--------
Event: Discrete Math Seminar
Speaker: Jacob Fox
Affiliation: Princeton University
Date: Tuesday August 8, 2006
Time: 3:30 - 4:20
Room: ASB 10900 (IRMACS Theatre)
Title: Ramsey-type results for intersection graphs of geometric objects
Abstract:
Suppose we have a collection of n curves in the plane.
How large a subcollection can we necessarily find such that
either every pair of curves in the subcollection intersects,
or every pair of curves in the subcollection is disjoint?
The qualitative answer is, "quite large." We will discuss how to
employ different algebraic, combinatorial, geometric, and topological
methods to tackle this problem and several variants of it.
Along the way, we will come across several old and new conjectures
in Ramsey theory.
This talk is based on joint work with Janos Pach and Csaba Toth.
--------
Event: Discrete Math Seminar
Speaker: Tamon Stephen
Affiliation: Simon Fraser University
Date: Tuesday September 26, 2006
Time: 3:30 - 4:20
Room: ASB10900 (IRMACS theatre)
Title: Colourful Simplicial Depth
Abstract:
The simplicial depth of a point p relative to a finite set S in R^d
is the number of simplices from S that contain p. This quantity is
studied in statistics since the point of maximum depth is a d-dimensional
median. By considering a colourful generalization of simplicial depth
we improve Barany's lower bound for the depth of the median of n points
in R^d, and encounter some nice geometric and algorithmic questions.
--------
Event: Graph Theory/ Theoretical CS Seminar
Speaker: Eyal Ackerman
Affiliation: Simon Fraser University
Date: Wednesday September 27, 2006
Time: 11:30 - 12:30
Room: ASB 9705
Title: On the maximum number of edges in $k$-quasi-planar graphs
Abstract:
A graph is called $k$-quasi-planar if it can be drawn in the plane such
that there are no $k$ pairwise crossing edges. It is conjectured that for
every fixed $k$ the maximum number of edges in a $k$-quasi-planar graph on
$n$ vertices is $O(n)$. We provide, for the first time, an affirmative
answer to the case $k=4$. We also give the simplest proof and the best
upper bound known, for the maximum number of edges in 3-quasi-planar
graphs on $n$ vertices. Moreover, we show a tight upper bound for
3-quasi-planar graphs in which every pair of edges meet at most once.
Joint work with Gabor Tardos.
--------
Event: Joint UBC/SFU Discrete Math Seminar
Speaker: Joachim Rosenthal
Affiliation: University of Zurich
Date: Tuesday October 17, 2006
Time: 3:30 - 4:20
Room: WMAX 110 UBC
Title: Three challenges of Claude Shannon
Abstract:
In 1948/1949 Claude Shannon wrote two papers which became the
foundation of modern information theory. The papers showed
that information can be compressed up to the `entropy', that data can be
transmitted error free at a rate below the capacity and that there exist
provable secure cryptographic systems. These were all fundamental
theoretical result. The challenge remained to build practical systems
which came close to the theoretical optimal systems predicted by Shannon.
In this overview talk we will explain how the first two challenges
concerning coding theory have resulted in practical solutions which are
very close to optimal. Then we explain why the gap between the practical
implementation of cryptographic protocols with the theoretical result of
Shannon is largest.
The talk will be tutorial in nature and should be accessible to advanced
undergraduate students.
--------
Event: Discrete Math Seminar
Speaker: Tomas Kaiser
Affiliation: University of West Bohemia, Pilsen, Czech Republic
Date: Tuesday October 17, 2006
Time: 3:30 - 4:20
Room: ASB 10900 (IRMACS Theatre)
Title: Non-intersecting perfect matchings in cubic graphs
Abstract:
The Berge-Fulkerson conjecture asserts that every bridgeless cubic
graph G admits a double cover by (six) perfect matchings. A weaker
conjecture of Fan and Raspaud asserts that G contains three perfect matchings
with empty intersection. We propose a possible approach to problems of this
type, based on what we call balanced joins in embedded graphs. We use
the technique to prove a special case of a related conjecture of
Macajova and Skoviera. This is joint work with Andre Raspaud.
--------
Event: Discrete Math Seminar
Speaker: Drabos Cvetkovic
Affiliation: University of Belgrade
Date: Tuesday October 31, 2006
Time: 3:30 - 4:20
Room: IRMACS Studio ASB 10900
Title: Signless Laplacians of finite graphs
Abstract:
For regular graphs the whole existing theory of spectra of the
adjacency matrix and of the Laplacian matrix is directly
transferred to the signless Laplacian. We consider arbitrary
graphs with special emphasis on the non-regular case. We survey
properties of spectra of signless Laplacians of graphs and discuss
possibilities for developing a spectral theory of graphs based on
this matrix. The results which we survey (old and new) are of two
types: (a) results obtained by applying to the signless Laplacian
the same reasoning as for corresponding results concerning the
adjacency matrix, (b) results obtained indirectly via line graphs.
Among other things, we present eigenvalue bounds for several graph
invariants, an interpretation of the coefficients of the
characteristic polynomial, a theorem on powers of the signless
Laplacian and applications of the star complement technique.
--------
Event: 2006 Combinatorial Potlach
Speaker: Richard Brualdi + Gary Gordon + Matt DeVos
Affiliation: U. Wisconsin at Madison + Lafayette College + Simon Fraser University
Date: Saturday November 11, 2006
Time: 3:30 - 4:20
Room: Portland State University, Cramer Hall, Room 171
Title: TBA
Abstract:
TBA
--------
Event: Discrete Math Seminar
Speaker: Kevin Purbhoo
Affiliation: University of British Columbia
Date: Tuesday November 21, 2006
Time: 3:30 - 4:20
Room: IRMACS Studio ASB 10900
Title: Puzzles, Tableaux, and Mosaics
Abstract:
The Littlewood-Richardson numbers show up in a number of different
areas of mathematics. They are structure constants of the ring of
symmetric functions, which connects them to representation
theory and cohomology of Grassmannians. There are now several
well known combinatorial rules for computing Littlewood-Richardson
numbers. I will talk about two of the main ones: the original rule
of Littlewood and Richardson, which is phrased in terms of tableaux,
and the Knutson-Tao ``puzzle rule'', which looks very different. Most
every other known rule is just a variant on one or the other. Yet it is
not immediately obvious why these two are rules are the same, or why
they are correct. I will give a new construction---mosaics---which
interpolates between puzzles and tableaux. Then a miracle will
occur: just using the fact that one can interpolate between them, a
new and pleasant proof of correctness (for both rules) will appear
out of thin air.
--------
Event: Joint UBC/SFU Discrete Math Seminar
Speaker: John Gimbel
Affiliation: University of Alaska
Date: Tuesday December 7, 2006
Time: 3:30 - 4:20
Room: WMAX 110 UBC
Title: Remarks on split graphs and related notions.
Abstract:
A graph is split if its vertices can be covered by two sets A and B where
A induces a complete graph and B induces an empty graph. This concept has
many related notions. For example, the number of non-isomorphic set
covers of a set of order n is the number of non-isomorphic split graphs of
order n. We consider split graphs and three extensions: cochromatic
number, split chromatic number and (j,k)-colorings. The cochromatic
number of a graph is the minimum number of colors necessary to color the
vertices so that each color class induces a complete or empty graph. The
split chromatic number is the minimum number of colors used to color the
vertices so that each color class induces a split graph. We focus our
attention on (j,k)-colorings. A (j,k)-coloring of a graph is a covering
of the vertex set using j+k parts where j parts induce complete graphs and
k parts induce empty graphs. We consider a simple extremal problem: given
j and k, what is the largest n so that every n-graph has a (j,k)-coloring.
We also consider some results on computational complexity.
--------
Event: Discrete Math Seminar
Speaker: Moshe Rosenfeld
Affiliation: University of Washington, Tacoma
Date: Tuesday December 12, 2006
Time: 2:30 - 3:20
Room: IRMACS Studio ASB 10900
Title: Spanning Graph Designs, an extension of the "Graph disease"
Abstract:
A graph G of order n decomposes K_n if the edges of K_n an be decomposed
into edge-disjoint copies of G. Kotzig-Ringel's conjecture that any given
tree of order 2n+1 decomposes K_{2n+1}, referred to by Kotzig as the
"graph disease" is probably the most celebrated spanning graph design
problem.
In this talk I'll focus on cubic graph designs and graph designs
originated from equi-angular lines. I'll present methods for constructing
cubic graph designs using graceful labellings and related methods. A bunch
of open problems will be served for desert, so bring a healthy appetite.
Part of this work is being done with L. Stacho, H. Ardal and J. Manuch
(SFU) and another part jointly with Vu Dinh Hoa (Hanoi University of
Education).
--------
Event: Discrete Math Seminar
Speaker: John Irving
Affiliation: St. Mary's University, Halifax
Date: Tuesday December 12, 2006
Time: 3:30 - 4:20
Room: IRMACS Studio ASB 10900
Title: Counting Transitive Factorizations in the Symmetric Group
Abstract:
Transitive factorizations in the symmetric group have
recently become objects of intense interest because of their connections
with algebraic geometry. We shall briefly discuss these geometric
connections, but our view of permutation factorization will be purely
combinatorial. In particular, we will show how a simple graphical
model can be exploited to count various classes of transitive
factorizations.
--------
Event: Discrete Math Seminar
Speaker: Azhvan Sheikh-Ahmady
Affiliation: SFU
Date: Tuesday January 30, 2007
Time: 3:30 - 4:20
Room: IRMACS Studio ASB 10900
Title: Eigenvalues of Cayley graphs and group characters.
Abstract:
There are a few classes of graphs which admit a simple method to
compute their eignevalues. Cayley graphs form one such class.
Cayley graphs are highly symmetrical, and fortunately there
is a straightforward formula for their eigenvalues. This formula,
as given by L. Babai, depends on irreducible characters of the
group underlying the Cayley graph. The problem of computing eigenvalues
of transitive graphs can be reduced to finding eigenvalues of Cayley
graphs. Therefore also we have a method for determining the spectra
of transitive graphs.
--------
Event: Discrete Math Seminar
Speaker: Cedric Chauvre
Affiliation: Simon Fraser University
Date: Tuesday February 6, 2007
Time: 3:30 - 4:20
Room: IRMACS Studio ASB 10900
Title: Inferring ancestral genomes with common intervals
Abstract:
The problem we address in this talk is the following: given the gene orders
of several species ands a phylogenetic tree relating these species, can we
construct possible ancestral genomes (for example, if we have the genomes of
the mouse and the rat, what can we say on the structure of the genome of the
ancestral rodent). This problem received a lot of attention following the
work of the group Pavel Pevzner (UCSD), that uses an evolution model based
on reversals and translocations and a parsimony framework. Here we discuss
another approach that does not rely on an evolution model but on combining
the genome segments that are conserved in several species to infer possible
ansestral genome segments.
We will present a method based on the notion of conserved intervals
(published in WABI 2004, in collaboration with Anne Bergeron, Mathieu
Blanchette and Annie Chateau), and the combinatorial and algorithmical
problems related to using better notions of conserved structures (work in
progress with Annie Chateau).
--------
Event: Discrete Math Seminar
Speaker: Neil Roberson
Affiliation: Ohio State University
Date: Tuesday February 20, 2007
Time: 3:30 - 4:20
Room: IRMACS Studio ASB 10900
Title: CANCELLED
-----------
Event: Eighth Combinatorics Conference
Date: Tuesday February 24 - 25, 2007
Time: 9:30 - 5:20
Room: ECS Room 116, U. of Victoria
URL: http://pims.math.ca/science/2007/07ccc/index.html
Schedule:
Saturday
9:30 am Rick Brewster (Thompson Rivers University): Solution to the restricted homomorphism conjecture
10:05 am Laura Yang (University of Alberta): Postnikov's Identity and its Generalizations
10:40 am Aaron Williams (UVic): Generating multi-set permutations in a cool way
11:15 am Luis Goddyn (SFU): Vanishing Bases in Projective Geometries
1:30 pm Wendy Myrvold (UVic): Ally and Adversary Reconstruction Numbers
2:05 pm Tom Brown (SFU): On colorings of the factors of a word
2:40 pm Gara Pruesse (Malaspina): A new proof for Knuth's old sum
3:30 pm Moshe Rosenfeld (U. Washington): Famous and lesser known problems in "elementary" combinatorial geometry
4:30 pm Mohammad Ghebleh (SFU): Computing the circular chromatic number
Sunday
9:30 am Joe Peters (SFU): Constructing Incremental Sequences in Graphs
10:05 am Frank Ruskey (UVic): Hamming distance from an irreducible polynomial
10:40 am Art Finbow (St. Mary's): Remarks on Well-Covered Graphs of Girth 4
11:15 am Petr Lisonek (SFU): Planar Eulerian triangulations are equivalent to spherical latin bitrades
1:30 pm Mark Weston (UVic): Symmetries of Venn Diagrams Embedded on the Sphere
2:05 pm Brett Stevens (Carleton): Locating and avoiding errors in software testing
2:40 pm Stephen Finbow (StFX): Open-Open Irredundance
3:15 pm Gary MacGillivray (UVic): Fractional maximal independent sets in graphs
-----------
Event: Discrete Math Seminar
Speaker: Gena Hahn
Affiliation: Universite de Montreal
Date: Tuesday February 27, 2007
Time: 3:30 - 4:20
Room: IRMACS Studio ASB 10900
Title: CANCELLED
-----------
A name="2007.03.06">
Event: Discrete Math Seminar
Speaker: Francois Bergeron
Affiliation: Universite du Quebec a Montreal
Date: Tuesday March 6, 2007
Time: 3:30 - 4:20
Room: IRMACS Studio ASB 10900
Title: A combinatorial classification of polynomials
Abstract:
The purpose of this talk is to present a new combinatorial
classification of curves obtained as zeros of the real part
of degree n polynomials over the complex field.
A resulting decomposition of the space of polynomials is given
in terms of maps consisting of forests of non intersecting
special trees, and many ties are established between properties
of the polynomials and those of the associated maps. If time
allows we will go over the study of underlying symmetries
and ties with statistical mechanics.
-----------
A name="2007.03.13">
Event: Discrete Math Seminar
Speaker: Mike Zabrocki
Affiliation: York University
Date: Tuesday March 13, 2007
Time: 3:30 - 4:20
Room: IRMACS Studio ASB 10900
Title: A Zoo of Hopf algebras
Abstract:
If we start with a combinatorial object such as partitions,
permutations, graphs, or non-crossing partitions and impose
Hopf algebra structure the resulting algebra is essentially unique.
We will examine questions that interest researchers in this area of
mathematics and look at how the Hopf algebra of set partitions
(or symmetric functions in non-commuting variables) fits into this
picture.
-----------
A name="2007.03.20">
Event: Discrete Math Seminar
Speaker: Robert Samal
Affiliation: York University
Date: Tuesday March 20, 2007
Time: 3:30 - 4:20
Room: IRMACS Studio ASB 10900
Title: On XY mappings
Abstract:
I will speak about four (rather new) types of mappings between graphs.
These mappings have plenty of connections with graph homomorphisms,
with flows on graphs, and with cycle covers.
To be more concrete: If G, H are graphs, a mapping from E(G) to E(H) is called
_cut-continuous_ (or TT for short) if the preimage of every cut in H is
a cut in G. Analogically we define _flow-continuous_ (FF) mappings,
and FT mappings.
Now
* FT mappings correspond precisely to double-covers by cycles,
* TT mappings correspond roughly to homomorphisms, and
* FF mappings provide an open problem that would imply much of the unsolved
problems in the area.
-----------
Event: Discrete Math Seminar
Speaker: A. Vijayakumar
Affiliation: Cochin University of Science and Technology
Date: Tuesday May 15, 2007
Time: 3:30 - 4:20
Room: IRMACS Studio ASB 10900
Title: Graph operators and co-graphs: some recent trends
Abstract:
In this talk we consider the four graph operators- Median, Antimedian,
Gallai and Antigallai. After mentioning some general properties of these
operators, we shall discuss its action on cographs, graphs which are
essentially P4-free. We shall also discuss some results on the graph
parameters such as the chromatic number,the radius and the diameter. This
is a joint work with S.B.Rao (Indian Statistical Institute, Kolkata) and
Aparna Lakshmanan S.
------------------
Event: Special Discrete Math Seminar
Speaker: Andre Raspaud
Affiliation: LaBRI, Universite Bordeaux I
Date: Friday May 18, 2007
Time: 1:30 - 2:20
Room: IRMACS Studio ASB 10900
Title: Injective colourings of graphs
Abstract:
For a graph G = (V(G), E(G)), a vertex k-colouring is a mapping from V(G)
into {0,1, ... , k-1}. We say that a colouring of a graph is injective
if its restriction to the neighbourhood of any vertex is injective.
The injective chromatic number of a graph G is the least k such that
there is an injective k-colouring.
In this talk I will give a survey of the old and new results concerning injective
colourings. I will also focus on recent results concerning sparse graphs.
------------------
Event: Discrete Math Seminar
Speaker: Jonathan Jedwab
Affiliation: Simon Fraser University
Date: Tuesday May 22, 2007
Time: 3:30 - 4:20
Room: IRMACS Studio ASB 10900
Title: Golay complementary sequences: a multi-dimensional approach
Abstract:
Golay complementary sequences have been used since the 1950s in diverse
areas of digital information processing, including multislit spectrometry,
optical time domain reflectometry, and power control for multicarrier
wireless transmission. In 1999 Jim Davis and I demonstrated an unexpected
connection with the classical Reed-Muller codes, which accounted for all known
Golay sequences of length 2^m over binary, quaternary, and higher-order alphabets.
But in 2005 Li and Chu discovered an additional 1024 length 16 Golay
quaternary sequences. I shall explain how these additional sequences arise,
and describe a new approach to the construction and enumeration of Golay sequences
in which Golay sequences are viewed as projections of a multi-dimensional Golay array.
This simplifies previous approaches, by separating the construction of Golay arrays
from the enumeration of all possible projections of these arrays to lower dimensions.
It accounts, in particular, for all quaternary Golay sequences spawned by Li and
Chu's examples.
The talk will not assume any prior knowledge.
(Joint work with Frank Fiedler and Matthew Parker)
--------------
Event: Joint CS Theory / Discrete Math Seminar
Speaker: Janos Pach
Affiliation: City College, New York and R\'enyi Institute, Budapest
Date: Thursday May 24, 2007
Time: 11:30 - 12:20
Room: IRMACS Studio ASB 10900
Title: Decomposition of multiple coverings
Abstract:
A family $\cal C$ of convex bodies form a $k$-fold covering of a
region $R$ if every point of $R$ is contained in at least $k$
members of $\cal C$. It is known that for each centrally symmetric
convex polygon $P$, there is a constant $k=k(P)$ such that any
$k$-fold covering of the plane with translates of $P$ can be
decomposed into {\em two} coverings. Does the same theorem remain
true for (a) unit circles in the place of polygons, (b) circles of
arbitrary radii, (c) unit balls in higher dimensions? We survey
some old and new results of this type.
The case when $\cal C$ consists of axis-parallel rectangles will
be discussed in more detail. We construct, for every $k$, a
$k$-fold covering ${\cal C}_k$ of the plane (or of a large square)
with rectangles whose sides are parallel to the coordinate-axes,
such that ${\cal C}_k$ cannot be split into two coverings
(P.-Tardos-T\'oth). We also present, for every $k$ and $c$, a
probabilistic construction of a $k$-fold covering ${\cal C}_{k,c}$
of the plane with axis-parallel rectangles such that no matter how
we color these rectangles with $c$ colors, we find a point that is
covered only by rectangles of the same color (P.-Tardos). The
``dual" statement is also true: With probability tending to one, a
sufficiently large point set, randomly and uniformly selected from
the unit square, has the property that no matter how we color its
elements by $c$ colors, there is an axis-parallel rectangle
containing precisely $k$ points, all of which have the same color
(Chen-P.-Szegedy-Tardos).
-----------
Event: PIMS 10th Anniversery Distinguished Lecture
Speaker: Herbert Wilf
Affiliation: University of Pennsylvania
Date: Friday May 25, 2007
Time: 2:30 - 3:20
Room: IRMACS Studio ASB 10900
Title: Mathematics: An experimental Science
Abstract:
We'll discuss some recent results that were conjectured via computer
experiments and then proved. The examples will be drawn from number
theory, Young tableaux, hypergeometric determinant evaluation, theory
of matrices of 0s and 1s, etc. Several unsolved probelms that also
resulted from these studies will be presented.
-----------
Event: PIMS 10th Anniversery Distinguished Lecture
Speaker: Paul Seymour
Affiliation: Princeton University
Date: Friday Aug 31, 2007
Time: 2:30 - 3:20
Room: Room 1430 SFU Harbour Centre
Title: Structure Theorems in Graph Theory
Abstract:
Fix a graph H. What is the most general graph that does not contain H?
In other words, how do we explicitly construct all the graphs that do
not contain H?
To begin to make this precise, we have to say what "contain" means;
we have in mind either minor containment, or induced subgraph containment.
But what do we mean by an "explicit construction" of a class of graphs?
We give some examples, and describe some connections and differences
between the two containment relations, and discuss several open questions
in the area. There will be no detailed proofs, and very little knowledge
of graph theory will be assumed.
--------
Event: Discrete Math Seminar
Speaker: Mark Siggers
Affilitation: Simon Fraser University
Date: Tuesday September 25, 2007
Time: 2:30 - 3:20
Room: Pims Seminar Room - TASC2 8500, SFU
Title: Integer packings of hypergraphs through fractional packings.
Abstract
Given graphs G and H, an integer H packing of G is a decomposition
of the edges of G into copies of H. Finding the weight of a maximum
such packing, for most fixed H, is NP-hard. Extending results of
Rodl, Haxell, and Nagle, and Yuster, we use the fractional relaxation
of the problem, along with a hypergraph version of the Szemeredi
regularity lemma to get a polynomial time approximation for the
weight of the maximum packing.
In our presentation, we restrict mostly to the graph case, but
describe how our proof allows us to overcomes some of the issues
in extending to hypergraphs, that earlier proofs of the graph case
could not overcome.
This is joint work with Rodl, Schacht and Tokushige.
--------
Event: Coast To Coast Seminar - Live From IRMACS
Speaker: Dr. Luis Goddyn
Affiliation: Simon Fraser Universtiy
Date: Tuesday, September 25, 2007
Time: 11:30-12:20
Room: IRMACS Presentation Studio, ASB 10900
Title: Spectra of (3,6)-Fullerenes
Abstract:
A (3,6)-Fullerene is a 3-regular planar graph whose faces
are triangles and hexagons. Being variants of Buckyballs, these graphs
are of interest to chemists. It was conjectured (P. Fowler, 1995) that
the spectrum of any (3,6)-Fullerene consists of opposite real pairs
{ \pm \lambda }, and four (unpaired) exceptional eigenvalues { 3, -1, -1, -1 }.
We prove this conjecture (and more) by expressing every (3,6)-Fullerene
as a Cayley Sum Graph, a variant of Cayley Graph which was introduced by
Ben Green in 2003.
This is joint work with Matt DeVos, Robert Samal, and Bojan Mohar.
---------------------------------
Event: 2007 Combinatorial Potlach
Speaker: Manley Perkel + John Moon + Anthony Quas
Affiliation: U. Puget Sound + U of Alberta + U of Victoria
Date: Saturday September 29, 2007
Time: 11:00am - 4:30pm
Room: University of Victoria, Engineering and Computing Science
Title:
Antibandwidth and Cyclic Antibandwidth of Kneser Graphs +
On the Number of Proper Nodes in Rooted Trees +
Distances in Positive Density Sets
Abstract: See website
--------
Event: Discrete Math Seminar
Date: Tuesday October 2, 2007
Time: 2:30 - 3:20
Room: PIMS seminar room, TASC2 8500, SFU
Speaker: Robert Samal
Affiliation: Simon Fraer University
Title: Trading Handles for Crossings
Abstract:
Let cr_n(G) be the minimum number of crossings when G is drawn on S_n
(the orientable surface of genus n). Archdeacon, Bonnington, and Siran
conjecture that any strictly decreasing sequence (ending with zeros)
is (cr_n(G))_n for some graph G.
We confirm this for all sequences (a, b, 0). That is, we show that
for all integers a > b there is a graph G with cr_0(G) = a,
cr_1(G) = b, such that G embeds on the double torus.
This is joint work with Matt DeVos, Bojan Mohar.
-----------
Event: Discrete Math Seminar
Speaker: Blair D Sullivan
Affiliation: Princeton University
Date: Tuesday October 9, 2007
Time: 2:30 - 3:20
Room: PIMS seminar room, TASC2 8500, SFU
Title: Feedback Arc Sets in Circular Interval Digraphs
Abstract:
Given a directed graph G with girth at least m+1 (and no parallel edges),
let \beta(G) denote the size of the smallest subset X of E(G) so that
G\X has no directed cycles, and let \gamma(G) be the number of non-edges in G
(unordered vertex pairs joined by no edge).
Prior joint work with Maria Chudnovsky and Paul Seymour showed that when m=3,
\beta(G) \leq \gamma(G), and we conjectured 2 \beta(G) \leq \gamma(G).
Can one say anything stronger if m>3? In this talk, I will discuss
a new conjecture giving a ratio between \beta(G) and \gamma(G),
namely (m^2-m-1) \beta(G) \leq 2 \gamma(G), for m>2.
The talk will also cover two new results in this direction:
the bound 3 \beta(G) \leq \gamma(G) when m=4, and for circular interval graphs,
a generalization of previous methods which gives a new bound for all m.
-----------
Event: Discrete Math Seminar
Speaker: Gabor Kun
Affiliation: SFU
Date: Tuesday October 23, 2007
Time: 2:30 - 3:20
Room: PIMS seminar room, TASC2 8500, SFU
Title: An asymptotic version of the Bollobas-Catlin-Eldridge conjecture
Abstract: We say that two graphs G and H pack if G and H can be mapped
into the same vertex set such that the image of edge sets do not intersect.
Bollobas and Eldridge, and independently Catlin conjectured that if
the graphs G and H on n vertices with maximum degree M(G) and M(H),
respectively satisfy (M(G)+1)(M(H)+1) <= n+1 then G and H pack.
We prove that for every epsilon>0 if M(G) and M(H) are large enough
(depending on epsilon) and M(G)M(H)(1+epsilon) < n holds then G and H
pack.
-----------
Event: Discrete Math Seminar
Speaker: Matthias Koeppe
Affiliation: U. Magdeburg, Germany
Date: Tuesday October 30, 2007
Time: 2:30 - 3:20
Room: PIMS seminar room, TASC2 8500, SFU
Title: Topic: Ehrhart polynomials of matroid polytopes
Abstract:
We show the polynomial-time computability of Ehrhart polynomials for
matroid polytopes, matroid base polytopes, and polymatroids, whenever
the rank function is bounded by an arbitrary constant.
This result complements other complexity results, like the
polynomial-time computability of the highest k (fixed) coefficients of
the Ehrhart (quasi-)polynomials of rational simplices in varying
dimension (Barvinok 2005).
The proof relies on the following new techniques:
1. a polynomial-time construction of a triangulation of the vertex
cones of the polytopes into half-open simplicial unimodular cones
2. a technique to turn a triangulation into an exact partition of
half-open cones
3. a polynomial-time specialization algorithm of multivariate rational
generating functions in varying dimension
Based on unpublished joint work with Jesus De Loera and David Haws
and my paper arXiv:0705.3651 [math.CO] (with Sven Verdoolaege).
-----------
Event: Discrete Math Seminar
Speaker: Eric Fusy
Affiliation: SFU
Date: Tuesday November 6, 2007
Time: 2:30 - 3:20
Room: PIMS seminar room, TASC2 8500, SFU
Title: Transversal structures on triangulations: combinatorial study and algorithmic applications
Abstract:
We study the combinatorial properties and algorithmic
of planar maps (planar graphs embedded in the plane).
The techniques are illustrated on a particular family,
namely plane triangulations with no separating triangle
(called irreducible). These triangulations can be endowed
with specific edge bicolorations, called transversal
structures, which makes it possible to count the triangulations
bijectively, generate them at random, encode them and
draw them on a grid. Simulations indicate that the grid
used by the drawing has with high probability a size close
to 11n/27 * 11n/27, where n is the number of vertices.
As we will see, this can be proved rigorously using tools
from bijective combinatorics as well as analytic combinatorics.
----------
Event: Discrete Math Seminar
Speaker: Vladmir Korzhik
Affiliation: National University of Chernivtsi, Ukraine
Date: Tuesday November 13, 2007
Time: 2:30 - 3:20
Room: PIMS seminar room, TASC2 8500, SFU
Title: Some open problems on the set of triangular embeddings of a complete graph
Abstract:
The set of triangular embeddings of a complete graph $K_n$
in a surface is a complicated class of combinatorial objects,
the number of which dramatically increases with $n$.
We consider some open problems on the set. The problems are
of general mathematical interest and pertain to many combinatorial
designs (Steiner triple systems, Latin squares, etc.)
----------
Event: Discrete Math Seminar
Speaker: Frederic Giroire
Affiliation: Intel Research
Date: Tuesday November 27, 2007
Time: 2:30 - 3:20
Room: PIMS seminar room, TASC2 8500, SFU
Title: Probabilistic algorithms to compute the cardinality of very large datasets
Abstract:
The cardinality of a multiset is the number of distinct elements, and the size is the
total number of elements. An important issue in computer science is to estimate the
cardinality of a multiset having a very large size. This problem aroze in the 1980's,
motivated by optimisation of classical algorithmic operations on data bases
(union, intersection, sorting,...). As the data sets to be measured have a size
typically far larger than the RAM capacities, a natural requirement is to treat
the data in one pass using a simple loop, and with a small auxiliary memory
(constant or logarithmic in the size). An elegant class of probabilistic algorithms
has been developed to solve this problem. The crucial point, first developed by
Flajolet and Martin (1983) in their algorithm Probabilistic Counting,
is to relax the contraint of giving the exact number of distinct values in the
multiset and to build only a probabilistic estimate of the cardinality.
I will explain some algorithms of this class. This simple statistic has a
surprisingly large number of applications and I will present applications in
the field of network monitoring and network security and in bioinformatics.
-----------
Event: Discrete Math Seminar
Speaker: Maia Fraser
Affiliation: University of Colima, Mexico
Date: Tuesday January 15, 2008
Time: 3:30 - 4:20
Room: K9509, SFU
Title: Local Routing in Graphs Embedded on Orientable Surfaces"
Abstract:
The problem of local route discovery in geometric graphs has
important applications in adhoc networks, where the nodes know their
geometric location but operate autonomously. In such networks, usually
no accurate, global map exists and there are strong limitations on how
much memory routing agents can carry. For 2D geometric graphs, many
algorithms exist and all correct ones are based at least in part on Face
Routing, proposed by Kranakis et al in 1999. 3D geometric graphs which
are "relatively flat" are traditionally approximated by 2D graphs (after
projection to a plane) and handled by existing methods. The requirement
of relative flatness has recently been shown (by Durocher et al) to be
necessary, implying no general local routing algorithm exists for 3D graphs.
Thus more information is needed to achieve local geometric routing there.
We show that if the graph is embedded on a known surface, then local
routing is possible.
-----------
Event: Discrete Math Seminar
Speaker: Gabor Kun
Affiliation: Eotvos University, Hungary
Date: Tuesday February 25, 2008
Time: 3:30 - 4:20
Room: K9509, SFU
Title: Cops and robbers in random graphs
Abstract:
We will study the following game known as cops and robbers.
There is a finite, connected, undirected graph $G$, and $m$ cops and one robber.
At the start, each cop chooses one vertex, and then the robber makes his
choice of a vertex. Then they move alternately (first the cops then the robber).
In the cops' turn, each cop may move to an adjacent vertex, or remain where he is,
and similarly for the robber. The cops win the game if
one of the cops catches the robber, i.e. lands on the same vertex.
We denote by $c(G)$ the `cop-number' of $G$, meaning the minimal $m$ such
that $m$ cops have a winning strategy in $G$, and by $c(n)$ the maximum of
$c(G)$ over all graphs with $n$ vertices. Maamoun and Meyniel determined
the cop-number for grids. Aigner and Fromme proved that in the case of
planar graphs three cops can catch the robber. Frankl gave lower bounds on
$c(G)$ in the case of large girth graphs. Meyniel conjectured that
$c(n)=O(\sqrt{n})$. Our main aim is to prove that the conjecture
essentially holds for sparse random graphs: in this case the cop-number
has order of magnitude $\Omega(n^{1/2+o(1)})$. Joint work with Bela Bollobas
and Imre Leader.
-----------
Event: Discrete Math Seminar
Speaker: Luis Goddyn
Affiliation: Simon Fraser University
Date: Tuesday March 4, 2008
Time: 3:30 - 4:20
Room: K9509, SFU
Title: How bad can a Euclidean Traveling Salesman Problem be?
Abstract:
Let R be a fixed region of unit volume in Eucliedan d-space.
The TSP-length L(X) of a finite subset X of R is the
least length among all closed curves containing X.
We investigate the "worst case" TSP-length:
L(n) = sup { L(X) : X \subset R, |X|=n }.
For large n,
L(n) ~ \alpha_d n^{1-1/d}.
Here \alpha_d is a fundamental invariant of Euclidean
d-space which is very challenging to estimate.
For example, in the plane we only know
1.07 < \alpha_2 < 1.39.
I describe some rather old work of mine, determining
upper and lower bounds on \alpha_d. My bounds are still
the best known after 20 years!
Techniques involve sphere packings, geometric quantizers and
the analysis of TSP heuristic algorithms.
-----------
Event: Discrete Math Seminar
Speaker: Penny Haxell
Affiliation: University of Waterloo
Date: Tuesday March 11, 2008
Time: 3:30 - 4:20
Room: PIMS seminar room, TASC2 8500, SFU
Title: More on Sperner's Lemma
Abstract:
In this very informal seminar I will explain some old applications of
Sperner's Lemma (independent transversals, hypergraph matchings, etc.)
and make some other observations for (possibly) more general settings.
-----------
Event: Discrete Math Seminar
Speaker: Agelos Georgakopoulos
Affiliation: University of Hamburg
Date: Tuesday March 18, 2008
Time: 3:30 - 4:20
Room: K9509, SFU
Title: Infinite cycles in graphs
Abstract:
Many attempts to generalise theorems about cycles in finite graphs to
infinite graphs had failed, until recently Diestel and Kuhn proposed a
new notion of infinite cycle; this notion has an elegant topological
definition that allows a cycle to go to infinity and come back.
This approach has turned out to be very successful, leading to
generalisations of well known theorems to infinite graphs, but also
to interesting new problems. I'm going to introduce the new concepts
and present some results and problems.
-----------
Event: Discrete Math Seminar
Speaker: Marni Mishna
Affiliation: Simon Fraser University
Date: Tuesday March 25, 2008
Time: 3:30 - 4:20
Room: K9509, SFU
Title: Decomposition and Enumeration of Planar Graphs, Part I: Combinatorial Warm Up
Abstract:
The first part of this pair of talks is an expository summary recalling motivations
and analytic techniques for combinatorial decomposition and enumeration.
I will describe some decompositions for some families of graphs and how to use
generating functions for asymptotic enumeration and random generation.
The second part of this talk continues next week, by Eric Fusy.
Both talks are intended to be accessible to a wide combinatorial audience.
Graduate students are encouraged to attend.
-----------
Event: Discrete Math Seminar
Speaker: Eric Fusy
Affiliation: Simon Fraser University
Date: Tuesday April 1, 2008
Time: 3:30 - 4:20
Room: K9509 - SFU
Title: Decomposition and Enumeration of Planar Graphs, Part II
Abstract:
We describe a very precise decomposition of planar graphs, and all of the fruits
of such a description.
-----------
Event: Discrete Math Seminar
Speaker: Laura Chavez
Affiliation: Simon Fraser University
Date: Tuesday April 08, 2008
Time: 3:00 - 3:50
Room: K9509 - SFU
Title: Flow and chromatic numbers for matroids
Abstract:
This talk will give an overview of the results in my PhD thesis.
Taking circular flow and circular chromatic numbers for graphs as
a starting point, we will explore flow- and chromatic number-like
parameters for matroids. We consider extensions based on orientations
and linear algebra to two matroid classes:
1. Orientable matroids: following work of Goddyn, Hlineny and Hochstattler.
2. Sixth root of unity matroids: a class of matroids representable over
the complex numbers by matrices with properties similar to those of totally
unimodular matrices.
We will introduce these parameters, pose some general questions and present some results.
-----------
Event: Discrete Math Seminar
Speaker: Derek Bingham
Affiliation: Simon Fraser University
Date: Tuesday April 15, 2008
Time: 3:30 - 4:20
Room: K9509 - SFU
Title: Defining contrast subspaces and the randomization structure of factorial designs
Abstract:
Two-level factorial and fractional factorial designs have played a
prominent role in the statistical design and analysis of experiments.
It is often impossible to perform the trials of a factorial design
(or, fractional factorial design) in a completely random order.
Instead, restrictions are imposed on the randomization of experimental
runs. In recent years, considerable attention has been devoted to
factorial and fractional factorial plans with different randomization
restrictions (e.g., nested designs, split-plot designs,
split-split-plot designs, strip-plot designs, split-lot designs, and
combinations thereof). Our work introduces a general representation
referred to as a randomization defining contrast subspace (RDCSS). The
RDCSS is a projective geometric representation of the randomization
structure of a design. Here, the theoretical results are developed
for the existence of factorial designs with randomization restrictions
using (t-1)-spreads and partial (t-1)-spreads of PG(p-1, 2). The
theory developed offers a systematic approach for the construction of
two-level full factorial designs and regular fractional factorial
designs with randomization restrictions. The problems are motivated
by a plutonium processing experiment that was performed at Los Alamos
National Lab. This is joint work with P. Ranjan (Acadia U.) and A.
Dean (Ohio State U.).
-----------
Event: Discrete Math Seminar
Speaker: Sean McGuinness
Affiliation: Thomson Rivers Unviversity
Date: Tuesday April 29, 2008
Time: 3:30 - 4:20
Room: K9509 - SFU
Title: Perfect Path Double Covers, Matroids, A Theorem of Fan, ... And A Problem of Goddyn
Abstract.
In this talk, I will discuss how a recent result for matroids leads us to some interesting
known and unknown conjectures for graphs. For example, the (solved) Perfect Path Double
Cover conjecture, a conjecture of Hajos, and ... a problem of Goddyn.
-----------
Event: Discrete Math Seminar
Speaker: Bojan Mohar
Affiliation: Simon Fraser University
Date: Tuesday May 06, 2008
Time: 3:30 - 4:20
Room: K9509 - SFU
Title: On the sum of k largest eigenvalues of graphs and symmetric matrices
Abstract:
Let $k$ be a positive integer and let $G$ be a graph of order $n\ge k$.
It is proved that the sum of $k$ largest eigenvalues of $G$ is at most
$(\sqrt{k} + 1)n/2$. This bound is shown to be best possible
in the sense that for every $k$ there exist graphs whose sum is
$(\sqrt{k} + 1/2)n/2 - o(k^{-2/5})n$.
A generalization to arbitrary symmetric matrices is given.
-----------
Event: Discrete Math Seminar
Speaker: Simon Spacapan
Affiliation: Simon Fraser Universtiy
Date: Tuesday May 20, 2008
Time: 3:30 - 4:20
Room: K9509 - SFU
Title: The Acyclic, the Star, and the Degenerate Chromatic Numbers
Abstract:
In this talk we discuss the acyclic, the star and the degenerate chromatic
number of a graph. We give a short history of results in the area. Then we
sketch a proof that the degenerate chromatic number of a planar graph
is at most nine (this is a joint work with B. Mohar).
-----------
Event: Discrete Math Seminar
Speaker: Windfried Hochstaettler
Affiliation: University of Hagen, Germany
Date: Tuesday July 22, 2008
Time: 3:30 - 4:20
Room: K9509 - SFU
Title: Flows in Oriented Matroids and a Chromatic Number
Abstract:
Recently, two competing definitions for a chromatic number or, dually,
a flow number of an oriented matroid have been proposed. The oriented
chromatic number of Goddyn, Hlineny and Hochstaettler is a
generalization of the circular chromatic number and, thus, in general
not an integer. Moreover, it is not a matroid invariant. The latter is
open for the chromatic number of Hochstaettler and Nesetril,
which is always integer and will be the topic of this talk.
For us a flow is an integer combination of signed characteristic
vectors of directed circuits. Thus, the flows form an integer
lattice. The flow number is the smallest integer k such that there
exists a nowhere-zero-k flow in that lattice, i.e. a vector without
zeroes the entries of which are bounded by -k+1 and k-1.
In this lecture we present several structural results concerning the
flow resp. chromatic number of an oriented matroid. In particular we
give a complete characterization of the flow lattice of rank 3
oriented matroids and numerical results for the corank 3
case. Moreover, we show that if the rank r of the oriented matroid is
at least 3, then the chromatic number is bounded by r+1, where
equality is achieved only if the oriented matroid is the complete
graph on r+1 vertices.
(This is joint work with Robert Nickel.)
-----------
Event: Discrete Math / Network Modelling Seminar
Speaker: David Coudert
Affiliation: Charge de Recherche INRIA, University of Nice Sophia
Host: Joseph Peters
Date: Tuesday August 19, 2008
Time: 3:30 - 4:20
Room: TASC 9204 East - SFU (Note unusual time and place)
Title: Survivability and Routing in Oriented Networks
Abstract:
This presentation addresses two issues regarding oriented networks
such as DM optical networks:
(1) survivability under multiple failure scenarios and
(2) routing reconfiguration.
(1) Shared Risk Resource Group (SRRG)
SRRG has been introduced in order to capture network survivability
issues where a failure may break a whole set of resources, and has
been formalized as colored graphs, where a set of resources is
represented by a set of edges with same color.
We present here the analogous of classical problems such as determining
paths or cuts with the minimum numbers of colors or color-disjoint paths.
These optimization problems are much more difficult than their counterparts
in classical graph theory. In particular standard relationships such as
the Max Flow - Min Cut equality no longer hold.
In this talk I present cases where these problems are polynomial,
for example when the edges of a given color form a connected subgraph,
and otherwise give hardness and non approximability results for these problems.
(2) Routing Reconfiguration and Process Number
The process number is the number of requests that have to be simultaneously
disturbed during a routing reconfiguration phase of a connection oriented
network. Here, a reconfiguration phase consists in switching connections
(lightpath) one by one from current routing to a predetermined routing.
From a graph theory point of view, it can be formulated as a particular
cops and robber game similar to the node search number, and thus to the
pathwidth. However they are not always equal in general graphs.
Determining these parameters is, in general, NP-complete. In this talk,
I will present cases where the process number can be determined in
polynomial time in both directed and undirected graphs.
-------------------------------------------
Event: Discrete Math Seminar
Speaker: Juanjo Ru\'e
Affiliation: Politechnical University of Catalonia, Spain
Date: Tuesday September 23, 2008
Time: 3:30 - 4:20
Room: K9509, SFU
Title: On a question of S\'arkozy and S\'os on bilinear forms
Abstract:
This talk deals with a problem on combinatorial number theory.
More concretely, we prove that if $2 \leq k_1 \leq k_2$,
then there is no infinite sequence $\mathcal{A}$ of positive integers
such that the representation function
$r(n) = #\{(a, a') : n = k_1 a + k_ 2a': a, a' \in \mathcal{A}\}$
is constant for $n$ large enough.
This result completes previous work of Dirac and Moser
for the special case $k_1 = 1$ and answers a question
posed by S\'arkozy and S\'os. We present some generalisations
for multilinear forms. This is a joint work with Javier Cilleruelo,
from Universidad Aut\' onoma de Madrid.
-------------------------------------------
Event: Discrete Math Seminar (Alan Meckler Colloquium)
Date: Tuesday, October 28, 2008
Time: 2:30-3:20 followed by refreshments
Room: IRMACS Presentation Studio, ASB 10900
Speaker: Dr. David Brydges, Canada Research Chair in Mathematical Physics
and Deputy Director of PIMS, University Of British Columbia
Title: Combinatorics with Gaussian integrals
Abstract:
This will be an exposition of identities that link Gaussian
integration with combinatorial problems, in particular self-avoiding
walks, tree-like molecules and the matrix tree theorem.
About the Speaker: David Brydges received his PhD in 1976 at the
University of Michigan under the direction of Paul Federbush. He was
in the faculty of the departments of mathematics and of physics at the
University of Virginia until 2001, when he was appointed as a Canada
Research Chair at the University of British Columbia. He is known to
mathematical physics and probability through his work on self-avoiding
walk, branched polymers, Coulomb systems and the renormalisation
group, and has lectured on these subjects in the Troisieme Cycle at Lausanne,
in the NachDiplom program at ETH, Switzerland, and at the Park City
Graduate Summer School. He was an Alfred P. Sloan Research fellow in
1982-1984 and president of the International Association of
Mathematical Physics from 2003-2005.
-------------------------------------------
Event: Discrete Math Seminar
Speaker: Mireille Bousquet-Melou
Affiliation: CNRS, Bordeaux, France
Date: Thursday September 23, 2008
Time: 1:30 - 2:20
Room: K9509, SFU
Title: Enumeration of Planar Maps
Abstract:
N/A
-------------------------------------------
Event: Discrete Math Seminar
Speaker: Eli Berger
Affiliation: University of Haifa
Date: Tuesday October 14, 2008
Time: 3:30 - 4:20
Room: K9509, SFU
Title: Using classical topology in combinatorial problems
Abstract:
The idea of using topology in order to solve combinatorial problems has been
known for several decades, but only recently it started to become an organized
theory. In my talk I will introduce several classical topological theorems such
as Brouwer's fixed point theorem and Sperner's Lemma and give the basic methods
for using them in combinatorial settings. I will also describe a new approach
that may enable us to use the Borsuk Ulam theorem in similar settings and
hopefully obtain better results.
-------------------------------------------
Event: Discrete Math Seminar
Speaker: Ken-ichi Kawarabayashi
Affiliation: National Institute of Informatics, Japan
Date: Tuesday November 04, 2008
Time: 3:30 - 4:20
Room: K9509, SFU
Title: From the plane to higher surfaces
Abstract:
We say a result in a planar graph is linear extendable if,
for any graph G on a fixed surface of Euler genus g,
there is a vertex set X of order O(g) such that the result holds for G-X.
We give some linear extendable results, including Grotzsch's theorem,
the 5-list-color theorem, decomposition theorems etc.
This is joint work with Carsten Thomassen.
---------------------------------
Event: Discrete Math Seminar
Speaker: Aida Ouangraoua
Affiliation: Simon Fraser University
Date: Tuesday November 18, 2008
Time: 3:30 - 4:20
Room: K9509, SFU
Title: Algorithmical tools to compare tree-structured biological objects
Abstract:
Tree-graph is a data structure that is frequently used in biology :
botany, molecular biology, etc. In some botanical applications,
tree-graphs are used to model the topological structure of a plant
architecture and then to evaluate the similarity between these
architectures using tree-to-tree editing methods. Also, in molecular
biology RNA secondary structures (without pseudo-knots) are often
modeled as ordered tree-graphs in order to be compare using edit
distance computation.
For the last three decades, many tree-to-tree editing algorithms for
the comparison of tree-graphs have been developped. These works have
allowed to considere different extensions devoted to biological
applications. In this talk, I will first present a brief review of the
editing methods usually used for the comparison of unordered and
ordered tree-graphs. Then, I will describe new editing algorithms for
the comparison of tree-graphs that we developped in order to take
account of some specific properties of biological objects such as
semi-order and multi-scale organization of their components.
---------------------------------
Event: 2008 Combinatorial Potlach
Speaker: Eric Fusy + Chuck Dunn + Ioana Dumitriu
Affiliation: Simon Fraser U. + Linfield Collge + U. Washington
Date: Saturday November 22, 2008
Time: 10:00am - 5:00pm
Room: Room 193, Thompson Hall, Science Center, U. Puget Sound, N 14th St and Union Ave, Tacoma WA
Title:
11am - Bijective Links on Planar Maps via Orientations +
2pm - Complete Multipartite Graphs and the Relaxed Coloring Game +
4pm - Path Counting and the Moment Method for Random Matrices OR Fun with Walter and Theo
---------------------------------
Event: Discrete Math Seminar
Speaker: Brian Alspach
Affiliation: University of Newcastle, Australia
Date: Tuesday December 02, 2008
Time: 3:30pm - 4:20pm
Room: K10908 IRMACS, SFU
Title: Hamlton paths in vertex-transitive graphs
Abstract:
A graph is Hamilton-connected if for any two vertices u and v
there is a Hamilton path whose terminal vertices are u
and v. Similarly, a bipartite graph is Hamilton-laceable if for any
two vertices u and v from distinct parts there is a Hamilton path with
terminal vertices u and v. We present a survey of what is known
about Hamilton-connected and Hamilton-laceable vertex-transitive
graphs.
---------------------------------
Event: Discrete Math Seminar
Speaker: Robert Bailey
Affiliation: Carleton University
Date: Tuesday February 10, 2009
Time: 3:30pm - 4:20pm
Room: K9509, SFU
Title: Packing spanning trees in graphs and bases in matroids
Abstract:
The spanning tree packing number of a graph G, denoted \sigma(G),
is the largest number of edge-disjoint spanning trees in G.
An obvious upper bound on \sigma(G) is the edge-connectivity of G.
We consider those graphs for which these two parameters are equal,
and obtain a constructive description of them.
We can also ask an equivalent question for matroids,
and will conclude by mentioning this.
This is joint work with Brett Stevens (Carleton) and Mike Newman (Ottawa).
---------------------------------
Event: Discrete Math Seminar
Speaker: Markus Grassl
Affiliation: Centre for Quantum Technologies (NUS), Singapore
Date: Tuesday February 24, 2009
Time: 3:30pm - 4:20pm
Room: K9509, SFU
Title: Searching for good error-correcting codes
Abstract:
A central problem in coding theory is to construct codes with the
highest possible minimum distance. An important class of codes are
linear block codes, i.e., k-dimensional subspaces of an n-dimensional
vector space over a finite field GF(q). There are well-known tables
that for given n, k, and q provide upper and lower bounds on the
minimum distance. The most prominent tables are those of Andries
Brouwer.
In cooperation with the Computational Algebra Group at the University
of Sydney I have been working on explicit constructions for codes
establishing the lower bounds. In my talk I will present novel
algorithms and techniques yielding codes which often even improve the
lower bounds.
The core result is an optimized algorithm for computing the minimum
distance of a linear code, a problem which is NP hard in general.
The algorithm can exploit partial knowledge of the automorphism group,
leading to improved algorithms. Then several constructions are
discussed that are based on codes with known generator matrices.
The combinatorial search problem associated with one of these
constructions can be rephrased in terms of polynomial equations.
A Groebner basis for the corresponding ideal, and hence a solution to
the original problem, can often be computed in moderate time. Time
permitting, generalizations of the algorithms to additive codes and
quantum error-correcting codes will be given.
---------------------------------
Event: Special Joint Discrete/Applied Math Seminar
Speaker: Natasa Przulj
Affiliation: University of California, Irvine
Date: Tuesday March 24, 2009
Time: 3:30pm - 4:20pm
Room: K9509, SFU
Title: From Network Topology to Biological Function and Disease
Abstract:
Historically, a new natural science proceeds through three stages of
development: first, amassing observations about the world; second,
developing simplistic models capable of approximately reproducing the
observations; and finally, the development of accurate predictive
theoretical models under which the observations and earlier models become
evident. Our current understanding of biological networks can be likened to
the state of physics before Newton: although Copernicus, Kepler, Galileo
and others had amassed a huge corpus of observations, and even some
simplistic, case-specific models describing various phenomena, there was no
theoretical framework tying it all together to provide understanding.
Systems biology is currently somewhere between the first and second stages:
we can hardly even describe the observational data mathematically, much
less understand it theoretically.
Analysis and comparison of genetic sequences is well into the second stage
mentioned above and making tentative steps into the third, but network
analysis is just barely entering the second stage. In this talk I discuss
new tools, developed in my lab, which are advancing network analysis into
this second stage, and possibly giving hints towards the third stage---a
theoretical understanding of the structure of biological networks.
Analogous to tools for analyzing and comparing genetic sequences, we are
developing new tools that decipher large network data sets, with the goal
of improving biological understanding and contributing to development of
new therapeutics.
Because nature is variable and the data are noisy, traditional graph
isomorphism is of little use for graph comparison, and a more flexible,
intentionally approximate approach is necessary. We introduce a systematic
measure of a network's local structure that imposes a large number of local
similarity constraints on networks being compared. In particular, we
generalize the degree of a node to a degree vector describing the local
topology around a node. We demonstrate that this local node similarity
corresponds to similarity in biological function and involvement in
disease. We also show how to use the degree vectors to design a
network alignment algorithm that produces correct phylogenetic trees.
Next, we demonstrate how statistics from large numbers of these
local similarity measures can be combined to provide a global network
similarity measure. Using this global similarity measure, we demonstrate
that protein-protein interaction (PPI) networks are better modeled by
geometric graphs than by any previous model. The geometric model is
further corroborated by demonstrating that PPI networks can explicitly be
embedded into a low-dimensional geometric space. Finally, we argue for a
theoretical reason why PPI networks might be geometric.
---------------------------------
Event: Discrete Math Seminar
Speaker: Hernando Bermudez
Affiliation: University of Monatna at Missoula
Date: Tuesday March 31, 2009
Time: 3:30pm - 4:20pm
Room: K9509, SFU
Title: Scheduling Tournaments With Home and Away Constraints
Abstract:
We study the problem of scheduling a round robin tournament
in which each team that competes in the tournament has their
own stadium and said stadium may be unavailable on certain dates.
We model this problem in terms of one factorizations
of complete graphs.
----------------
Event: Discrete Math Seminar
Speaker: Cedric Chauve
Affiliation: Simon Fraser University
Date: Tuesday April 14, 2009
Time: 3:30pm - 4:20pm
Room: K9509, SFU
Title: Enumerative results for graph decomposition trees
Abstract:
I will discuss two works.
(1) The average case analysis of an algorithm for computing genome
rearrangement distances that relies on enumerative results
on the modular decomposition of labeled permutation graphs.
In particular, we will give precise characterization of the modular
decomposition tree of a random permutation, and asymptotics of
statistics for separable permutations (work in collaboration with
M. Bouvel (LIAFA), M. Mishna (SFU) and D. Rossin (LIAFA)).
(2) An enumeration of distance hereditary graphs from their split
decomposition tree (work in collaboration with Eric Fusy (SFU/CNRS)).
----------------
Event: Discrete Math Seminar
Speaker: Eric Fusy
Affiliation: CNRS, France
Date: Tuesday April 21, 2009
Time: 3:30pm - 4:20pm
Room: K9509, SFU
Title: Schnyder woods generalized to higher genus surfaces
Abstract:
Schnyder showed in 1989 that every plane triangulation has a partition
of its (inner) edges into 3 trees spanning all (inner) vertices.
The so-called Schnyder woods are a powerful combinatorial structure
with many applications: new planarity criterion, straight-line drawing,
coding, bijective counting... In this talk, we show that the definition
of Schnyder woods admits a generalization to surfaces of any genus,
and that such a Schnyder wood can be computed efficiently.
As an application we extend a simple coding procedure to higher genus.
This is joint work with Luca Castelli Aleardi and Thomas Lewiner.
----------------
Event: Discrete Math Seminar
Speaker: Bruce Richter
Affiliation: Univerisity of Waterloo
Date: Tuesday April 28, 2009
Time: 3:30pm - 4:20pm
Room: K9509, SFU
Title: Do we really know what characterizes planarity?
Abstract:
Three well-known characterizations of planarity of graphs
are the theorems of Kuratowski, MacLane, and Whitney. The first is
about forbidden subgraphs, the second about a basis for the cycle
space, and the third is about dual graphs. Thomassen generalized
Kuratowski's Theorem to "2-connected, compact, locally connected
metric spaces", Bruhn and Stein proved MacLane's Theorem for the
Freudenthal compactification of a locally finite graph. Bruhn and
Diestel proved a version of Whitney's Theorem for (compactifications
of certain) infinite graphs.
In this talk, we will see how to omit the "2-connected"
hypothesis from Thomassen's Theorem and generalize both of the other
two theorems to compact graph-like spaces.
----------------
Event: Discrete Math Seminar
Speaker: Daniel Kral
Affiliation: Charles University, Prague, Czechia
Date: Tuesday May 5, 2009
Time: 2:00pm - 2:50pm
Room: PIMS Seminar room, TASC2 8500, SFU
Title: Removal Lemma for systems of linear equations
Abstract:
We study algebraic analogues of the graph Removal Lemma.
Vaguely speaking, the lemma says that if a given graph
does not contain too many subgraphs of a given kind, then
all the subgraphs of this kind can be destroyed by removing
few edges. In 2005, Green conjectured the following
analogue of it for systems of equations over integers:
For every k x m integral matrix A with rank k and every eps>0,
there exists delta>0 such that the following holds for every N and
every subset S of {1,...N}: if the number of solutions of A x = 0
with x \in S^m is at most delta N^{m-k}, then it is possible
to destroy all solutions x \in S^m of A x = 0 by removing
at most eps N elements from the set S.
We prove this conjecture by establishing its variant
for not necessarily homogenous systems of equations
over finite fields. The core of our proof is a reduction
of the statement to the colored version of hypergraph
Removal Lemma for (k+1)-uniform hypergraphs. Independently
of us, Shapira obtained the same result using a reduction
to the colored version of hypergraph Removal Lemma
for O(m^2)-uniform hypergraphs.
This is joint work with Oriol Serra and Lluis Vena.
----------------
Event: Discrete Math Seminar
Speaker: Gena Hahn
Affiliation: Universite de Montreal
Date: Tuesday Aug 25, 2009
Time: 3:30pm - 4:20pm
Room: K9509, SFU
Title: Cops-and-robbers on infinite graphs
Abstract:
While the game of cops-and-robbers has been studied, sometimes
intensely, over the past two decades for finite graphs, not much
has been done for infinite ones. This talk will be a quick survey of
some finite graph results leading to considerations of infinite ones
where we mention some perhaps surprising results, some old, some new.
Some of this work is in collaboration with Anthony Bonato,
Francois Laviolette, Norbert Sauer, Claude Tardif end Robert Woodrow.
----------------
Event: Discrete Math Seminar
Speaker: Robert Samal
Affiliation: Charles University, Cz
Date: Tuesday Sep 01, 2009
Time: 3:30pm - 4:20pm
Room: K9509, SFU
Title: Cubical chromatic number, spherical chromatic number, and Lovasz theta function
Abstract:
We study several variants of graph coloring, based on (fractional) covering
graphs with cuts, labeling its vertices with unit vectors, etc. Connections
with Lovasz' theta function and with approximability of MAX-H-COLORING
(generalization of MAX-CUT) will be discussed.
----------------
Event: Discrete Math Seminar
Speaker: Bojan Mohar, CRC Chair
Insitute: Simon Fraser University
Date: Tuesday Sep 22, 2009
Time: 1:30pm - 2:20pm
Room: K9509, SFU
Title: How useful can the spectral radius of graphs be?
Abstract:
This will be a presentation of my talk at EuroComb'09:
Is there a structural graph theory based on the spectral radius?
The spectral radius r(G) of a finite graph G is defined as the largest eigenvalue
of the adjacency matrix of the graph. It can also be defined for infinite graphs as the
supremum of spectral radii of all finite subgraphs. In this talk, we shall survey what is known about
this simple algebraic parameter. Special emphasis will be made to uncover properties
related to the structural graph theory. Among others, the following topics will be discussed:
- Spectral radius of finite and infinite trees, planar graphs, tessellations.
- Minor-closed families of graphs and beyond.
- Spectral degeneracy with respect to hereditary, induced hereditary and graph minors orderings.
- Spectral radius of digraphs.
----------------
Event: Discrete Math Seminar
Speaker: Ladislaw Stacho
Insitute: Simon Fraser University
Date: Tuesday Sep 29, 2009
Time: 1:30pm - 2:20pm
Room: K9509, SFU
Title:
Cyclic colorings of plane graphs with independent faces
Abstract:
Let G be a plane graph with maximum face size Delta*. If all faces of G
with size four or more are vertex disjoint, then G has a cyclic coloring
with Delta* + 1 colors, i.e., a coloring such that all vertices incident with
the same face receive distinct colors.
We discuss the background behind this statement, in particular three
related conjectures, the Ringel's conjecture, Ore and Plummer conjecture,
and Albertson's conjecture. Then we present known results about cyclic
colorings and finally we highlight the discharging method that we used
to prove our result that answers Albertson's conjecture in more general
settings.
This is joined work with Jernej Azarija, Rok Erman, Daniel Kral,
and Matjaz Krnc.
----------------
Event: Discrete Math Seminar
Speaker: Guillaume Chapuy
Institute: Ecol Polytechnique, Paris and SFU
Date: Tuesday Oct 06, 2009
Time: 1:30pm - 2:20pm
Room: K9509
Title: Maps on surfaces : asymptotic enumeration and metric properties.
Abstract:
An orientable map of genus g is a (multi)graph embedded without edge
crossings in the torus with g handles. When the number of edges n tends to
infinity and g is fixed, the number of these objects behaves as:
t_g n^(5(g-1)/2) 12^n for t_g>0 [Bender and Canfield 86, via generating
functions].
I will talk about new bijective techniques, relating orientable maps to
tree-like objects, that enable to understand this result better. In
particular, the counting exponent 5(g-1)/2 will appear as a simple
combinatorial parameter of the surface.
The bijection being based on a geodesic exploration of the graph, it gives
access to non-trivial metric information : for example, the diameter (and
typical distance) in a random map of fixed genus is of order n^(1/4), and
certain scaling distributions can be explicitely described.
----------------
Event: Discrete Math Seminar
Speaker: Andrea Spencer
Institute: Simon Fraser University
Date: Tuesday 13 Oct 2009
Time: 1:30 - 2:20
Room: K9509, SFU
Title: Efficient Edge List Colouring of Cubic Planar Graphs
Abstract:
A graph is k-edge-choosable if for every assignment of a list of k colours to each edge,
it is possible to obtain a proper edge colouring by selecting one colour from each list.
It follows from an extension of Brooks' Theorem that every cubic graph is 4-edge-choosable.
In this talk, we strengthen this result by showing that if a cubic graph is planar and has c cut edges,
then all but a specified set of 3c edges may have lists of smaller length.
This is joint work with Luis Goddyn.
----------------
Event: Discrete Math Seminar
Speaker: Mahdad Khatirinejad Fard
Institute: Helsinki University of Technology
Date: Tuesday, 27 Oct 2009
Time: 1:30 - 2:20
Room: K9509
Title: Edge-weighting vertex colouring of (di)graphs
Abstract:
An edge-weighting vertex colouring of a (di)graph is an edge-weight
assignment such that the accumulated weight at each vertex yields a
proper vertex colouring. If such an assignment from a set S exists, we
say the graph is S-weight colourable. Using the Combinatorial
Nullstellensatz and a classical theorem of Schur, we show that every
digraph is S-weight colourable for any set S of size 2. We also
discuss the analogous problem for graphs and present a number of
intriguing families of (non) S-weight colourable graphs (for various
sets S of size 2).
----------------
Event: Discrete Math Seminar
Speaker: Kevin Milans
Institute: University of Illinois at Urbana-Champaign
Date: Tuesday Feb 09, 2010
Time: 3:30pm - 4:20pm
Room: TASC2 8500, PIMS Seminar room, SFU
Title: Degree Ramsey Numbers of Graphs
Abstract:
In Ramsey Theory, we study when every partition of a large structure
yields a part with additional structure. For example, Van der Waerden's
theorem states that every s-coloring of the integers contains arbitrarily
long monochromatic arithmetic progressions, and the Hales-Jewett Theorem
guarantees that every game of tic-tac-toe in high dimensions has a winner.
Ramsey's Theorem implies that for any target graph G, every s-coloring of
the edges of some sufficiently large host graph contains a monochromatic
copy of G. In Ramsey's Theorem, the host graph is dense (in fact complete).
We explore conditions under which the host graph can be sparse and still
force a monochromatic G.
A graph H *arrows* a graph G if every 2-edge-coloring of H contains a
monochromatic copy of G. The *degree Ramsey number* of G is the minimum
k such that some graph with maximum degree k arrows G. Burr, Erdos,
and Lovasz found the degree Ramsey number of stars and complete graphs.
We establish the degree Ramsey number exactly for double stars and for C_4,
the cycle on four vertices. We prove that the degree Ramsey number of the cycle
C_n is at most 96 when n is even and at most 3878 in general. Consequently,
there are very sparse graphs that arrow large cycles. We present a family of
graphs in which the degree Ramsey number of G is bounded by a function of the
maximum degree of G and ask which graph families have this property. This is
joint work with Tao Jiang, Bill Kinnersley, and Douglas B. West.
-------
Event: Discrete Math Seminar
Speaker: Ararat Harutyunyan
Institute: SFU
Date: Tuesday, March 02, 2010
Time: 3:30 - 4:20
Room: TASC2 8500, SFU
Title: Independent dominating sets in graphs of girth five
Abstract:
One of the classical applications of the probabilistic method
is the result that every n-vertex graph G with minimum degree d has a
dominating set of size at most (n(1+log(d+1))/(d+1). In this talk we show
that if G is d-regular and of girth at least 5, then we can find an independent
dominating set of essentially the same size, n(log(d) + c)/d. This upper bound
is best possible up to the constant c, and it extends results of Duckworth and
Wormald on the independent domination number of random regular graphs. We also
show (by examples) that in the above statement, the exclusion of cycles of
length 4 is necessary and that the regularity condition cannot be significantly
improved. The method of the proof is probabilistic - it is a variant of methods
such as Rodl's Nibble and Wormald's differential equation method.
This is joint work with Paul Horn and Jacques Verstraete.
-------
Event: Discrete Math Seminar
Speaker: Adolfo Rodriguez
Institute: LACIM, Universite du Quebec a Montreal
Date: THURSDAY March 4, 2010
Time: 1pm - 2pm
Room: K9509
Title: Bugs, colonies, and q-Boson normal ordering
Abstract:
In my work with Miguel Mendez, we provided a new combinatorial model
for the coefficients appearing in the normal ordering of q-Boson words,
by introducing combinatorial structures called bugs, colonies and settlements.
In this lecture I will show how this kind of structures can be used to
simplify proofs of combinatorial theorems involving q-analogs,
and how our combinatorial model and formulas for the coefficients appearing
in the q-Boson normal ordering problem arise as a direct application of
these general techniques.
-------
Event: Discrete Math Seminar
Speaker: Roland Wittler
Institute: Bielefeld, and SFU
Date: Tuesday, March 23, 2010
Time: 3:30 - 4:20
Room: TASC2 8500
Title: Phylogeny-based Analysis of Gene Clusters
Abstract:
The order of genes in genomes provides extensive information. In
comparative genomics, differences or similarities of gene orders are
determined to predict functional relations of genes or phylogenetic
relations of genomes. For this purpose, various combinatorial models can
be used to identify gene clusters - groups of genes that are co-located
in a set of genomified approach to model gene clusters and define the
problem of labeling the inner nodes of a given phylogenetic tree with
sets of gene clusters. Our optimization criterion in this context
combines two properties:
(1) Parsimony, i.e. the number of gains and losses of gene clusters has
to be minimal. This aim can be approached using well known methods, like
Fitch-Hartigan.
(2) Consistency, i.e. for each ancestral node, there must exist at least
one potential gene order that contains all the reconstructed clusters.
Verifying this property is far from being trivial. We give an overview
of already known and our new results for solving the "consistency
problem" for different gene cluster models. Our findings range from a
simple and efficient solution for adjacencies to NP-completeness for
other models.
We developed an oracle-based algorithm to reconstruct optimal labelings
and finally show results on both simulated and real data.
-------
Event: Discrete Math Seminar
Speaker: Justin Chan
Institute: University of Victoria
Date: Thursday, March 25, 2010
Time: 1:00 - 1:50
Room: K 9509
Title: The Lamken-Wilson Theorem and Its Applications
Abstract:
In this talk, we will describe the Lamken-Wilson theorem and how
it applies to my work on design theory. My work on this subject was
motivated by a flaw in the proof of the asymptotic existence of uniform
G-frames, a crucial ingredient in the proof of asymptotic existence of
resolvable G-designs. In my thesis, I was able to fix the proof, and
provide simplifications for similar proofs involving other structures.
-------
Event : IRMACS: The Interdisciplinary Colloquium
Speaker: Dr. Peter Horak
Institute: University of Washington, Tacoma
Date: Monday, April 12, 2010
Time: 2:30 - 3:20
Room: IRMACS Presentation Studio, ASB 10900, SFU
Title: Tiling n-space by cubes
Abstract:
A lattice tiling T of n-space by cubes is a tiling where the centers of cubes in T
form a group under the vector addition. In 1907 Minkowski conjectured that in a lattice tiling
of n-space by unit cubes there must be a pair of cubes that share a complete (n-1)-dimensional
face. Minkowski's problem attracted a lot of attention as it is an interface of several
mathematical disciplines. In fact, Minkowski's problem, like many ideas in mathematics, can
trace its roots to the Phytagorean theorem aB2+bB2=cB2. We discuss the conjecture, its history
and
variations, and then we describe some problems that Minkowski's conjecture, in turn, suggested.
We will focus on tilings of n-space by clusters of cubes, namely by spheres in Lee metric, and
show how these tilings are related to the perfect error-correcting codes. The Golomb-Welch
conjecture, the long-standing and the most famous conjecture in the area, will be discussed. At
the end of our talk we will consider tilings by n-crosses, the Lee spheres of radius 1 (if we
reflect an n-dimensional cube in all its faces, then the 2n+1 obtained cubes form an n-cross).
Some "unexpected" tilings by n-crosses will be presented.
Event: Discrete Math Seminar
Speaker: Alejandro Erickson
Institute: University of Victoria
Date: Tuesday, April 13, 2010
Time: 3:30 - 4:20
Room: TASC2 8500 (PiMS seminar room)
Title: Negative correlation properties for graphs
Abstract:
The effective conductance between two points in a network of resistors
should not decrease if the conductance of any resistor is increased.
This is equivalent to the following. If we select one of the spanning trees
of a graph $G$, with a certain probability, then the probability that the tree
contains a desired edge $e$ is not increased if we choose only among spanning trees
already containing a given edge $f$. This property is a kind of negative correlation
between edges in spanning trees, and has been known to be true for many years.
Whether or not this holds for spanning forests, however, is open.
I will give an accessible talk which introduces the problem and describes
some of the work done so far and especially, a possible lead toward a solution.
-------
Event: Discrete Math Seminar
Speaker: Alejandro Erickson
Institute: University of Victoria
Date: Tuesday, April 13, 2010
Time: 3:30 - 4:20
Room: TASC2 8500 (PiMS seminar room)
Title: Negative correlation properties for graphs
Abstract:
The effective conductance between two points in a network of resistors
should not decrease if the conductance of any resistor is increased.
This is equivalent to the following. If we select one of the spanning trees
of a graph $G$, with a certain probability, then the probability that the tree
contains a desired edge $e$ is not increased if we choose only among spanning trees
already containing a given edge $f$. This property is a kind of negative correlation
between edges in spanning trees, and has been known to be true for many years.
Whether or not this holds for spanning forests, however, is open.
I will give an accessible talk which introduces the problem and describes
some of the work done so far and especially, a possible lead toward a solution.
-------
Event: Discrete Math Seminar
Speaker: Robert Samal
Institute: Charles University, Prague
Date: Tuesday, April 20, 2010
Time: 3:30 - 4:20
Room: TASC2 8500 (PiMS seminar room)
Title: Star Chromatic Index
Abstract:
The star chromatic number of a graph is the minimum number of colors needed
to properly color the graph so that each two color classes induce a forest
in which every component is a star.
The star chromatic index of a graph G is the star chromatic number of the
line graph L(G). Equivalently, it is the minimum number of colors needed to
properly color the edges of the graph so that no path or cycle of length
four is bi-colored.
We obtain a near-linear upper bound on the star chromatic index in terms of
the maximum degree $\Delta=\Delta(G)$. Our best lower bound in terms of
$\Delta$ is $2\Delta(1+o(1))$. We also consider the special case of cubic
graphs, for which it is shown that the star chromatic index lies between 4
and 7. The proofs involve a variety of notions from other branches of
mathematics and may therefore be of certain independent interest.
Event: Discrete Math Seminar
Speaker: John Stardom
Institute: Statistics Canada
Date: Tuesday, June 8, 2010
Time: 2:30 - 3:30
Room: K9509
Title: Sample Stratification and Allocation: an Application to Statistics Canada's Unified Enterprise Survey
Abstract:
In 1988, Lavallée and Hidiroglou proposed na algorithm that, given a
fixed target level of precision and sample allocation scheme, could be
used to optimally stratify a population in order to minimize the
effective sample size. For over a decade, this algorithm has been
used in selecting the annual sample for Statistics Canada's Unified
Enterprise Survey (UES).
This presentation outlines the problem of stratification and
allocation, in particular for the UES, and examines the
Lavallée-Hidiroglou (L-H) algorithm as well as some of its recent
generalizations. A recently-proposed random search algorithm due to
Kozak is also presented. This alternative approach is compared to the
L-H algorithm in order to assess the feasibility of its implementation
in the case of a survey redesign.
Event: Discrete Math Seminar
Speaker: Christian Stump
Instiute: CRM-ISM Postdoctoral Research Fellow; Lacim UQAM
Date: Tuesday, June 22, 2010
Time: 2:30 - 3:30
Room: K9509 SFU
Title: Non-crossing and non-nesting partitions and the cyclic sieving phenomenon
Abstract:
The cyclic sieving phenomenon (CSP) was introduced in 2004 by Reiner,
Stanton and White and generalizes Stembridge's q=-1 phenomenon. It
appears in various contexts and in particular in Coxeter-Catalan
combinatorics: for example, several instances of the CSP can be found
in the context of non-crossing partitions associated to Coxeter
groups. I will define the CSP in general and will give several
examples. Moreover, I will introduce a less known instance of the CSP
on non-crossing partitions using the Kreweras complement and will
relate it to a new instance on non-nesting partitions which can be
associated to crystallographic Coxeter groups.
Event: Discrete Math Seminar
Speaker: Karel Casteels
Institute: Simon Fraser University
Date: Tuesday, July 6, 2010
Time: 2:30 - 3:30
Room: K9509 SFU
Title: Combinatorial aspects of the prime spectrum of quantum matrices
Abstract: This talk will be a review of the results of my thesis, written
under the supervision of Jason Bell. We wish to understand the prime
spectrum of the algebra of quantum matrices (I'll explain what this
means). To this end, a useful combinatorial tool is that of "Cauchon
diagrams". I'll show how we can use these to both determine generating
sets of certain prime ideals and how one can determine important
information about the structure of the prime spectrum. The latter
result implies some enumerative formula which I'll also discuss.
Event: Discrete Math Seminar
Speaker: Guillaume Chapuy
Institute: Simon Fraser University
Date: Tuesday, July 13, 2010
Time: 2:30 - 3:30
Room: K9509 SFU
Title: Covered maps on orientable surfaces
Abstract:
In 1967, Mullin introduced "tree-rooted" planar maps, i.e. plane graphs
carrying a distinguished spanning tree, and he discovered a very nice
counting formula for these objects. The formula is easy to establish,
but the combinatorial interpretation has been open until Bernardi found
in 2006 a very nice bijection relating them in particular to "minimal
plane orientations". When trying to generalize this result to surfaces
of higher genus, we realized that tree-rooted maps are not the good
objects anymore, partly due to their lack of duality. We introduced the
larger class of "covered maps", in which the spanning tree is replaced
by a "one-face spanning submap". The genus of the submap is not fixed,
in particular on any surface, a tree-rooted map is a covered map, and so
is its dual. Covered maps are in bijection with a generalization of
plane minimal orientations that we called "left-connected orientations",
and other objects. Nice counting formulas follow, as well as surprising
enumerative corollaries concerning one-face maps themselves.
Speaker: Kai-Uwe Schmidt
Institute: Simon Fraser University
Date: Tuesday, August 10 , 2010
Time: 2:30 - 3:30
Room: K9509 SFU
Title: Appended m-sequences with merit factor greater than 3.34
Abstract:
Speaker: Zdenek Dvorak
Institute: Charles University
Date: Tuesday, Sept 14, 2010
Time: 2:30 - 3:30
Room: K9509 SFU
Title: Choosability of Planar graphs
Abstract:A graph is k-choosable if it can be properly colored from any assignment
of lists of colors of length at least k to its vertices. A well-known results of
Thomassen state that every planar graph is 5-choosable and every planar graph of girth 5
is 3-choosable. These results are tight, as shown by constructions of Voigt. We review
some new results in this area, concerning 3-choosability of planar graphs with triangles
and 4-cycles far apart (an analogue of Havel's problem) and bounds on sizes of critical planar
graphs with precolored vertices of one face.
Speaker: Jessica Mcdonald
Institute: Simon Fraser University
Date: Tuesday,Sept 21 , 2010
Time: 2:30 - 3:30
Room: K9509 SFU
Title: Characterizing high chromatic index
Abstract:
For a multigraph G, the chromatic index of G is the minimum number of colours needed to colour the edges of G such that no two
edges sharing a vertex have the same colour. There are many well-known upper bounds for chromatic index, including bounds by Shannon, Vizing,
Goldberg and Steffen. In this talk we explore the question of which multigraphs actually achieve these bounds. As part of the discussion we present
a new partial characterization of those multigraphs achieving Vizing's upper bound, a result obtained jointly with P. Haxell.
Speaker: Emmanuel Godard
Institute: U. Aix (Marseilles)
Date: Tuesday, Sept 28 , 2010
Time: 2:30 - 3:30
Room: K9509 SFU
Title: Using isometric embeddings in distributed algorithms for the median problem in partial rectangular grids and their relatives
Abstract:
Given a graph G = (V, E), a vertex v of G is a median vertex if it minimizes the sum of the distances to all other vertices of
G. The median problem consists in finding the set of all median vertices
of G. A self-stabilizing algorithm is a distributed algorithm that can recover from any transient fault of the system.
We present a self-stabilizing algorithm for the median problem in partial rectangular grids. Our algorithm is based on the fact that partial rectangular grids can be isometrically embedded into the Cartesian product of two trees. These trees are closely r
elated to two spanning trees of the partial grid, to which we apply the algorithm proposed by Antonoiu, Srimani (1999) and Bruell, Ghosh, Karaata, Pemmaraju (1999) for computing the medians in trees.
Then we extend our approach from partial rectangular grids to some other plane quadrangulations.
This is joint work with Victor Chepoi, Tristan Fevat, and Yann Vaxès
(Aix-Marseille Université)
Speaker: Mohamed Omar
Institute: UC Davis
Date: Tuesday, October 5, 2010
Time: 2:30 - 3:30
Room: K9509 SFU
Title: Graph Automorphism and Permutation Groups via Polytopes
Abstract:
Speaker: Karen Yeats
Institute: Simon Fraser University
Date: Tuesday, October 12 , 2010
Time: 2:30 - 3:30
Room: K9509 SFU
Title: The support of power series given by systems of equations.
Abstract: This is joint work with Jason Bell and Stanley Burris. We investigate the problem of when generating functions built out of some standard combinatorial operators have periodic support. This is closely related to the problem of spectra in finit
e model theory.
Speaker: Cedric Chauve
Institute: Simon Fraser University
Date: Tuesday, October 19, 2010
Time: 2:30 - 3:30
Room: K9509 SFU
Title:On matrices that do not have the Consecutive-Ones Property.
Abstract:There has been a recent renewed interest in the computational biology community
for the classical Consecutive-Ones Property (c1P) for binary matrices, motivated
by the reconstruction of ancestral genomes. In general, binary matrices obtained
from real data do not satisfy the C1P, while they should if the data were
error-free.
In the first part of the talk, I will introduce the notion of Minimal C1P
Conflicting Set (MCS) for a given binary matrix M, that are the minimum sets of
rows of M that do not satisfy the C1P. I will discuss the combinatorial properties
of MCS and several algorithmic questions: counting the number of MCS a row of M
belongs to, deciding if a row is part of at least one MCS, generating all MCS.
I will present exponential time algorithms for these questions based on old
results of Tucker and on the generation of Minimum True Clauses for Monotone
Boolean Functions. Work in collaboration with V. You, T. Stephen and U.U. Haus.
Speaker: Andrew Crites
Institute: University of Washington
Date: Tuesday, October 26, 2010
Time: 2:30 - 3:30
Room: K9509 SFU
Title: Affine permutations and pattern avoidance
Abstract:
n this talk I will introduce some of the combinatorics behind affine
permutations. These are a generalization of classical permutations
that, when viewed as a reflection group, amount to adding an affine
reflection to the set of generators (hence the name). We now end up
with an infinite group, however, many of the same results from
classical permutations still hold. Classifying families of
permutations in terms of the patterns they avoid has been studied for
a long time. However, applying pattern avoidance to affine
permutations is fairly new. I will discuss pattern avoidance, and in
particular, the role it plays in the geometry of the corresponding
affine Schubert varieties.
Part of this talk is joint work with Sara Billey.
Speaker: Flavio Guinez
Institution: UBC
Date: Tuesday, November 9, 2010
Time: 2:30 - 3:30
Room: K9509 SFU
Title:The reconstruction of a colored grid by its projections: a solution to the 2-atom
problem in discrete tomography.
Abstract:
Let us consider a digitalized image arranged in a two-dimensional grid in which every pixel
takes one of three possible colors: red, green or blue. The projections of each color are
the total number of pixels of that color that appear in each row and column of the grid. We
consider the following problem: Given requests of colors red, green and blue for each row
and column, does there exist an image having that request as projections?
For 2 colors, this problem is equivalent to a classical combinatorial question in which we
are interested in the reconstruction of binary matrices by their row and column sum
vectors. Ryser, and independently Gale, found a necessary and sufficient condition for the
existence of a such a matrix, and they exhibited a very simple polynomial time algorithm to
construct one solution when the condition is satisfied. In contrast, for 4 or more colors,
Chrobak and Durr showed that the problem is NP-hard.
In this talk we will review the case of 3 colors. First, we will see that for some
particular instances a necessary and sufficient condition exists. However, we prove that in
general the problem is NP-hard. In addition, we study a generalization of this problem to
the reconstruction of tilings of the grid using rectangles of different sizes, only by
given their projections. For this tiling problem, we clarify the computational complexity
of all possible cases, with the exception of a single one that still remains open.
Last but not least, we will see some connections of this problem with the factor problem in
graphs, as well as other combinatorial problems.
Speaker: Bruce Shepherd
Institute: Simon Fraser University
Date: Tuesday, November 30, 2010
Time: 2:30 - 3:30
Room: K9509 SFU
Title: Minimum Cost Networks Supporting All Matchings
Abstract:
Given a graph G, and a subset W of V(G) (called the terminals),
we'd like to assign edge capacities so that (roughly speaking)
any matching on W can be "routed" using the capacities.
The first part of the talk explores several different mathematical
formulations on the above problem. We then focus on one version -
called the virtual private network probelm (VPN for short) - which has
a particularly clean solution using T-joins. We hope to also emphasize some
of the many open problems in this area.
Spring 2011
Tuesday February 1, 2011 2:30 PM K9509
Speaker: Roi Krakovski
Title: Subdivisions in Graphs
Abstract: A graph G is said to be a subdivision of a graph H, if G can
be obtained from H by subdividing some of the edges of H with vertices
of degree two.
The question: "what is the structure of a graph containing no
subdivision of H as a subgraph, for some fixed H?" has been one of the
main problems in graph theory since the 1930s. Such
"H-subdivision-free" graph families are found in many of the so called
"pearls" of graph theory: Kuratowski's theorem, Tutte's integer-flow
conjectures, Hajos' conjecture, Kelmans-Seymour conjecture and more.
Of a particular interest is the case when H is isomorphic to the
complete graph on 5 vertices (K5). The Kelmans-Seymour conjecture
(1975) asserts that every 5-connected non-planar graph contains a
subdivision of K5. In 1992, X. Zha conjectured that the line-graph of
a 3-connected non-planar graph contains a subdivision of K5. In this
talk I will present recent progress on the first conjecture, and (if
time permits) a proof of the second conjecture.
---------------------------------------------------------------
Tuesday February 8, 2011 2:30 PM K9509
Speaker: Sam Black, SFU
Title: A new state model for the Alexander polynomial
Abstract: Markov's theorem gives conditions under which a function
defined on braids descends to a link invariant, upon closing up the
ends of the braid. Thus, representations of the braid group, suitably
rescaled, are effective tools in knot theory. Perhaps the nicest
representations factor through the Iwahori-Hecke algebra (of type A),
and the corresponding invariants enjoy a skein relation on the link
diagrams. I will present a new diagram calculus for obtaining the
Alexander polynomial, beginning with a braid diagram and obtaining
various combinatorial states and summing their weights. If we look
"under the hood," then we find a version of Young's seminormal
representations adapted to the Hecke algebra, and some character
formulas due to Ocneanu. Time permitting, I will discuss a particular
quotient of the Hecke algebra on which these combinatorics are based.
---------------------------------------------------------------
Tuesday March 1, 2:30 PM K9509
Speaker: Winfried Hochstaettler, FernUniversität
Title: Some heuristics for the binary paint shop problem and their
expected number of colour changes
Abstract: in the binary paint shop problem we are given a word on $n$
characters of length $2n$ where every character occurs exactly
twice. The objective is to colour the letters of the word in two
colours, such that each character receives both colours and the number
of colour changes of consecutive letters is minimized. Amini et.\ al
proved that the expected number of colour changes of the heuristic
greedy colouring is at most $2n/3$. They also conjectured that the
true value is $n/2$. We verify their conjecture and, furthermore,
compute an expected number of $2n/3$ colour changes for a heuristic,
named {\em red first}, which behaves well on some worst case examples
for the greedy algorithm.
From our proof method, finally, we derive a new recursive greedy
heuristichich achieves an average number of $2n/5$ colour changes.
---------------------------------------------------------------
Tuesday March 1, 2:30 PM K9509 Speaker: Pavol Hell, SFU Title:
Obstruction Characterizations in Graph Partition Problems. Abstract:
I will discuss a type of partition problem that generalizes graph
colourings and homomorphisms, and often occurs in the study of graph
perfection. I will survey recent results from the perspective of
forbidden structure characterizations.
---------------------------------------------------------------
Tuesday March 15, 2:30 PM K9509
Speaker: Lino Demasi, SFU
Title: Domination in Plane Triangulations.
Abstract: Matheson and Tarjan
showed that the vertices of every plane triangulation can be divided
into 3 disjoint sets each of which is dominating. A direct corollary
of this is that any plane triangulation has a dominating set of size
$\frac{1}{3} \vert V(G) \vert$. They showed that a dominating set of
size $\frac{1}{4} \vert V(G) \vert$ is best possible in general, and
conjectured this to be true for all sufficiently large graphs. I will
present their result for $\frac{1}{3}$ as well as new result that
shows $\frac{2}{7}$ is possible for all but two graphs. This is joint
work with Matt Devos.
---------------------------------------------------------------
Tuesday March April 5, 2:30 PM K9509
Speaker: Gelasio Salazar
Title: Recent progress on Turan's Brickyard Problem
Abstract:
While working in a labor camp during World War II, Paul Turan came up
with the following problem. Suppose that there are m kilns and n
warehouses, and that each kiln is connected to each warehouse by a
rail track. What is the minimum number of rail crossings? This problem
gave rise to the area of crossing numbers. The crossing number cr(G)
of a graph G is the minimum number of crossings in a drawing of G in
the plane. Under this terminology, Turan's question is: what is the
crossing number of the complete bipartite graphs $K_{m,n}$? This
conjecture remains open; it has only been settled for $\min{m,n} \le
6$ and for a few special cases. In this talk we will review the
(short) literature on Turan's problem, including some recent progress
we have achieved jointly with Robin Christian and Bruce Richter.