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