Discrete Math Seminars

Most Tuesdays in K9509 - 12:30pm to 1:20pm

Please join us for this weekly seminar on a wide variety of topics under the umbrella of discrete mathematics. We gratefully acknowledge the Pacific Institute of Mathematical Sciences for their generous funding since 2010.

Watch for upcoming Seminars listed below, offered in SCK 9509 and/or on Zoom. We welcome remote participation from groups at other universities.

All talks will be announced on this page, on the department calendar (found at the bottom of the Math homepage), and on the DM Seminar mailing list. If you have an SFU email address, you can subscribe or unsubscribe to the mailing list by logging in to maillist.sfu.ca and searching for the math-dmsem list. Otherwise, you can ask any discrete math faculty member to manually add you to the list. With the permission of the speaker, we will record the talk video and upload it to the SFU Discrete Math Seminar Youtube Channel

Current organizer: Ladislav Stacho & Alexander Clow

2024 Talks

Spring 2024

Date: Tuesday April 09, 2024 Speaker: Kasra Masoudi, SFU Talk Title: A Strict Inequality on the Energy of Edge Partitioning of Graphs

There is an interesting connection between chemistry and graph theory. This connection is highlighted by the relationship between a energy of a molecule and the eigenvalues of its graph. In the 1970s, a chemist named Ivan Gutman introduced a concept to define the energy of graphs, denoted as E(G). Simply put, Gutman’s definition involves adding up the absolute values of the eigenvalues of the graph’s adjacency matrix A.

There exists a famous inequality on the energy of edge partitioning of Graphs, which states that energy of a graphs G is either less than or equal to the sum of the energies of its edge partitions. In this work, we show that in case of the connectivity of G the inequality is strict by using some features of positive semi-definite matrices and the relationship of the partitions with their adjacency matrices.

Date: Tuesday April 02 , 2024 Speaker: Krishna Narayanan, SFU Talk Title: Monitoring Edge-geodetic sets in graphs
We introduce a new graph-theoretic concept in the area of network monitoring. In this area, one wishes to monitor the vertices and/or the edges of a network (viewed as a graph) in order to detect and prevent failures. Inspired by two notions studied in the literature (edge-geodetic sets and distance-edge-monitoring sets), we define the notion of a monitoring edge-geodetic set (MEG-set for short) of a graph G as an edge-geodetic set S Ď VpGq of G (that is, every edge of G lies on some shortest path between two vertices of S) with the additional property that for every edge e of G, there is a vertex pair x,y of S such that e lies on all shortest paths between x and y. The motivation is that, if some edge e is removed from the network (for example if it ceases to function), the monitoring probes x and y will detect the failure since the distance between them will increase. We explore the notion of MEG-sets by deriving the minimum size of a MEG-set for some basic graph classes (trees, cycles, unicyclic graphs, complete graphs, grids, hypercubes, corona products...) and we prove an upper bound using the feedback edge set of the graph. We also show that determining the smallest size of an MEG-set of a graph is NP-hard, even for graphs of maximum degree at most 9.
Date: Tuesday March 26 , 2024 Speaker: Vesna Irsic, University of Ljubljana Talk Title: TBD
 
Date: Tuesday March 05 , 2024 Speaker: Amarpreet Rattan, SFU Talk Title: TBD
 
Date:  Tuesday February 20, 2024   CANCELLED Speaker: Peter Horak, University of Washington Talk Title: Perfect Matchings in Cubic Graphs

In 2008 Alon and Friedland showed that a simple cubic graph G on 2n vertices has at most 6^{n/3} perfect matchings, and this bound is attained by taking the disjoint union of bipartite complete graphs K_{3,3}. In other words, the above theorem says that the complete bipartite graph  K_{3,3} has the highest density of perfect matchings among all cubic graphs; thus the disjoint union of its copies constitutes the extremal graph. However, this result does not provide any insight into the structure of extremal connected cubic graphs.

In this talk it will be presented that for n >= 6, the number of perfect matchings in a simple connected cubic graph on 2n vertices is at most  4f_{n-1}, with f_{n} being the n-th Fibonacci number, and a unique extremal graph will be characterized as well. In addition, it will be shown that the number of perfect matchings in any cubic graph G equals the expected value of a random variable defined on all 2-colorings of edges of G.

In the second part of our talk an improved lower bound on the maximum number of cycles in a cubic graph will be provided.

Tuesday, February 13 , 2024 Sepeaker: Jesse Campion Loth, University of Bristol Talk Title: Symmetry of star factorisations

How many ways are there to write a given permutation as a product of m transpositions (i_1, j_1) (i_2, j_2) \dots (i_m, j_m)?  For example, there are three ways to write (1,2,3) as a product of two transpositions: (1,2)(1,3), (1,3)(2,3) and (2,3)(1,2).  This is an example of a permutation factorisation problem.  There are a broad range of problems of this type, with links to algebraic geometry and graph embeddings.  We will first give an overview of how problems of this type are usually approached using generating functions and character theory.

We then show how a combinatorial approach can be used to give bijections between different classes of permutation factorisation.  In particular, we will present the first fully combinatorial proof of the symmetry of star factorisations, answering a question of Goulden and Jackson [2009].  

This is joint work with Amarpreet Rattan, who will give a seminar on a symmetric function approach to these problems in March.

Date:  Tuesday Feb 06 , 2024 Speaker: Torsten Mutze, University of Warwick Talk Title: Kneser graphs are Hamiltonian

For integers k>=1 and n>=2k+1, the Kneser graph K(n,k) has as vertices all k-element subsets of an n-element ground set, and an edge between any two disjoint sets. It has been conjectured since the 1970s that all Kneser graphs admit a Hamilton cycle, with one notable exception, namely the Petersen graph K(5,2). This problem received considerable attention in the literature, including a recent solution for the sparsest case n=2k+1. The main contribution of our work is to prove the conjecture in full generality. We also extend this Hamiltonicity result to all connected generalized Johnson graphs (except the Petersen graph). The generalized Johnson graph J(n,k,s) has as vertices all k-element subsets of an n-element ground set, and an edge between any two sets whose intersection has size exactly s. Clearly, we have K(n,k)=J(n,k,0), i.e., generalized Johnson graphs include Kneser graphs as a special case. Our results imply that all known families of vertex-transitive graphs defined by intersecting set systems have a Hamilton cycle, which settles an interesting special case of Lovász’ conjecture on Hamilton cycles in vertex-transitive graphs from 1970. Our main technical innovation is to study cycles in Kneser graphs by a kinetic system of multiple gliders that move at different speeds and that interact over time, reminiscent of the gliders in Conway’s Game of Life, and to analyze this system combinatorially and via linear algebra.

This is joint work with my students Arturo Merino (TU Berlin) and Namrata (Warwick).

 

2023 Talks

Fall 2023

Date: Tuesday December 5, 2023 Speaker: Omer Angel, UBC Talk Title: Non-monotonicity for all-in poker tournaments

We consider a simplified model for a poker tournament taking into account only hands where two or more players make the maximal bet of their entire stack.  While the probability of any player being the overall winner is a simple function of the amounts they currently have, the probability of ending up in kth place for any other k is a surprisingly complex function, which we study. 

Joint work with Mark Holmes.

Date:  Tuesday November 28, 2023 Speaker: Yanwen Luo, SFU Talk Title: Spaces of Geodesic Triangulations of Surfaces

In 1962, Tutte proposed a simple method to produce a straight-line embedding of a planar graph in the plane, known as Tutte's spring theorem. This construction provides not only one embedding of a planar graph, but infinite many distinct embeddings of the given graph. This observation leads to a surprisingly simple proof of a classical theorem proved by Bloch, Connelly, and Henderson in 1984 stating that the space of geodesic triangulations of a convex polygon is contractible. In this talk, we will introduce spaces of geodesic triangulations of surfaces, review Tutte's spring theorem, and present this short proof. We will briefly report the recent progress in identifying the homotopy types of spaces of geodesic triangulations of more complicated surfaces. 

This is a joint work with Tianqi Wu and Xiaoping Zhu.

Date: Tuesday November 7, 2023 Speaker: Speaker: Yifan Jing, University of Oxford Talk Title: Measure doubling for sets in locally compact groups

A central problem in additive combinatorics is to obtain a good lower bound for the size of the product set AB of two subsets A, B of a group G. In this talk, we will be focusing on the setting when G is a locally compact group, where G has a natural notion of size: the Haar measure. I will talk about some recent developments and their connections to analysis and geometry, including the resolution of the Inverse Kemperman problem, a non-abelian Brunn-Minkowski inequality, and the confirmation of a conjecture of Breuillard and Green. 

The talk is based on joint work with Chieu-Minh Tran and Ruixiang Zhang.

Date:  Tuesday October 31, 2023 Speaker: Shivaramakrishna Pragada, SFU Talk Title: Subdivision and adjacency spectra of graphs

In this talk, we investigate the asymptotic nature of graph spectra when some edges of a graph are subdivided sufficiently many times. We show that the eigenvalues of the sequences of graphs obtained by subdividing edges are Cauchy. As an application of the main result, we construct a bounded degree graph sequence with (approximate) high second eigenvalue multiplicity. 

This is a joint work with Hitesh Kumar, Bojan Mohar and Hanmeng Zhan.

Date:  Tuesday October 24, 2023 Speaker: Thomas Pender, SFU Talk Title: Balanced Weighing Matrices and Association Schemes

A weighing matrix is a square (-1,0,+1)-matrix with pairwise orthogonal rows such that each row has a constant number of non-zero entries. If upon taking the absolute values of all the entries of a weighing matrix, one obtains an incidence matrix for a symmetric balanced incomplete block design, we say that the weighing matrix is balanced.

In this talk, we construct a new infinite family of balanced weighing matrices. We then show a novel characterization of balanced weighing matrices using association schemes. Finally, we explore analogous relations between more general classes of objects: balanced generalized weighing matrices, quasi-balanced weighing matrices.

This is joint work with Dr. Hadi Kharaghani (University of Lethbridge) and Dr. Sho Suda (National Defense Academy of Japan).

Date:  Tuesday October 3, 2023 Speaker: Shizhe Liang, Brandeis University Talk Title: Grand-Schnyder woods and applications to drawing

In 1990, Schnyder showed that every plane triangulation admits a special partition of its inner edges into 3 trees, which are known as the Schnyder woods. Using this structure, Schnyder designed a straight-line grid drawing algorithm for triangulations. Since then, other structures and algorithms sharing the same flavor have been found by various authors.

In this talk I will present a new construction, named grand-Schnyder woods, that simultaneously generalizes several of these structures (notably the original Schnyder woods, the regular edge labelings of Kant and He, and the d-Schnyder structures of Bernardi and Fusy). Precisely, a grand-Schnyder wood of parameter d is defined on a planar graph which has faces of degree at most d and non-facial cycles of length at least d. It is a set of d spanning forests crossing each other in a specific way. 

Grand-Schnyder woods of parameter d=4 inspires a general framework of drawing algorithms, which unifies several classical algorithms due to Kant and He, Fusy, Barriere & Huemer, and Bernardi & Fusy.

This is a joint work with Olivier Bernardi and Eric Fusy.

Date:  Tuesday September 26, 2023 Speaker: Alexander Clow, SFU Talk Title: Injective and Oriented Colouring Graphs of Bounded Euler Genus

In this talk we consider the injective chromatic index and the oriented chromatic number of graphs with bounded Euler genus. In particular, we present our proofs of a tight (up to the choice of  little o(1)) bound on the injective chromatic index in genus and that the oriented chromatic number is bounded polynomially in genus.  The latter being a major improvement over the previous best upper bound which is exponential in genus. We conclude the talk by discussing directions for future study.

Joint work with Peter Bradshaw (University of Illinois Urbana Champaign), and Jingwei Xu (University of Illinois Urbana Champaign).

Date:  Tuesday September 19, 2023 Speaker: Maxwell Levit, SFU Talk Title: 4-cycle-free covers of Cartesian products of cycles
In order to classify certain small generalized hexagons, Cohen and Tits proved that the d-dimensional hypercube has a unique 2-fold cover with no 4-cycles. I will discuss some reasons I find these covers interesting, including a close connection to Huang's recent proof of the Sensitivity conjecture from computer science.  Then I will give a group-theoretic description of these covers which generalizes nicely to provide 4-cycle-free covers of Cartesian products of p-cycles.

spring 2023

11 Jan
Jesse Campion Loth, SFU Permutations, probability and graph embeddings
Products of permutations are used to model problems in fields ranging from representation theory and algebraic geometry to topological graph theory.  I will show how probability can be used to study such problems.  I will start with some algebraic results on products of symmetric group conjugacy classes.  I will then show how these results can be used to solve natural topological problems.  The main focus of the talk will then be using these random techniques to study how graphs may be embedded on different surfaces.
18 Jan
Shuxing Li, SFU Packings of Partial Difference Sets
As the underlying configuration behind many elegant finite structures, partial difference sets have been intensively studied in design theory, finite geometry, coding theory, and graph theory. In the first part of this talk, I will showcase that partial difference sets are indeed the fundamental structures explaining a series of “two-valued phenomena” in various mathematical branches. The second part concerns the construction of partial difference sets. Over the past three decades, there have been numerous constructions using very dif- ferent and delicate approaches. Surprisingly, we discovered a common frame- work unifying and extending many previous constructions. This is joint work with Jonathan Jedwab.
2 Feb Prof. Dimitri Leemans, Université Libre de Bruxelles The number of string C-groups of high rank

(Joint with Operations Research seminar)

Abstract polytopes are a combinatorial generalisation of  classical objects that were already studied by the greeks. They consist  in posets satisfying some extra axioms. Their rank is roughly speaking  the number of layers the poset has. When they have the highest level of symmetry (namely the automorphism group has  one orbit on the set of maximal chains), they are called regular. One  can then use string C-groups to study them. Indeed, string C-groups are in one-to-one correspondence with  abstract regular polytopes. They are also smooth quotients of Coxeter  groups. They consist in a pair $(G,S)$ where $G$ is a group and $S$ is a  set of generating involutions satisfying a string property and an  intersection property. The cardinality of the set $S$ is the rank of the  string C-group. It corresponds to the rank of the associated polytope.

In this talk, we will give the latest developments on the study of  string C-groups of high rank. In particular, if $G$ is a transitive  group of degree $n$ having a string C-group of rank $rgeq (n+3)/2$, work  over the last twelve years permitted us to show that $G$ is necessarily the symmetric group $S_n$.

We have just proven in the last months that if $n$ is large enough,  up to isomorphism and duality, the number of string C-groups of rank  $r$ for $S_n$ (with $rgeq (n+3)/2$) is the same as the number of string  C-groups of rank $r+1$ for $S_{n+1}$. This result and the tools used in its proof, in particular the rank  and degree extension, imply that if one knows the string C-groups of  rank $(n+3)/2$ for $S_n$ with $n$ odd, one can construct from them all  string C-groups of rank $(n+3)/2+k$ for $S_{n+k}$ for any positive integer $k$. The classification of the string C-groups of rank $rgeq (n+3)/2$  for $S_n$ is thus reduced to classifying string C-groups of rank $r$ for  $S_{2r-3}$. A consequence of this result is the complete classification of all  string C-groups of $S_n$ with rank $n-kappa$ for $kappain{1,ldots,6}$,   when $ngeq 2kappa+3$, which extends previous known results. The number of string C-groups of rank $n-kappa$, with $ngeq 2kappa  +3$, of this classification gives the following sequence of integers  indexed by $kappa$ and starting at $kappa = 1$.

$$Sigma{kappa}=(1,1,7,9,35,48).$$
This sequence of integers is new according to the On-Line Encyclopedia of Integer Sequences.

Joint work with Peter J. Cameron (University of St Andrews) and Maria Elisa Fernandes (University of Aveiro)

8 Feb Curtis Bright, University of Windsor SAT Solvers, Isomorph-free Generation, and the Quest for the
Minimum Kochen–Specker System
I will describe a new approach for exhaustively generating combinatorial objects by combining a satisfiability (SAT) solver with an isomorph-free exhaustive generation method such as orderly generation. The SAT solver is able to limit the search to objects that satisfy given criteria, while the isomorph-free generation method ensures that the objects are generated up to isomorphism. The combined search procedure performs orders-of-magnitude faster than a pure SAT or pure computer algebraic approach, as the SAT solver tailors the search to the object in question while the isomorph-free generation avoids duplication of work when the search space is highly symmetrical.

As a motivating example, I will discuss how this approach can be applied to search for Kochen-Specker (KS) systems, an important combinatorial object arising in quantum physics.  For example, a KS system is at the heart of the "KS Theorem" which intuitively states that a quantum observation cannot be understood as revealing a pre-existing value, and the "Free Will Theorem" which intuitively states that if humans have free will then so must quantum particles.

Since 1990, the smallest known KS system in three dimensions has contained 31 vectors and much effort has been expended trying to find a KS system of smaller size.  An exhaustive computer search in 2016 was able to disprove the existence of a KS system of 21 or fewer vectors. Our SAT and orderly generation approach is over 25,000 times faster than the previously used approach and has also ruled out the existence of a KS system with 22 vectors.

This work is joint with Zhengyu Li and Vijay Ganesh (University of
Waterloo).
15 Feb Stephen Kobourov, University of Arizona Contact Representation of Planar Graphs in 2D and 3D
In a proportional contact representation of a planar graph, each vertex is represented by a simple polygon with area proportional to a given weight, and edges are represented by adjacencies between the corresponding pairs of polygons. We show how to use Schnyder realizers and canonical orders for planar graphs to obtain different types of contact representations. Specifically, we describe an algorithm that constructs proportional contact representation for
arbitrary planar graphs using 10-sided rectilinear polygons. We also describe a construction with 8-sided polygons, which is optimal in terms of polygonal complexity, as 8-sided polygons are sometimes necessary. In 3D vertices are represented by polytopes and edges by contacts between the corresponding polytopes contacts. We show that planar 3-trees have contact representations with cubes and proportional contact representations with boxes.
8 Mar Harmony Zhan, SFU On trees with extremal second largest eigenvalues
We will characterize members that maximize/minimize the second largest adjacency eigenvalue in certain families of trees. Joint work with H. Kumar, B. Mohar and S. Pragada.
15 Mar Zhilin Ge, SFU Hamiltonicity of Covering Graphs of Trees
We consider covering graphs obtained by lifting trees as voltage graphs over cyclic groups. We generalize a tool of Hell, Nishiyama, and Stacho, known as the billiard strategy, for constructing Hamiltonian cycles in the covering graphs of paths. The presentation will show that our extended tool can be used to provide new sufficient conditions for the Hamiltonicity of covering graphs of trees that are similar to those of Batagelj and Pisanski and of Hell, Nishiyama, and Stacho. Next, we focus specifically on covering graphs obtained from trees lifted as voltage graphs over cyclic groups Zp of large prime order p. The presentation will show that for a given reflexive tree T with random nonzero voltage labels from Zp on its edges, the corresponding lift is almost surely Hamiltonian for a large enough prime-ordered cyclic group Zp. Finally, we show that if a reflexive tree T is lifted over a group Zp of a large prime order, then for any assignment of nonzero elements of Zp to the edges of T, the corresponding cover of T has a large circumference. 
5 Apr Alexandra Wesolek, SFU
Cops and Robber Game on Surfaces of Constant Curvature
Recently, Mohar introduced a variant of the cops and robber game that is played on geodesic spaces. In this talk we discuss the rules of the game and strategies for the players when the game is played on compact surfaces of constant curvature, in particular surfaces of negative constant curvature. Joint work with Vesna Iršič and Bojan Mohar.
14 Apr Daniel Panario, Carleton University The Dynamics of Iterating Functions over Finite Fields
When we iterate functions over finite structures, there is an underlying natural functional graph. For a function $f$ over a finite field $\mathbb{F}_q$, this graph has $q$ nodes and a directed edge from vertex $a$ to vertex $b$ if and only if   $f(a)=b$. It is well known, combinatorially, that functional graphs are sets of connected components, components are directed cycles of nodes, and each of these nodes is the root of a directed tree.   The study of iterations of functions over a finite field and their corresponding functional graphs is a growing area ofresearch, in part due to their applications in cryptography and integer factorization methods like Pollard rho algorithm.  Some functions over finite fields when iterated present strong symmetry properties. These symmetries allow mathematical proofs of some dynamical properties such as period and preperiod of a   generic element, (average) ``rho length'' (number of iterations until a cycle is formed), number of connected components, cycle lengths, and permutational properties (including the cycle decomposition).   We survey the main problems addressed in this area so far. We briefly comment on ongoing research about the functional graph of generalized cyclotomic mappings of finite fields. We study periodic points, cycle structure, and rooted trees attached to periodic points. We briefly comment on some open problems.   Based on joint works with Alexander Bors (Carleton, Canada), Rodrigo Martins (UTFPR, Brazil), Claudio Qureshi (UdelaR, Uruguay), Lucas Reis (UFMG, Brazil) and Qiang (Steven) Wang (Carleton, Canada).  

 

2022 Talks

Fall 2022

07 Oct
Special Time: 11am
Bojan Mohar. Simon Fraser University Beyond the Four-Color Theorem
The speaker will discuss the Four-Color Theorem and some of the outstanding problems left open after the proof.
14 Oct
Peter Bradshaw, Simon Fraser University A small step forward in bipartite list coloring
The choosability of a graph G is the minimum value k such that G has a proper list coloring whenever each vertex of G has a list of k colors. Molloy showed that if G is a triangle-free graph of maximum degree d, then the choosability of G is at most (1 + o(1)) d / log d and that this bound is tight within a factor of roughly 2. It is widely believed that this upper bound can be greatly improved in the special case that G is bipartite, and Alon and Krivelevich conjectured an upper bound of O(log d) in this case. However, little progress has been made toward solving this conjecture, and it is currently unknown whether the optimal upper bound for bipartite graphs is different from the optimal upper bound for triangle-free graphs.
In this talk, we will use a modification of a coupon-collector argument from Alon, Cambie, and Kang to show that every bipartite graph of maximum degree d has choosability at most 0.797 d / log d. Our result provides strong evidence that the list-coloring problem is fundamentally easier in bipartite graphs than in triangle-free graphs and hence takes an important step toward solving the conjecture of Alon and Krivelevich. (The content of this talk is part of ongoing work with Bojan Mohar and Ladislav Stacho.)
21 Oct Harmony Zhan, Simon Fraser University An introduction to discrete quantum walks
A discrete quantum walk is determined by a unitary matrix representation of a graph. In this talk, I will give an overview of different quantum walks, and show how the spectral information of the unitary matrix representation links properties of the walks to properties of the graphs. Part of this talk will be based on the book, Discrete Quantum Walks on Graphs and Digraphs, by Chris Godsil and me.
28 Oct Zhouningxin Wang Circular flows in mono-directed Eulerian signed graphs
In this talk, we consider analogs of Jaeger's circular flow  conjecture and its dual Jaeger-Zhang conjecture in signed graphs. We  will first give the notions of circular coloring and circular flow in  signed graphs, and then show that every (6k-2)-edge-connected Eulerian signed graph admits a circular 4k/(2k-1)-flow and that every  signed bipartite planar graph of negative-girth at least 6k-2 admits a  circular 4k/(2k-1)-coloring (equivalently, admits a homomorphism to a  negative cycle of length 2k). We also provide some recent results about circular flow indices of signed graphs with  high edge-connectivities. 
This is based on joint work with Jiaao Li, Reza Naserasr, and Xuding Zhu.
4 Nov Dong Ye, Middle Tennessee State University Nowhere-zero Z3-flow and sign-circuit covering
In 1950s, Tutte discovered that the map-coloring problem on orientable surface could be interpreted as an integer flow problem. A classic result of Tutte states that a graph with a nowhere-zero Z3-flow has a circuit cover which covers every edge at most twice, and hence has a shortest circuit cover with length at most 4/3 of the total number of edges. For an orientable graphs on non-orientable surfaces, its dual is a signed graph. In this talk, we focus on nowhere-zero Z3-flows and circuit covers of signed graphs, extending Tutte’s result from graph to signed graphs. This is based on joint work with Jiaao Li and Yezhou Wu.
18 Nov Daniel Neuen, SFU Parameterized Algorithms for Graph Isomorphism - Decompositions via Regularity
In the first part of the talk, I will give an overview of recent advances on the graph isomorphism problem focusing on quasi-polynomial parameterized algorithms with a running time of the form n^{polylog(k)}, where k is some graph parameter. The first such algorithm was obtained for k being the maximum degree of the input graphs [FOCS 2018] by extending the group-theoretic tools of Babai's quasi-polynomial time isomorphism test [STOC 2016]. Subsequently, this result was generalized in a series of works to all graphs that exclude the complete graph on k vertices as a topological subgraph [SODA 2022]. In particular, this includes all graphs of Euler genus at most k-7 as well as all graphs of tree-width at most k-2.  The key concept underlying this latest algorithm is the notion of t-CR-bounded graphs that serves as a gateway to combine the group-theoretic tools underlying the isomorphism test for bounded-degree graphs with decomposition-based approaches for graphs that exclude the complete graph on k vertices as a topological subgraph. In the second part of the talk, we explore the graph-theoretic side of the algorithm in more depth and discuss how regularity of the input graphs can be leveraged to obtain decompositions into parts with few symmetries that can then be handled by the group-theoretic graph isomorphism machinery.
25 Nov Jonathan Jedwab, SFU Constructions of difference sets in groups of order $4^d$
The study of difference sets lies at the intersection of design theory, coding theory, finite geometry, and algebraic number theory. The central problem is to determine which groups contain at least one difference set, and the richest existence results occur when the group order is a power of 4. The principal obstacles are that the number of such groups grows rapidly, and that the groups have such diverse structures that an overall theory seems out of reach. However, after a ten-­year collaboration, this question was resolved completely for all 56,092 groups of order 256 using a new theoretical framework together with computational search. I shall describe the history of this problem, the methods used to resolve order 256, and the prospects for extending these techniques to order 1024.

Spring 2022

18 Jan  (ZOOM) Jiaxi Nie, University of California San Diego On Asymptotic Packing of Geometric Graphs
A set of geometric graphs is geometric-packable if it can be asymptotically packed into every sequence of drawings of the complete graph $K_n$. For example, the set of geometric triangles is geometric-packable due to the existence of Steiner Triple Systems. When G is the 4-cycle (or 4-cycle with a chord), we show that the set of plane drawings of G is geometric-packable. In contrast, the analogous statement is false when G is nearly any other planar Hamiltonian graph (with at most 3 possible exceptions). A convex geometric graph is convex-packable if it can be asymptotically packed into the convex drawings of the complete graphs.  For each planar Hamiltonian graph G, we determine whether or not a plane G is convex-packable. Many of our proofs explicitly construct these packings; in these cases, the packings exhibit a symmetry that mirrors the vertex transitivity of $K_n$.  
 here is the link. (ID: 668 0051 2140, password: Graph)
25 Jan Kathryn Nurse, Simon Fraser University Toward Bouchet’s conjecture on nowhere-zero flows in signed graphs.
I will present a work in progress. In 1954, Tutte proved flow-colouring duality and made a conjecture that every graph without a cut-edge has a nowhere-zero 5-flow. A parallel conjecture to this, but for signed graphs is Bouchet's conjecture (1983) that every signed graph without the obvious obstruction has a nowhere-zero 6-flow. We have been able to show that Bouchet's conjecture holds for 3-connected graphs when 6 is replaced with 8. This is joint with Matt DeVos and Robert Šámal.
01 Feb Annie Raymond (UMass) Tropicalization of graph profiles
The number of homomorphisms from a graph H to a graph G, denoted by hom(H;G), is the number of maps from V(H) to V(G) that yield a graph homomorphism, i.e., that map every edge of H to an edge of G. Given a fixed collection of finite simple graphs {H_1, ..., H_s}, the graph profile is the set of all vectors (hom(H_1; G), ..., hom(H_s; G)) as G varies over all graphs.  Graph profiles essentially allow us to understand all polynomial inequalities in homomorphism numbers that are valid on all graphs. Profiles can be extremely complicated; for instance the full profile of any triple of connected graphs is not known. To simplify these objects, we introduce their tropicalization which we show is a closed convex cone that still captures interesting combinatorial information. We explicitly compute these tropicalizations for some sets of graphs, and relate the results to some questions in extremal graph theory. This is joint work with Greg Blekherman, Mohit Singh and Rekha Thomas.
08 Feb Vesna Iršič (Simon Fraser University) Winning vs. catching in the game of cops and robber on manifolds
Recently, Mohar introduced a variant of the cops and robber game that is played on geodesic spaces. The game combines properties of pursuit-evasion games with the classical cops and robber game played on graphs. In the game, cops win if they can get arbitrarily close to the robber. On the other hand, cops catch the robber if one of them occupies the same point as the robber. In this talk we will discuss several strategies for players in the game, and observe the difference between the number of cops needed to catch the robber and the number of cops needed to win the game. Joint work with Bojan Mohar and Alexandra Wesolek.
15 Mar Bojan Mohar (Simon Fraser University) Proper orientations and proper chromatic number
It is an interesting (and not entirely obvious) fact that every graph admits an orientation of its edges so that the outdegrees at vertices form a "coloring" (outdegrees of any two adjacent vertices are different).
The proper chromatic number $\Vec{\chi}(G)$ of a graph $G$ is the minimum $k$ such that there exists an orientation of the edges of $G$ with all vertex-outdegrees at most $k$ and such that for any adjacent vertices, the outdegrees are different. Two major conjectures about the proper chromatic number are resolved. First it is shown, that $\Vec{\chi}(G)$ of any planar graph $G$ is bounded (in fact, it is at most 14). Secondly, it is shown that for every graph, $\Vec{\chi}(G)$ is at most $O(\frac{r\log r}{\log\log r})+\tfrac{1}{2}\MAD(G)$, where $r=\chi(G)$ is the usual chromatic number of the graph, and $\MAD(G)$ is the maximum average degree taken over all subgraphs of $G$. Several other related results are derived. Our proofs are based on a novel notion of fractional orientations.
This is joint work with Yaobin Chen and Hehui Wu.
05 Apr Zdenek Dvorak (Charles University) 3-coloring near-quadrangulations of the plane and the torus using flows
(joint work with C. Bang, E. Heath, and B. Lidicky)
A graph drawn in a surface is a k-near-quadrangulation if the product of the lengths of its faces, except for 4-faces, is at most k. Near-quadrangulations play a fundamental role in the theory of 3-colorability of triangle-free graphs on surfaces.  We show how the well-known duality between colorings and flows can be used to design

* a 3-precoloring extension algorithm for k-near-quadrangulations of the plane, and
* a 3-coloring algorithm for k-near-quadrangulations of the torus,

with time complexity polynomial in k and the number of vertices.

2021 Talks

Fall 2021

09 Nov
Andrei Bulatov, Simon Fraser University
The complexity of counting homomorphisms
The Constraint Satisfaction Problem (CSP) provides a general framework for a wide range of combinatorial problems. The simplest way to state the problem is: Given relational structures (say, graphs) G and H, decide if there is a homomorphism from G to H. The counting version of the CSP, #CSP, asks for the number of such homomorphisms. In order to represent specific problems, the CSP is often restricted in various ways, in particular by fixing the target structure H. Thus, CSP(H) asks if, for a given structure G, there is a homomorphism from G to H. If H is a graph such a problem is often called H-Coloring. The counting versions #CSP(H), #H-Coloring of these problems are defined accordingly.
In this talk we survey the developments in the study of the complexity of #CSP(H) that eventually led to a complete classification of such problems and their various generalizations.   ZOOM Information: https://sfu.zoom.us/j/66800512140?pwd=N011dU5ZNThSWnVzMFBjYnBidDdmUT09  (ID: 668 0051 2140  Password: Graph)
16 Nov Peter Bradshaw, Simon Fraser University A rainbow connectivity threshold for random graph families
Given a family G of graphs on a common vertex set X, we say that G is rainbow connected if for every vertex pair u, v ∈ X, there exists a path from u to v that uses at most one edge from each graph of G. We consider the case that G contains s graphs, each sampled randomly from G(n, p), with n = |X| and p = c log n / sn , where c > 1 is a constant. We show that there exists a threshold of at most three consecutive integer values such that when s is greater than or equal to this threshold, G is a.a.s. rainbow connected, and when s is below this threshold, G is a.a.s. not rainbow connected. Joint work with Bojan Mohar.

Summer 2021

19 May
Joy Morris, University of Lethbridge
Lexicographic products and wreath products
Abstract: I will present a history and overview of some of the work that has been done on the lexicographic product of graphs, and related generalisations. The focus of my talk will be on the automorphism groups of such graphs, and the relationship to the wreath product of permutation groups.
2 June
Xiang-dong Hou, University of South Florida
On the number of equivalence classes of boolean functions
Abstract: Two Boolean functions from $\Bbb F_2^n$ to $\Bbb F_2$ are called (affine) equivalent if one can be obtained from the other through an invertible affine transformation of the variables followed by an addition of an affine function. Most coding theoretic and cryptographic properties of Boolean functions are preserved under this equivalence. Let $N_n$ denote the number of equivalence classes of Boolean functions in $n$ variable. No explicit formula for $N_n$ is known. A long-standing open question by MacWilliams and Sloane asks for an asymptotic formula for $N_n$ as $n\to\infty$. Recently, we find a solution to this question. (Abstract in PDF)
8 June
*Tuesday @ 2 pm*
Special session for the Round the World Relay in Combinatorics
Fan Chung, University of California San Diego 
Trees and forests in Green's functions of a graph

Abstract: The Green's functions of a graph are the pseudo inverses of the Laplacians and therefore are useful for solving many types of Laplace equations in discrete settings.In this talk, we will give  combinatorial interpretations of Green's functions in terms of counting trees and forests in a graph. We will also mention several applications concerning the pagerank algorithms and the hitting time for random walks.

16 June
Akbar Rafiey, SFU
Fast and Private Submodular and k-Submodular Functions Maximization with Matroid Constraints
Abstract: The problem of maximizing nonnegative monotone submodular functions under a certain constraint has been intensively studied in the last decade, and a wide range of efficient approximation algorithms have been developed for this problem. Many machine learning problems, including data summarization and influence maximization, can be naturally modeled as the problem of maximizing monotone submodular functions. However, when such applications involve sensitive data about individuals, their privacy concerns should be addressed.
In this paper, we study the problem of maximizing monotone submodular functions subject to matroid constraints in the framework of differential privacy. We provide (1−1/e)-approximation algorithm which improves upon the previous results in terms of approximation guarantee. This is done with an almost cubic number of function evaluations in our algorithm. Moreover, we study k-submodularity, a natural generalization of submodularity. We give the first 1/2-approximation algorithm that preserves differential privacy for maximizing monotone k-submodular functions subject to matroid constraints. The approximation ratio is asymptotically tight and is obtained with an almost linear number of function evaluations.
Joint work with Yuichi Yoshida (http://proceedings.mlr.press/v119/rafiey20a.html)
23 June
Rebecca Patrias, University of St Thomas
Webs and tableau promotion
Abstract: We will start with an introduction to webs, standard Young tableau promotion, and the relationship between web rotation and tableau promotion. We will then discuss increasing tableaux---a K-theoretic analogue of SYT---and K-promotion. A big open question in this area deals with the order of K-promotion on increasing tableaux. We will talk about results in the 3-row case (in joint work with O. Pechenik) as well as current efforts to relate this problem to web promotion (joint with O. Pechenik, J. Striker, and J. Tymoczko). 
30 June
Haggai Liu
Enumerative Properties of Cogrowth Series on Free products of Finite Groups
Abstract: Given a group G with a finite set of generators, S, it is natural to ask if the product of n generators from S evaluate to the identity. The enumerative version of this problem, known as the cogrowth problem, counts the number of such products and studies the associated counting sequence. Many cogrowth sequences are known. We focus on the free products of finite groups: Specifically, cyclic and dihedral groups. Such groups have the property that their cogrowth generating functions are algebraic functions, and thus, are solutions to implicit polynomial equations. Using algebraic elimination techniquesand free probability theory, we establish upper bounds on the degrees of the polynomial equations that they satisfy. This has implications for asymptotic enumeration, and makes it theoretically possible to determine the functions explicitly.
7 July
Christin Bibby, Louisiana State University
Combinatorics of orbit configuration spaces
Abstract: From a group action on a space, define a variant of the configuration space by insisting that no two points inhabit the same orbit. When the action is almost free, this "orbit configuration space" is the complement of an arrangement of subvarieties inside the cartesian product, and we use this structure to study its topology. We give an abstract combinatorial description of its poset of layers (connected components of intersections from the arrangement) which turns out to be of much independent interest as a generalization of partition and Dowling lattices. The close relationship to these classical posets is then exploited to give explicit cohomological calculations. 
14 July
Yifan Jing, UIUC
Minimal and nearly minimal measure expansions in locally compact groups
Abstract: In 1964, Kemperman proved the following continuous nonabelian counterpart of the Cauchy-Davenport theorem: If G is a connected unimodular locally compact group with a left (and hence right) Haar measure \mu, A, B \subseteq G are nonempty and compact, and AB is their product set, then \mu(AB) \geq \min\{ \mu(A) + \mu(B), \mu(G)\}. 
I will present the recent joint works with Jinpeng An, Chieu-Minh Tran and Ruixiang Zhang where we determine the conditions for the equality to happen or nearly happen in the above inequality. Our results and methods answer several questions by Griesmer, Henstock, Hrushovski, Kemperman, Macbeath, McCrudden, and Tao.
21 July
Sophie Spirkl, Waterloo
The complexity of list-5-colouring with a forbidden induced sugbraph
Abstract: A k-list-assignment for a graph G is a function L from V(G) to the set of subsets of {1,…,k}. The list-k-colouring problem asks, given G and a k-list-assignment L, is there a colouring f of G with f(v) in L(v) for all v in V(G)? This generalizes the k-colouring problem (where we use L(v)={1,…,k} for every vertex). For k at least 3, both k-colouring and list-k-colouring are NP-hard, which motivates studying the complexity of these problems when the input is restricted to H-free graphs (for a fixed H, excluded as an induced subgraph).
I will present an algorithm for list-5-colouring restricted to H-free graphs for all H which consist of connected components each of which is a 3-vertex path. This, together with previous results, gives a complete answer to the question, “for which H is list-5-colouring restricted to H-free graphs NP-hard? Joint work with Sepehr Hajebi and Yanjia Li.
28 July
Anurag Bishnoi, TU Delft
The minimum degree of minimal Ramsey graphs for cliques
Abstract: In this talk we will present a new upper bound of $s_r(K_t) = O(t^5r^{5/2})$ on the Ramsey parameter $s_r(K_t)$ introduced by Burr, Erd\H{o}s and Lov\'{a}sz in 1976, which is defined as the smallest minimum degree of a graph $G$ such that any $r-colouring of the edges of $G$ contains a monochromatic $K_t$, whereas no proper subgraph of $G$ has this property. This improves the previous upper bound of $s_r(K_t) = O(t^6r^3)$ proved by Fox et al. The construction used in our proof relies on a group theoretic model of generalised quadrangles introduced by Kantor in 1980.
This is joint work with John Bamberg and Thomas Lesgourgues (https://arxiv.org/abs/2008.02474).

Spring 2021

20 January
Peter Bradshaw, SFU
Flexible list colorings in graphs of bounded degree
Abstract: For a given $\epsilon > 0$, we say that a graph $G$ is $\epsilon$-flexibly $k$-choosable if the following holds: for any assignment $L$ of lists of size $k$ on $V(G)$, if a preferred color is requested at any set $R$ of vertices, then at least $\epsilon |R|$ of these requests are satisfied by some $L$-coloring. We characterize the graphs of maximum degree $\Delta$ that are $\epsilon$-flexibly $\Delta$-choosable for some $\epsilon = \epsilon(\Delta) > 0$, which answers a question of Dvořák, Norin, and Postle [List coloring with requests, JGT 2019]. In particular, we show that for any $\Delta\geq 3$, any graph of maximum degree $\Delta$ that is not isomorphic to $K_{\Delta+1}$ is $\frac{1}{2 \Delta^3}$-flexibly $\Delta$-choosable.
This is joint work with Ladislav Stacho and Tomáš Masařík.
27 January
*10am Start*
Ambat Vijayakumar, Cochin University of Science and Technology, India
Distance spectrum of graphs - some recent studies
Abstract: The distance matrix of a connected graph G is an n × n matrix $D(G) = [d_{ij}]$, where $d_{ij}$ is the distance between the vertices $v_i$ and $v_j$ . The distance spectrum of G is ${\lambda_1, . . . , \lambda_n}$, where $\lambda_i$'s are the eigenvalues of D(G). The distance energy of G is defined by $E_D(G) = \sum_{i=1}^n |\lambda_i|$. The distance matrix, dstance eigenvalue, and distance energy of a connected graph have been studied intensively in literature. We discuss a new problem of how the distance energy changes when an edge is deleted. Similar problem for adjacency energy of a graph was studied by Day and So. It turns out that the results for distance energy change and adjacency energy change are quite different. It follows that, for any connected graph with a unique positive eigenvalue, the deletion of any edge increases the distance energy provided that the resulting graph is still connected. We prove that the distance energy of a complete bipartite graph is always increased when an edge is deleted even though it has two positive distance eigenvalues. Also, we give a set of examples of connected graph whose distance energy decreases when a specific edge is deleted. This is a joint work with G. Indulal and A. Varghese.
3 February
Damanvir Binner, SFU
Proofs of Berkovich and Uncu conjectures regarding partition inequalities
Abstract: We use techniques from elementary number theory (such as Frobenius Numbers) to combinatorially prove four recent conjectures of Berkovich and Uncu (Ann. Comb. 23 (2019) 263–284) regarding inequalities between the sizes of two closely related sets consisting of integer partitions whose parts lie in the interval {s, . . . , L+s}. Further restrictions are placed on the sets by specifying impermissible parts as well as a minimum part.  (Joint work with A. Rattan)   
10 February
Pengyu Liu, SFU
Polynomial tree-based analysis
Abstract: We define a graph polynomial for unlabeled trees and show that the polynomial is a complete isomorphism invariant for unlabeled trees. We also demonstrate some applications of the tree distinguishing polynomial in tree-based analysis with examples in life sciences and linguistics.
17 February  Reading Break
 
24 February
Harmony Zhan, York University
Arc-reversal quantum walks
Abstract: A discrete quantum walk usually takes place on the arcs of a graph. Each step of the walk consists of two operations - a "coin flip" and an "arc shift". In this talk, we will consider quantum walks where the "arc shift" simply reverses each arc. Using different coins, I will show the connection of these walks to various graph structures, such as line digraphs, covers and embeddings. 
2 March
*TuesDAY @ 11:30-13:30*
SpeCial Session: Nancy Ann Neudauer, Pacific University
Being Together and Better: Building, Belonging,and Giving Back to Mathematical Communities
Abstract: What have I learned about building mathematical communities over the last twenty years, initially in North America and more recently in Africa and South America? What does “belonging” mean to those who are already part of a mathematical community, and how can we provide the sort of welcome we once received (or would have liked to receive)? What constructive actions can we take to help mathematics students transition to a research-based academic career, and how might these differ when the students are located in developing countries without access to established infrastructure? Dr. Neudauer will discuss these and other questions in a special session of the SFU Discrete Mathematics Seminar, intended for students and faculty at all career stages. She will share stories and insights gained from decades of service to the mathematical community as a researcher, teacher, mentor, and organizer.
10 March
Zeying Wang, Michigan Tech
Partial difference sets in abelian groups
Abstract: Recently we proved a theorem for  strongly regular graphs  that provides numerical restrictions on the number of fixed vertices and the number of vertices  mapped to adjacent vertices under an automorphism. We then used this result to develop some new techniques to study regular partial difference sets in abelian groups. We have proved several non-existence results and classification results of partial difference sets in abelian groups. Also we completely answered the question "For which odd positive integer $v>1$, can we find a Paley type partial difference set in an abelian group of order $v$?", a classical question from the 1990s.  In this talk I plan to give an overview of these results.
17 March
Riana Roux, Stellenbosch University
A localization game on graphs
Abstract: The classic game of cops and robbers on a graph is a pursuit-evasion game introduced in the late 1970's. In the original game the cops and robber take turns to either stay at their present vertex or move to an adjacent vertex. The cops win the game if at any moment a cop occupies the same vertex as the robber. In this talk we will consider a game where the robber is invisible and where the cop only has to locate the robber, that is, the cop does not have to be on the same vertex as the robber to win. This game is called the localization game and consist of two players: a team of k cops and a robber. The game starts with a robber occupying some vertex on the underlying graph. The cop team then probes k vertices and receives the distance of the robber to each of these probed vertices. If the cop can deduce the robber’s location from this information he wins, otherwise the robber may move to an adjacent vertex and the cop again probes k vertices. If the cop can locate the robber in a finite number of turns, the cop wins. Otherwise, the robber wins. The localization number of a graph is the smallest k for which the cop wins. During this talk we will discuss some basic results regarding the localization number, ideas around forbidden subgraphs and the game played on specific graphs classes.
24 March
Daniel Panario, Carleton University
Finite fields in combinatorial arrays: constructions and applications
Abstract: We discuss constructions based on finite fields of three types of combinatorial arrays: orthogonal, covering and ordered orthogonal arrays. Other combinatorial arrays have been similarly considered in the literature, including permutation arrays, frequency permutation arrays, hypercubes and Costas arrays. In this talk, for each of these arrays, we briefly explain constructions based on finite fields, and main applications. 
An Orthogonal Array (OA) of strength $t$ on $v$ symbols is an array with the property that, for every $t$-combination of column vectors, every one of the possible $v^t$ $t$-tuples of symbols appears as a row ``exactly'' once in the subarray defined by these column vectors. OAs have been applied in coding theory and in cryptography. They are equivalent to MDS (maximum distance separable) codes where the strength of the OA is closely related to the minimum distance of the code. OAs are also closely related to secret sharing in cryptography. An Ordered Orthogonal Arrays (OOA) is a generalization of OAs where the coverage property applies to some selected columns of the array. Similarly, a Covering Array of strength $t$ on $v$ symbols is an array with the property that, for every $t$-combination of column vectors, every one of the possible $v^t$ $t$-tuples of symbols appears as a row ``at least'' once in the subarray defined by these column vectors. Covering arrays are used to reduce the number of tests in application areas such as software testing and group testing.
A common theme on several recent constructions of these arrays is the use of linear feedback shift register (LFSR) sequences and finite fields. Arrays whose rows are cyclic shifts of a sequence over a finite field possess many combinatorial properties. They have been used to build arrays attaining a high number of $t$-subsets of columns with the desired ``coverage property''. We provide examples of applications of these combinatorial arrays. 
talk slides
31 March
Tomáš Masařík, SFU
Optimal discretization is fixed-parameter tractable
Abstract: Given two disjoint sets W_1 and W_2 of points in the plane, the Optimal Discretization problem asks for the minimum size of a family of horizontal and vertical lines that separate W_1 from W_2, that is, in every region into which the lines partition the plane there are either only points of W_1, or only points of W_2, or the region is empty. Equivalently, Optimal Discretization can be phrased as a task of discretizing continuous variables: we would like to discretize the range of x-coordinates and the range of y-coordinates into as few segments as possible, maintaining that no pair of points from W_1×W_2 are projected onto the same pair of segments under this discretization.
We provide a fixed-parameter algorithm for the problem, parameterized by the number of lines in the solution. Our algorithm works in time 2^O(k^2 log(k))n^O(1), where k is the bound on the number of lines to find and n is the number of points in the input. Our result answers in positive a question of Bonnet, Giannopolous, and Lampis [IPEC 2017] and of Froese [PhD thesis, 2018] and is in contrast with the knownintractability of two closely related generalizations: the Rectangle Stabbing problem and the generalization in which the selected lines are not required to be axis-parallel.
Joint work with: Stefan Kratsch, Irene Muzi, Marcin Pilipczuk, Manuel Sorge
7 April
Amy Wiebe, Free University of Berlin
A combinatorial approach to Minkowski tensors of polytopes
Abstract: Intrinsic volumes of a convex body provide scalar data (volume, surface area, Euler characteristic, etc. ) about the geometry of a convex body independent of the ambient space.
Minkowski tensors are the tensor-valued generalization of intrinsic volumes. They provide more complex geometric information about a convex body, such as its shape, orientation, and more. Minkowski volume tensors are closely linked to the moments of the uniform distribution on a convex body, and a rational generating function for these moments allows us to extract the tensors symbolically. In this talk, we explain this connection and show that it can be extended to the setting of Minkowski "surface tensors". We demonstrate how this generating function approach allows us to give an explicit formula for these surface tensors in the case of simplicial polytopes.
No prior knowledge of Minkowski tensors will be assumed.
This is a joint work with Büşra Sert and Niklas Livchitz
14 April
Carolyn Chun, United States Navel Academy
Graphs and binary matroids whose odd circuits all have size three or five
Abstract: Graphs with no odd circuits are well understood.  In 1992, Maffray characterized all graphs whose odd circuits only have size three.  Oxley and Wetzler generalized this result to binary matroids in 2016.  We give a complete characterization of all binary matroids whose odd circuits all have size three or five, as well as the graphs whose odd cycles all have size three or five.  This talk is based on joint work with Oxley and Wetzler. 
talk slides

2020 Talks

Fall 2020

16 September Marthe Bonamy, LaBRI On Vizing's edge colouring question
In his 1965 seminal paper on edge colouring, Vizing proved that a (Delta+1)-edge colouring can be reached from any given proper edge colouring through a series of Kempe changes, where Delta is the maximum degree of the graph. He concludes the paper with the following question: can an optimal edge colouring be reached from any given proper edge colouring through a series of Kempe changes? In other words, if the graph is Delta-edge-colourable, can we always reach a Delta-edge-colouring? If true, this would imply a more recent conjecture of Mohar (2006) that in any graph, all (Delta+2)-edge-colourings are equivalent up to a series of Kempe changes. We discuss recent progress around these questions.
23 September Carla Groenland, University of Oxford Asymptotic dimension of graph classes
I will attempt to give some intuition for asymptotic dimension of graph classes, starting from the definition and giving the connection to clustered colouring and weak-diameter network decompositions. I will sketch the ideas behind some of our results, e.g. that the class of planar graphs has asymptotic dimension 2. Asymptotic dimension was introduced by Gromov in 1993 within geometric group theory and in the graph setting makes sense for infinite graphs or graph classes. Joint work with M. Bonamy, N. Bousquet, L. Esperet, F. Pirot, and A. Scott.
30 September Karen Yeats, University of Waterloo Chains of hourglasses and the graph theory of their Feynman integrals
I will give a set up for understanding the graph theory of Feynman integrals that I have been using over the last number of years. It is all very combinatorial and does not require any understanding of physics or analysis. Then I will explain about some joint work with Oliver Schnetz where we are able to complete a generalized denominator reduction on a particular family of graphs and from this calculate an arithmetic graph invariant on them known as the c_2 invariant as well as understand properties of their Feynman integrals.
7 October Shanise Walker, University of Wisconsin Eau Claire The Game of Cycles
The Game of Cycles was introduced by Francis Su in his book titled Mathematics for Human Flourishing (2020). The game is played on a simple connected planar graph together with its bounded cells, and players take turns marking edges with arrows according to a sink-source rule. The object of the game is to produce a cycle cell–a cell surrounded by arrows all cycling in one direction–or to make the last possible move. In this talk, we explore the two-player game for various classes of graphs and determine who has a winning strategy.
14 October Laura Escobar, Washington University in St. Louis Which Schubert varieties are Hessenberg varieties?
Schubert varieties are subvarieties of the flag variety whose geometry can be understood using the combinatorics of permutations. Hessenberg varieties are also subvarieties of the flag variety with connections to both algebraic combinatorics and representation theory. After introducing and motivating these varieties, I will discuss joint work with Martha Precup and John Shareshian in which we investigate which Schubert varieties in the full flag variety are Hessenberg varieties.
21 October Inês Rodrigues, University of Lisbon An action of the cactus group on the shifted tableau crystal
The shifted tableau crystal is a crystal-like structure on shifted semistandard tableaux, introduced by Gillespie, Levinson and Purboo (2017). We define on this structure a shifted version of the crystal reflection operators, originally introduced by Lascoux and Schützenberger on type A crystals, which coincide with the restrictions of the shifted Schützenberger involution on primed intervals of two adjacent letters. Unlike type A crystal they not yield an action of the symmetric group. Following a similar approach as Halacheva (2016), we then exhibit a natural action of the cactus group on the shifted tableau crystal, realized by the restrictions of the shifted Schützenberger involution to all primed intervals of the underlying crystal alphabet, including, in particular, the crystal reflection operators.
28 October Jana Novotná, University of Warsaw/Charles University Clique-width of Atoms and Coloring for Hereditary Graphs
Clique-width is a well-established graph parameter. Many NP-complete graph problems are polynomially solvable on graph classes of bounded clique-width. Moreover, several of these problems are polynomially solvable on a hereditary graph class G if they are so on the atoms (graphs with no clique cut-set) of G. For these reasons, the boundedness of clique-width has been investigated for many graph classes. In this talk, we consider graph classes defined by one or two forbidden induced subgraphs. We discuss the coloring problem and the boundedness of clique-width of their atoms.
4 November Karen Meagher, University of Regina Erdős–Ko–Rado Theorems for Groups
The first half of this talk will be a gentle introduction to the Erdős–Ko–Rado (EKR) Theorem. This is a theorem that determines the size and structure of the largest collection of intersecting sets. It has become a cornerstone of extremal set theory and has been extended to many other objects. I will show how this result can be proven using techniques from algebraic graph theory.
In the second half of this talk I will give more details about extensions of the EKR theorem to permutations. Two permutations are intersecting if they both map some i to the same point (so σ and π are intersecting if and only if σ−1π has a fixed point). In 1977, Deza and Frankl proved that the size of a set of intersecting permutations is at most (n-1)!. It wasn't until 2003 that the structure of sets of intersecting permutations that meet this bound was determined.
For any group action, we can ask what is the size and structure of the largest set of intersecting permutations. I will show some recent results for different groups, with a focus on 2-transitive groups.
12 November 2:30-3:20pm Patricia Hersh, University of Oregon Posets arising as 1-skeleta of simple polytopes, the nonrevisiting path conjecture, and poset topology
Held jointly with the SFU Operations Research Seminar Note the nonstandard time and day of the week
Abstract: Given a polytope P and a nonzero vector c, the question of which point in P has largest inner product (or smallest inner product) with c is the main goal of linear programming in operations research. Key to efficiency questions regarding linear programming is the directed graph G(P,c) on the 1-skeleton of P obtained by directing each edge e(u,v) from u to v for c(u) < c(v) and in particular the diameter of G(P,c). We will explore the question of finding sufficient conditions on P and c to guarantee that no directed path ever revisits any polytope face that it has left; this is enough to ensure that linear programming is efficient under all possible choices of pivot rule. It turns out that poset-theoretic techniques and poset topology can help shed light on this question. In discussing work on this question, we will provide background along the way.
18 November Natasha Morrison, University of Victoria Hypergraph Lagrangians: Extremal Combinatorics and the Frankl-Füredi conjecture
In this talk we explore the origins of hypergraph Lagrangians and their applications to classical problems in extremal combinatorics. We then focus on the Frankl-Füredi conjecture, which concerns the maximal value of the Lagrangian of an r-uniform hypergraph with m edges. In particular, we show that the conjecture is false in general, but holds for all sufficiently large 3-uniform hypergraphs. This talk is based on joint work with Vytautas Gruslys and Shoham Letzter.
25 November Amélie Trotignon, Johannes Kepler University Discrete harmonic functions in the three-quarter plane
Harmonic functions play an important role in probability theory and are strongly related to the enumeration of walks. Doob h-transform is a way to build conditioned random processes in cones from a random process and a positive harmonic function vanishing on the boundary of the cone. Finding positive harmonic functions for random processes is therefore a natural objective in the study of confined random walks. There are very few ways to compute discrete harmonic functions. In this talk we are interested in positive discrete harmonic functions with Dirichlet conditions in three quadrants. Whereas planar lattice (random) walks in the quadrant have been well studied, the case of walks avoiding a quadrant has been developed lately. We extend the method in the quarter plane – resolution of a functional equation via boundary value problem using a conformal mapping – to the three-quarter plane applying the strategy of splitting the domain into two symmetric convex cones. We obtain a simple explicit expression for the algebraic generating function of harmonic functions associated to random walks avoiding a quadrant.
2 December Sofiat Olaosebikan, University of Glashow Algorithmics of the Student-Project Allocation problem
Matching problems are all around us – they arise when we try to find the “best” allocation between two sets of entities. For example, matching transplant patients with organ donors, allocating junior doctors to hospitals, students to projects, and wireless networks to users. This class of problems was first studied in 1962 by Gale and Shapley, and its founding researchers were awarded a Nobel prize in 2012. My talk is centred around the Student-Project Allocation problem (SPA), which, in its natural form, involves finding a many-to-one matching of students to projects offered by lecturers, based on student preferences over projects and the maximum number of students that each project and lecturer can accommodate. During my PhD, I explored SPA with lecturer preferences over Projects (SPA-P), SPA with lecturer preferences over Students (SPA-S), and SPA-S with Ties (SPA-ST). The solution concept that we seek in this context is a “stable matching” – a matching that ensures that no student and lecturer who are not paired together would rather be assigned to each other than remain with their current assignees. In my talk, I will present the structural and algorithmic results arising from my research on finding stable matchings in the problem models mentioned above.
8 December Aparna Lakshmanan, St. Xavier's College On Leech Labeling
Note the nonstandard day of the week
A tree is called a Leech tree, if one can assign positive integer edge weights such that the nC2 path weights are exactly 1, 2,..., nC2, where the weight of a path p, w(P) is the sum of weights of all its edges and such a labeling is called a Leech labeling. Motivated by a problem in electrical engineering, the concept was introduced by John Leech in 1975 and he found five examples which are the only known Leech trees till date. We have introduce a new parameter called Leech index which gives a measure of how close a tree is towards being a Leech tree. Let f : E → {1, 2, 3, . . . } be an edge labeling of T such that both f and the corresponding path weight function w are injective. Let S denote the set of all weights of the paths in T. Let kf be the positive integer such that {1, 2, 3, . . . , kf } ⊆ S and kf + 1 ∈/ S. Then k(T) = max kf , where the maximum is taken over all such edge labelings f is called the Leech index of T. We determine the Leech index of several families of trees and obtain bounds for this parameter. The concept of Leech trees has been extended to general graphs also and studies are going in that direction too.

Spring 2020

16 September Marthe Bonamy, LaBRI On Vizing's edge colouring question
In his 1965 seminal paper on edge colouring, Vizing proved that a (Delta+1)-edge colouring can be reached from any given proper edge colouring through a series of Kempe changes, where Delta is the maximum degree of the graph. He concludes the paper with the following question: can an optimal edge colouring be reached from any given proper edge colouring through a series of Kempe changes? In other words, if the graph is Delta-edge-colourable, can we always reach a Delta-edge-colouring? If true, this would imply a more recent conjecture of Mohar (2006) that in any graph, all (Delta+2)-edge-colourings are equivalent up to a series of Kempe changes. We discuss recent progress around these questions.
23 September Carla Groenland, University of Oxford Asymptotic dimension of graph classes
I will attempt to give some intuition for asymptotic dimension of graph classes, starting from the definition and giving the connection to clustered colouring and weak-diameter network decompositions. I will sketch the ideas behind some of our results, e.g. that the class of planar graphs has asymptotic dimension 2. Asymptotic dimension was introduced by Gromov in 1993 within geometric group theory and in the graph setting makes sense for infinite graphs or graph classes. Joint work with M. Bonamy, N. Bousquet, L. Esperet, F. Pirot, and A. Scott.
30 September Karen Yeats, University of Waterloo Chains of hourglasses and the graph theory of their Feynman integrals
I will give a set up for understanding the graph theory of Feynman integrals that I have been using over the last number of years. It is all very combinatorial and does not require any understanding of physics or analysis. Then I will explain about some joint work with Oliver Schnetz where we are able to complete a generalized denominator reduction on a particular family of graphs and from this calculate an arithmetic graph invariant on them known as the c_2 invariant as well as understand properties of their Feynman integrals.
7 October Shanise Walker, University of Wisconsin Eau Claire The Game of Cycles
The Game of Cycles was introduced by Francis Su in his book titled Mathematics for Human Flourishing (2020). The game is played on a simple connected planar graph together with its bounded cells, and players take turns marking edges with arrows according to a sink-source rule. The object of the game is to produce a cycle cell–a cell surrounded by arrows all cycling in one direction–or to make the last possible move. In this talk, we explore the two-player game for various classes of graphs and determine who has a winning strategy.
14 October Laura Escobar, Washington University in St. Louis Which Schubert varieties are Hessenberg varieties?
Schubert varieties are subvarieties of the flag variety whose geometry can be understood using the combinatorics of permutations. Hessenberg varieties are also subvarieties of the flag variety with connections to both algebraic combinatorics and representation theory. After introducing and motivating these varieties, I will discuss joint work with Martha Precup and John Shareshian in which we investigate which Schubert varieties in the full flag variety are Hessenberg varieties.
21 October Inês Rodrigues, University of Lisbon An action of the cactus group on the shifted tableau crystal
The shifted tableau crystal is a crystal-like structure on shifted semistandard tableaux, introduced by Gillespie, Levinson and Purboo (2017). We define on this structure a shifted version of the crystal reflection operators, originally introduced by Lascoux and Schützenberger on type A crystals, which coincide with the restrictions of the shifted Schützenberger involution on primed intervals of two adjacent letters. Unlike type A crystal they not yield an action of the symmetric group. Following a similar approach as Halacheva (2016), we then exhibit a natural action of the cactus group on the shifted tableau crystal, realized by the restrictions of the shifted Schützenberger involution to all primed intervals of the underlying crystal alphabet, including, in particular, the crystal reflection operators.
28 October Jana Novotná, University of Warsaw/Charles University Clique-width of Atoms and Coloring for Hereditary Graphs
Clique-width is a well-established graph parameter. Many NP-complete graph problems are polynomially solvable on graph classes of bounded clique-width. Moreover, several of these problems are polynomially solvable on a hereditary graph class G if they are so on the atoms (graphs with no clique cut-set) of G. For these reasons, the boundedness of clique-width has been investigated for many graph classes. In this talk, we consider graph classes defined by one or two forbidden induced subgraphs. We discuss the coloring problem and the boundedness of clique-width of their atoms.
4 November Karen Meagher, University of Regina Erdős–Ko–Rado Theorems for Groups

The first half of this talk will be a gentle introduction to the Erdős–Ko–Rado (EKR) Theorem. This is a theorem that determines the size and structure of the largest collection of intersecting sets. It has become a cornerstone of extremal set theory and has been extended to many other objects. I will show how this result can be proven using techniques from algebraic graph theory.

In the second half of this talk I will give more details about extensions of the EKR theorem to permutations. Two permutations are intersecting if they both map some i to the same point (so σ and π are intersecting if and only if σ−1π has a fixed point). In 1977, Deza and Frankl proved that the size of a set of intersecting permutations is at most (n-1)!. It wasn't until 2003 that the structure of sets of intersecting permutations that meet this bound was determined.

For any group action, we can ask what is the size and structure of the largest set of intersecting permutations. I will show some recent results for different groups, with a focus on 2-transitive groups.

12 November 2:30-3:20pm Patricia Hersh, University of Oregon Posets arising as 1-skeleta of simple polytopes, the nonrevisiting path conjecture, and poset topology
Held jointly with the SFU Operations Research Seminar Note the nonstandard time and day of the week
Abstract: Given a polytope P and a nonzero vector c, the question of which point in P has largest inner product (or smallest inner product) with c is the main goal of linear programming in operations research. Key to efficiency questions regarding linear programming is the directed graph G(P,c) on the 1-skeleton of P obtained by directing each edge e(u,v) from u to v for c(u) < c(v) and in particular the diameter of G(P,c). We will explore the question of finding sufficient conditions on P and c to guarantee that no directed path ever revisits any polytope face that it has left; this is enough to ensure that linear programming is efficient under all possible choices of pivot rule. It turns out that poset-theoretic techniques and poset topology can help shed light on this question. In discussing work on this question, we will provide background along the way.
18 November Natasha Morrison, University of Victoria Hypergraph Lagrangians: Extremal Combinatorics and the Frankl-Füredi conjecture
In this talk we explore the origins of hypergraph Lagrangians and their applications to classical problems in extremal combinatorics. We then focus on the Frankl-Füredi conjecture, which concerns the maximal value of the Lagrangian of an r-uniform hypergraph with m edges. In particular, we show that the conjecture is false in general, but holds for all sufficiently large 3-uniform hypergraphs. This talk is based on joint work with Vytautas Gruslys and Shoham Letzter.
25 November Amélie Trotignon, Johannes Kepler University Discrete harmonic functions in the three-quarter plane
Harmonic functions play an important role in probability theory and are strongly related to the enumeration of walks. Doob h-transform is a way to build conditioned random processes in cones from a random process and a positive harmonic function vanishing on the boundary of the cone. Finding positive harmonic functions for random processes is therefore a natural objective in the study of confined random walks. There are very few ways to compute discrete harmonic functions. In this talk we are interested in positive discrete harmonic functions with Dirichlet conditions in three quadrants. Whereas planar lattice (random) walks in the quadrant have been well studied, the case of walks avoiding a quadrant has been developed lately. We extend the method in the quarter plane – resolution of a functional equation via boundary value problem using a conformal mapping – to the three-quarter plane applying the strategy of splitting the domain into two symmetric convex cones. We obtain a simple explicit expression for the algebraic generating function of harmonic functions associated to random walks avoiding a quadrant.
2 December Sofiat Olaosebikan, University of Glashow Algorithmics of the Student-Project Allocation problem
Matching problems are all around us – they arise when we try to find the “best” allocation between two sets of entities. For example, matching transplant patients with organ donors, allocating junior doctors to hospitals, students to projects, and wireless networks to users. This class of problems was first studied in 1962 by Gale and Shapley, and its founding researchers were awarded a Nobel prize in 2012. My talk is centred around the Student-Project Allocation problem (SPA), which, in its natural form, involves finding a many-to-one matching of students to projects offered by lecturers, based on student preferences over projects and the maximum number of students that each project and lecturer can accommodate. During my PhD, I explored SPA with lecturer preferences over Projects (SPA-P), SPA with lecturer preferences over Students (SPA-S), and SPA-S with Ties (SPA-ST). The solution concept that we seek in this context is a “stable matching” – a matching that ensures that no student and lecturer who are not paired together would rather be assigned to each other than remain with their current assignees. In my talk, I will present the structural and algorithmic results arising from my research on finding stable matchings in the problem models mentioned above.
8 December Aparna Lakshmanan, St. Xavier's College On Leech Labeling
Note the nonstandard day of the week
A tree is called a Leech tree, if one can assign positive integer edge weights such that the nC2 path weights are exactly 1, 2,..., nC2, where the weight of a path p, w(P) is the sum of weights of all its edges and such a labeling is called a Leech labeling. Motivated by a problem in electrical engineering, the concept was introduced by John Leech in 1975 and he found five examples which are the only known Leech trees till date. We have introduce a new parameter called Leech index which gives a measure of how close a tree is towards being a Leech tree. Let f : E → {1, 2, 3, . . . } be an edge labeling of T such that both f and the corresponding path weight function w are injective. Let S denote the set of all weights of the paths in T. Let kf be the positive integer such that {1, 2, 3, . . . , kf } ⊆ S and kf + 1 ∈/ S. Then k(T) = max kf , where the maximum is taken over all such edge labelings f is called the Leech index of T. We determine the Leech index of several families of trees and obtain bounds for this parameter. The concept of Leech trees has been extended to general graphs also and studies are going in that direction too.
  All the remaining sessions cancelled due to the coronavirus disease (COVID-19)  
10 March David Wood, Monash University Graph and Poset Dimension Parameters
3 March Alexander Pott, Otto von Guericke University Magdeburg Vanishing flats: a combinatorial viewpoint on the nonlinearity of functions
25  Feburary Mehdi Salimi, SFU Pursuit-Evasion Games
18 Feburary Jason Schoeters, University of Bordeaux Temporal cliques admit sparse spanners
11 Feburary Timothy Chan, Monash and Warwick Matroid branch-depth and integer programming
 4  Feburary (Cancelled due to campus snowfall closure)  
28 January 

Joris van der Hoeven, CNRS 

(Distinguished PIMS Discrete Math talk)

Integer multiplication in time O(n log n) 
21 January Joris van der Hoeven, CNRS Historic algorithms for integer multiplication

14  January

Kevin Halasz, SFU Near transversals of latin squares

2019 Talks

Fall 2019

03 December Stephanie van Willigenburg, UBC
The e-positivity of chromatic symmetric functions
26 November Peter Horak, University of Washington
Extremal problems on cycles in graphs
19 November Thaís Bardini, SFU
Fault tolerance in cryptographic applications using cover-free families
12 November Brin Chan, UBC
A generalization of balanced tableaux and matching problems with unique solutions
05 November Pavol Hell, SFU Graphs with possible loops
29 October Kathryn Nurse, SFU
Maximum Directed Linear Arrangement
22 October Robert Samal, Charles University
The binary paint shop problem (aka necklace splitting problem)
15 October Farid Aliniaeifard, UBC
Combinatorial Hopf algebras and representation theory
08 October Rikke Marie Langhede, DTU
The weak group connectivity number versus the group connectivity number
01 October Petr Lisonek, SFU
Maximally non-associative quasigroups
24 September Gary MacGillivray, University of Victoria
Switching (m,n)-edge-coloured graphs
17 September Gonzalez Hermosillo de la Maza, SFU
Active cops and robbers
10 September
Peter Bradshaw, SFU
Graphs with high cop number
03 September Curtis Bright, University of Waterloo
SAT Solving with Computer Algebra: A Powerful Combinatorial Search Method

Spring 2019

23 April Amarpreet Rattan, SFU Parking functions and factorizations of the full cycle.
16 April Igor Shinkar, SFU
On (almost) Lipschitz mappings on the discrete hypercube
9 April Peter Bradshaw, SFU Cops and Robbers on Cayley Graphs
2 April
Nike Dattani, Harvard-Smithsonian Center for Astrophysics Solving mathematical and machine learning problems on quantum computers
26 March
Peter Horak, University of Washington
Old and New Conjectures in Tilings
19 March Bojan Mohar, SFU Toward a Theory of Crossing-Critical Graphs, Part I

2018 Talks

Fall 2018

4 December
Michael Monagan, SFU How to factor a multivariate polynomial
20 November Mahdieh Malekian, SFU Excluding small graphs as immersion
13 November Bojan Mohar, SFU 50 Years of the Ringel-Youngs Map Colour Theorem
23 October Jonathan Jedwab, SFU New Constructions of Difference Matrices
16 October
Leionid Chindelevitch, SFU Metabolic networks: discrete geometry and optimization
9 October Matt DeVos, SFU On the colourful world of Ron Aharoni

Summer 2018

7 August Fuji Zhang Spectral dynamics of graph eigenvalues
31 July Sebastian Gonzalez, SFU  
10 July Yifan Jing, SFU On the genus of complete 3-uniform hypergraphs
26 June Andrew Berget, Western Washington U Internal Zonotopal Algebras of Reflection Arrangements
5 June Cedric Chauve, SFU MaxTiC, ranking species trees using network constraints
29 May Amy Wiebe, University of Washington The Slack Realization Space of a Polytope
22 May James Davis, University of Richmond Apple vs Samsung: a Mathematical Battle
15 May
Haiyan Chen On the sandpile group of a polygon flower

Spring 2018

12 April Jephian Lin The zero forcing process and the strong Arnold property
31 March, Seattle Sylvie Corteel, Kevin Purbhoo, Steph van Willigenburg, Matjaž Konvalinka
Pacific NW Combinatorics day, UWash, Seattle
24-25 Mar, Victoria   2018 Coast Combinatorics Conference University of Victoria, Victoria, BC
20 Mar Ryan Hayward, Alberta Recent results on Hex
13 Mar Seyyed Aliasghar Hosseini, Simon Fraser University Cops and Robbers on Graphs of Bounded Diameter
6 Mar Stephen Melczer, UPenn Eventual Positivity of Rational Function Coefficients
27 Feb Amanda Montejano Cantoral, Universidad Nacional Autónoma de México Forced chromatic patterns in 2-colorings of the complete graph
20 Feb (cancellation)  
13 Feb No seminar (Reading week)  
6 Feb Philippe Nadeau, Lyon/CNRS Combinatorics of the category of noncrossing partitions
30 Jan Samantha Dahlberg, UBC The e-positivity of claw-contractible-free graphs
23 Jan Karen Meagher, Regina Approaches to the Erdős-Ko-Rado Theorem
16 Jan Jessica McDonald, Auburn Edge-colouring planar graphs with precoloured edges

2017 Talks

Fall 2017

Dec 5 Karen Yeats
C&O Waterloo

A little progress on the completion invariance of the c2 invariant

 Nov 28 Koen van Greevenbroek
Math, SFU

 Contracted Difference Matrices

 Nov 21 Tony Huynh
Université Libre de Bruxelles

A tight Erdős-Pósa function for wheel minors

7 Nov Leonid Chindelevitch
SFU
Finding the rank median of three genomes
24 Oct Ross McConnell
Colorado State
Planar and Outerplanar Graphs
17 Oct Ron Aharoni
Israel Institute of Technology
Cooperative colorings
10 Oct Sheila Sundaram
Pierrepont School
Variations on the S_n-module Lie_n: results and conjecture
3 Oct Amanda Montejano
Universidad Nacional Autónoma de México
Zero-sum over Z
26 Sept Jehanne Dousse
Universität Zürich
Refinement of partition identities
19 Sept Moshe Rosenfeld
U of Washington
Starters what you know or don't care to know: old and new open problems
12 Sept Amelie Trotignon
SFU
 Simple Walks in the Three Quarter Plane

Summer 2017

29 Aug David Wood
Monash University
Monotone expanders and applications
08 Aug Aniket Mane
SFU
A tractable variant of the Single Cut or Join distance with duplicated genes
08 Aug
Abhinav Shantanam
SFU
Hadwiger Number of Complements of Kneser Graphs with \alpha = 2
01 Aug Dirk Nowotka
Kiel University
k-abelian pattern matching
25 July Cesar Hernandez Cruz
Universidad National Automate de Mexico
k-quasi-transitive digraphs of large diameter
25 July Samuel Simon
SFU
Linking Systems of Difference Sets
18 July Shuxing Li
SFU
Construction and nonexistence of strong external difference family
11 July Julian Sahasrabudhe
U of Cambridge
Exponential Patterns in Arithmetic Ramsey Theory
04 July Avi Kulkarni
SFU
Reading graphs into SAGE from an IPE diagram
04 July Sebastian Gonzalez Hermosillo de la Maza
SFU
Proper Orientations of Planar Bipartite Graphs
06 Jun
Arnaud Casteigts,
LaBRI, U de Bordeaux
Robustness in Highly Dynamic Networks
30 May Joao Meidanis,
U of Campinas, Brazil
Genome Matrices and the Median Problem
23 May
Stephen Melczer,
U of Waterloo
Effective Analytic Combinatorics in Several Variables
16 May Mark Kayll,
U of Montana
Derangements through the years: 1708--1996--2014

Spring 2017

18 April Julian Sahasrabudhe,
U of Cambridge
Exponential Patterns in Arithmetic Ramsey Theory
28 Mar Jonathan Jedwab,
SFU
Costas cubes
21 Mar
Pavol Hell, 
SFU
Obstruction Certificates for Geometrically Defined Graph (and Digraph) Classes
14 Mar David Rowe,
Universitat Mainz
*This Talk Will Begin At 2pm*
The Role of Configurations in Classical Algebraic Geometry
7 Mar Peter Wu,
SFU
On maximal size of 2-weakly compatible split system
28 Feb Sean Griffin,
U of Washington
Schur positivity and labeled binary trees
21 Feb Bojan Mohar,
SFU
The Crossing Number of the Cone of the Graph
7 Feb Fiachra Knox, 
SFU
Majority Colourings of Digraphs
31 Jan Luis Goddyn,
SFU
Parity Trackles on Surfaces and Perturbations of Bilinear Forms

2016 Talks

Fall 2016

Date Speaker, Affiliation Talk Title
20 Sep Tony Huynh,
U Libre de Bruxelles
The matroid secretary problem for minor-closed classes and random matroids
18 Oct Marni Mishna,
SFU
Universality classes for weighted lattice paths: where probability and ACSV meet
25 Oct Jørgen Bang-Jensen,
U of Southern Denmark
Connectivity properties of tournaments and semicomplete digraphs
1 Nov Seyyed Aliasghar Hosseini,
SFU
Cops and Robbers on Oriented Grids I
8 Nov Sebastian Gonzalez, SFU Cops and Robbers on Oriented Grids II
15 Nov Samantha Dahlberg, UBC Pattern Avoidance in Restricted Growth Functions
22 Nov Steffen Borgwardt, U of Colorado The Hirsch Conjecture is true for Network-Flow Polytopes
29 Nov Justin Chan, SFU Suitable Cores And Arrays
*Please Note Date/Location: 
         Talk on December 5th will be held in the IRMACS Theatre on MONDAY, Dec 5th

5 Dec Fan Chung Graham, U of California, San Diego
Sequences: random, structured or something in between?

Summer 2016

10 May Natalia García-Colín
U Nacional Autónoma de México
On the tolerated Tverberg number
17 May Jonathan Jedwab
Simon Fraser University
How many mutually unbiased bases can exist in complex space of dimension d?
24 May Dmitry Doryn
IBS Center for Geometry and Physics
c2 invariants of Feynman graphs
31 May CANCELLED
7 Jun CANCELLED
14 Jun César Hernández Cruz
U Autónoma de Zacatecas
A dichotomy for the kernel by H-walks problem in digraphs
21 Jun Flavia Bonomo
U Buenos Aires
Three-coloring and list three-coloring graphs without induced paths on seven vertices
28 Jun
(extra)
11:30am
Ross McConnell
Colorado State University
Algorithms on graphs arising from intersections of intervals
28 Jun Melissa Huggan
Dalhousie University
Conjoined games: go-cut and sno-go
5 Jul (extra)
11:30am
Mathew Francis
Indian Statistical Institute, Chennai Centre
Uniquely restricted matchings in interval graphs
5 Jul Hendrik Süß
University of Manchester
Frobenius splitting of toric and T-varieties
12 Jul Bruce Reed
McGill University
How to determine if a random graph with a fixed degree sequence has a giant component
19 Jul CANCELLED
26 Jul Iain Crump
Simon Fraser University
The extended graph permanent as an affine variety
Thursday
28 Jul
3:30pm
Mordecai Golin
Hong Kong UST
Optimal binary comparison search trees

Spring 2016

12 Jan Rodolphe Garbit
Université d'Angers
On the exit time from a cone for random walks with drift
19 Jan Suil O
Simon Fraser
Interlacing families and their application to digraphs
26 Jan
IRMACS Theatre
1:00pm
(12:00 reception)
Kilian Raschel
CNRS / U François Rabelais - Tours
Counting quadrant walks via Tutte's invariants and transformation theory of elliptic functions 
2 Feb Stefan Hannie
Simon Fraser
Immersion of 2-regular digraphs
9 Feb Reading break CANCELLED
16 Feb Pierre Tarrago
Saarlandes University
Categories of two-colored non-crossing partitions
23 Feb CANCELLED
1 Mar Cedric Chauve
Simon Fraser
Counting, generating and sampling tree alignments
8 Mar Julien Courtiel
UBC
Terminal chords in connected diagrams chords
15 Mar Claudia Linhares Sales
UF Ceará
B-continuity of lexicographic product of graphs
22 Mar Alejandro Morales
UCLA
Hook Formulas for Skew Shapes
22 Mar
(2nd talk)
3:00pm
Barnaby Martin
Middlesex University London
The packing chromatic number of the infinite square lattice
29 Mar Fiachra Knox
Simon Fraser
Ramanujan gap for the norm of adjacency operators
5 Apr --- PIMS-SFU Colloquium: Anthony Várilly-Alvarado in IRMACS Theatre

2015 Talks

Fall 2015

22 Sept Ilya Shmulevich
Institute for Systems Biology
Probabilistic Boolean Networks as Models of Genetic Regulatory Networks
Thursday
24 Sept
11:00am
Harrison Chapman
University of Georgia
Asymptotic laws for knot diagrams
29 Sept Gary Greaves
Tohoku University
Equiangular lines in Euclidean spaces
6 Oct Karen Yeats
Simon Fraser
A few c_2 invariants of circulant graphs
13 Oct Abbas Mehrabian
UBC/SFU
Cops and a Fast Robber on Planar and Random Graphs
20 Oct Matt DeVos
Simon Fraser
Flows with large support
27 Oct Alejandro Erickson
Durham University
Graphs at the heart of the cloud
3 Nov Eric Fusy
CNRS / École Polytechnique
Baxter permutations and meanders
10 Nov Yota Otachi
Japan Advanced Institute of Science and Technology
Induced minor-free graphs: isomorphism and clique-width
17 Nov Theodore Kolokolnikov
Dalhousie University
Maximizing algebraic connectivity for certain families of graphs
24 Nov Shenwei Huang
Simon Fraser University
Colouring graphs without an induced path: A survey
1 Dec Luis Goddyn
Simon Fraser

Extending Hawiger’s Conjecture and Bicircular Matroids

8 Dec Campus closure CANCELLED
Monday
14 Dec
PIMS 8500
1:30pm
Chính Hoàng
Wilfred Laurier University
On the structure of (pan, even hole)-free graphs
Monday
14 Dec
PIMS 8500
3:00pm
Mark Giesbrecht
U Waterloo
Eigenvalues, invariant factors and random integer matrices (with a little bit of computing)

Summer 2015

12 May
Nicholas Beaton
U. Saskatchewan
Solvable self-avoiding walk and polygon models with large growth rates
19 May Matt DeVos
Simon Fraser
On nowhere-zero flows
26 May Luis Goddyn
Simon Fraser
Odd thrackles on surfaces
02 June CanaDAM 2015 CANCELLED
09 June Robert Samal 
Charles U.
Unique Vector Coloring and Cores
16 June Ron Graham conference CANCELLED
23 June Amanda Montejano
UNAM
Cyclic orders and oriented 3-hypergraphs.
30 June Marni Mishna
Simon Fraser
Efficient uniform generation of reluctant walks
07 July Moshe Rosenfeld The wondering salmon problem and (unrelated) graph designs
14 July Christopher Duffy
UVic
Colourings and simple colourings of (j,k)-mixed graphs
Thursday
23 July
Bruce Reed
McGill University
Connectivity preserving iterative compaction
28 July César Hernández-Cruz
UNAM
Mixed cages
Acyclic disconnection and minimum feedback arc sets of graphs
04 August Jan Manuch
UBC
 

Spring 2015

Tuesday Jan 13
David Gajser, University of Ljubljana, Slovenia  Simple PTAS’s for families of graphs excluding a minor
Tuesday Jan 20
Martina Mockovciakova (University of West Bohemia, Pilsen, Czech Republic) Star Edge Coloring of Some Classes of Graphs
Tuesday Jan 27 (IRMACS,
12:30 reception)
Michael Singer (NCSU)
(PIMS Distinguished Visitor)
Galois theory of difference and differential equations.
Tuesday Feb 3
Manuel Kauers (RISC)
Walks in the Quarter Plane with Multiple Steps
Tuesday Feb 10
(Reading Week)
 
Tuesday Feb 17
Cedric Chauve, SFU Graph-theoretical algorithms to correct gene trees
Tuesday Feb 24
Edita Rollova (KMA) Homomorphisms and colourings of signed graphs
Tuesday Mar 3
Murilo da Silva Even-hole-free graphs
Tuesday Mar 10
Henry Liu, New University Lisbon, Portugal Connected subgraphs in edge-coloured graphs
Tuesday Mar 17
Ashok Rajaraman Vertex Ordering Problems for Hypergraphs: Connections to the Consecutive Ones Property
Tuesday Mar 24
Veronika Irvine (U Victoria) Lace patterns
Tuesday Mar 31
Guillaume Chapuy (Liafa/ Paris 7) Spanning trees of the graph of spanning trees.
Tuesday April 7 Karen Yeats (SFU) Rooted tree classes and the renormalization group equation
Tuesday April 14 Nathan Ilten (SFU) Counting lines on toric surfaces

2010 Talks

Seminars 2001-2010

Fall 2010
Tue Sept 14 / 2:30 / K9509 Zdenek Dvorak Choosability of planar graphs + Welcome party
Tue Sept 21 / 2:30 / K9509 Jessica McDonald, SFU Characterizing high chromatic index
Tue Sept 28 / 2:30 / K9509 Emmanuel Godard, CNRS/ U. Aix (Marseilles) Using isometric embeddings in distributed algorithms for the median problem in partial rectangular grids and their relatives
Tue Oct 5 / 2:30 / K9509 Mohamed Omar, UC Davis. Graph Automorphism and Permutation Groups via Polytopes
Tue October 12 / 2:30 / K9509 Karen Yeats, SFU The support of power series given by systems of equations
Tue October 19 / 2:30 / K9509 Cedric Chauve, SFU On matrices that do not have the Consecutive-Ones Property.
Tue October 26 / 2:30 / K9509 Andrew Crites, U. Washington Affine permutations and pattern avoidance
Tue Nov 2 / 2:30 / K9509 Petr Lisonek, SFU Non-linear functions
Tue Nov 9 / 2:30 / K9509 Flavio Guinez, UBC The reconstruction of a colored grid by its projections: a solution to the 2-atom problem in discrete tomography
Tue November 16 / 2:30 / K9509 Amites Sarkar, UWW Partitioning
geometric covers
Tue November 23 / 2:30 / K9509 Kurt Luoto, UBC Quasisymmetric and noncommutative Schur functions
Tue Nov 30 / 2:30 / K9509 Aki Avis, SFU 3-Phase Golay Triads
Tue Dec 7 / 2:30 / K9509 Pradeep Sarvepalli (UBC) Topological color codes over prime power alphabet
Satruday December 11 (Western Washington University) Combinatorial potlatch Richard Guy, University of Calgary
Christine Kelley, University of Nebraska, Lincoln
Kai-Uwe Schmidt, Simon Fraser University
Tue Dec 14 / 2:30 / K9509 Bruce Shepherd Minimum Cost Networks Supporting All Matchings
Summer 2010
Tue 08 Jun / 2:30 / K9509 John Stardom, Statistics Canada Sample Stratification and Allocation: an Application to Statistics Canada's Unified Enterprise Survey
Tue 22 Jun / 2:30 / K9509 Christian Stump, CRM/ LaCIM UQAM Non-crossing and non-nesting partitions and the cyclic sieving phenomenon
Tue 07 July / 2:30 / K9509 Karel Casteels, SFU Combinatorial aspects of the prime spectrum of quantum matrices
Tue 13 July / 2:30 / K9509 Guillaume Chapuy, SFU Covered Maps on Orientable Surfaces
Tue 10 August / 2:30 / K9509 Kai-Uwe Schmidt, SFU Appended m-sequences with merit factor greater than 3.34
Spring 2010
Tue 09 Feb / 3:30 / TASC2 8500 Kevin Milans, U. Illinois UC Degree Ramsey Numbers of Graphs
Tue 02 Mar / 3:30 / TASC2 8500 Ararat Harutyunyan, SFU Independent dominating sets in graphs of girth five
Thu 04 Mar / 1:00 / K 9509 Adolfo Rodriguez, LaCIM UQAM Bugs, colonies, and q-Boson normal ordering
Tue 23 Mar / 3:30 / TASC2 8500 Roland Wittler, Bielefeld and SFU. Phylogeny-based Analysis of Gene Clusters
Thu 25 Mar / 1:00 / K 9509 Justin Chan, University of Victoria The Lamken-Wilson Theorem and Its Applications
Mon 12 Apr / 2:30 / IRMACS Theatre, ASB 10900, SFU Peter Horak, U. Washington, Tacoma Tiling n-space by cubes
Tue 13 Apr / 3:30 / TASC2 8500 Alejandro Erickson, University of Victoria Negative correlation properties for graphs
Tue 20 Apr / 3:30 / TASC2 8500 Robert Samal, Charles University, Prague Star Chromatic Index
Fall 2009
Tue 22 Sep / 1:30 / K9509 Bojan Monar, SFU How useful can the spectral radius of a graph be?
Tue 29 Sep / 1:30 / K9509 Ladislaw Stacho Cyclic colorings of plane graphs with independent faces
Tue 06 Oct / 1:30 / K9509 Guillaume Chapuy Maps on surfaces : asymptotic enumeration and metric properties.
Tue 13 Oct / 1:30 / K9509 Andrea Spencer, SFU Title: Efficient Edge List Colouring of Cubic Planar Graphs
Tue 27 Oct / 1:30 / K9509 Mahdad Khatirinejad-Fard, Helsinki U. of Tech. Title: Edge-weighting vertex colouring of (di)graphs
Sat 21 Nov / 10:00 / Labatt Room 2009 Combinatorial Potlach, SFU Harbour Centre Speakers: TBA
Summer 2009
Tue 05 May / 2:00 / TASC2 8500 Daniel Kral, Charles U., Prague Removal Lemma for systems of linear equations
Tue 25 Aug / 3:30 / K9509 Gena Hahn, U. de Montreal Cops and Robbers on Infinite Graphs
Tue 01 Sep / 3:30 / K9509 Robert Samal, Charles U., Prague Cubical chromatic number, spherical chromatic number, and Lovasz theta function
Spring 2009
Tue 10 Feb / 3:30 / K9509 Robert Bailey, Carleton University Packing spanning trees in graphs and bases in matroids
Sat-Sun 21-22 Feb, Univ. of Victoria 11th Coast Combinatorics Conference  
Tue 24 Feb / 3:30 / K9509 Markus Grassl, Centre for Quantum Technologies (NUS), Singapore Searching for good error-correcting codes
Tue 31 Mar / 3:30 / K9509 Hernando Bermudez, University of Montana Sheduling Tournaments with Home and Away Constraints
Tue 24 Mar / 3:30 / K9509 Natasa Przulj, UC Irvine From Network Topology to Biological Function and Disease
Tue 14 Apr / 3:30 / K9509 Cedric Chauve Enumerative results for graph decompostion trees
Tue 21 Apr / 3:30 / K9509 Eric Fusy Schnyder woods generalized to higher genus surfaces
Tue 28 Apr / 3:30 / K9509 Bruce Richter, University of Waterloo Do we really know what characterizes planarity?
Fall 2008
Tue 23 Sep / 3:30 / K9509 Juanjo Ru\'e, Politechnical U. of Catalonia On a question of S\'arkozy and S\'os on bilinear forms
Thu 02 Oct / 1:30 / K9509 Mireille Bousquet-Melou, CNRS, Bordeaux Enumeration of colored planar maps
Tue 14 Oct / 3:30 / K9509 Eli Berger, Univeristy of Haifa Using classical topology in combinatorial problems.
Tue 28 Oct / 2:30 / ASB 10900 David Brydges, CRC Chair, UBC Combinatorics with Gaussian Integreals
Tue 04 Nov / 3:30 / K9509 Ken-ichi Kawarabayashi, Nat. Inst. of Informatics, Japan From the Plane to Higher Surfaces
Tue 18 Nov / 3:30 / K9509 Aida Ouangraoua, SFU Algorithmic tools to compare tree-structured biological objects
Sat 22 Nov / 10:00 / U.P.S. 2008 Combinatorial Potlach, U. Puget Sound, Tacoma Speakers: E. Fusy + C. Dunn + I. Dumitriu
Tue 02 Dec / 3:30 / K9509 Brian Alspach, U. Newcastle Hamilton paths in vertex-transative graphs
Summer 2008
   
Tue 06 May / 3:30 / K9509 Bojan Mohar, SFU On the sum of k largest eigenvalues of graphs and symmetric matrices
Tue 20 May / 3:30 / K9509 Simon Spacapan, SFU The Acyclic, the Star, and the Degenerate Chromatic Numbers
Tue 22 Jul / 3:30 / K9509 Winfried Hochstaettler, U. of Hagen, Germany Flows in Oriented Matroids and a Chromatic Number
Tue 19 Aug / 2:30 / TASK 9204 David Coudert, CNRS U. Nice Sophia Survivability and Routing in Oriented Networks
Spring 2008
Tue 15 Jan / 3:30 / K9509 Maia Fraser, U. Colima, Mx Local routing on higher surfaces
Tue 25 Feb / 3:30 / K9509 Gabor Kun, Etvos University, Hungary Cops and robbers in random graphs
Tue 04 Mar / 3:30 / K9509 Luis Goddyn, Simon Fraer University How bad can a Euclidean Traveling Salesman Problem be?
Tue 11 March / 3:30 / TASC2 8500 Penny Haxell, University of Waterloo More on Sperner's Lemma
Tue 25 March / 3:30 / K9509 Agelos Georgakopoulos, University of Hamburg Infinite cycles in graphs
Tue 25 March / 3:30 / K9509 Marni Mishna, Simon Fraser University Decomposition and Enumeration of Planar Graphs, Part I: Combinatorial Warm Up
Tue 01 April / 3:30 / K9509 Eric Fusy, Simon Fraser University Decomposition and Enumeration of Planar Graphs, Part II
Tue 08 April / 3:00 / K 9509 Laura Chavez, Simon Fraser University Flow and chromatic numbers for matroids (reception to follow)
Tue 15 April / 3:30 / K 9509 Derek Bingham, Simon Fraser University Defining contrast subspaces and the randomization structure of factorial designs
Tue 29 April / 3:30 / K 9509 Sean McGuinness, Thompson Rivers University Perfect Path Double Covers, Matroids, A Theorem of Fan, ... And A Problem of Goddyn.
Fall 2007
Tue 25 Sep / 10:30 / ASB10900 Luis Goddyn, SFU (Coast to Coast) Spectra of (3,6)-Fullerenes
Tue 25 Sep / 2:30 / TASC2 8500 Mark Siggers, SFU Integer packings of hypergraphs through fractional packings
Sat 29 Sep / 11:00 / U. Victoria 2007 Combinatorial Potlach Speakers: Perkel + Moon + Quas
Tue 02 Oct / 2:30 / TASC2 8500 Robert Samal, SFU Trading Handles for Crossings
Tue 09 Oct / 2:30 / TASC2 8500 Blair D Sullivan, Princeton Feedback Arc Sets in Circular Interval Digraphs
Tue 23 Oct / 2:30 / TASC2 8500 Gabor Kun, SFU An asymptotic version of the Bollobas-Catlin-Eldridge conjecture
Tue 30 Oct / 2:30 / TASC2 8500 Matthias Koeppe, U. Magdeburg, de Topic: Ehrhart polynomials of matroid polytopes
Tue 06 Nov / 2:30 / TASC2 8500 Eric Fusy, SFU Transversal structures on triangulations: combinatorial study and algorithmic applications
Tue 13 Nov / 2:30 / TASC2 8500 Vladmir Korzhik, Nat. U. Chernivtsi, Ukraine Some open problems on the set of triangular embeddings of a complete graph
Tue 27 Nov / 2:30 / TASC2 8500 Frederic Giroire, Intel Research Probabilistic algorithms to compute the cardinality of very large datasets
Summer 2007
Tue 15 May / 3:30 / ASB10908 Ambat Vijayakumar Graph operators and co-graphs: some recent trends
Fri 18 May / 1:30 / ASB10900 Andre Raspaud Injective Colourings of Graphs
Tue 22 May / 3:30 / ASB10908 Jonathan Jedwab, SFU Golay complementary sequences: a multi-dimensional approach
Thu 24 May / 11:30 / ASB10900 Janos Pach Decomposition of multiple coverings
Fri 25 May / 2:30 / ASB10900 Herbert Wilf Mathematics: An experimental science
Fri 31 Aug / 2:30 / 1430 SFU Harbour Centre Paul Seymour Structure Theorems in Graph Theory
Spring 2007
Tue 30 Jan / 3:30 / ASB10908 Azhvan Sheikh-Ahmady, SFU Eigenvalues of Cayley graphs and group characters.
Tue 6 Feb / 3:30 / ASB10908 Cedric Chauvre, SFU Inferring ancestral genomes with common intervals
Tue 20 Feb / 3:30 / ASB10908 Neil Robertson, Ohio State U. CANCELLED
SatSun 24-25 Feb /9:30 / U. Victoria Eighth Coast Combinatorics Conference Speakers: Several
Tue 27 Feb / 3:30 / ASB10908 Gena Hahn, Universite de Montreal CANCELLED
Tue 06 Mar / 3:30 / ASB10908 Francois Bergeron, UQAM A combinatorial classification of polynomials
Tue 13 Mar / 3:30 / ASB10908 Mike Zabrocki, York U. A Zoo of Hopf Algebras
Tue 20 Mar / 3:30 / ASB10908 Robert Samal, SFU On XY mappings
Tue 27 Mar / 3:30 / ASB10908 Jonathan Jedwab, SFU On XY mappings
Fall 2006
Tue 26 Sep / 3:30 / ASB10908 Tamon Stephen, SFU Colourful Simplicial Depth
Wed 27 Sep / 3:30 / ASB9705 Eyal Ackerman, SFU Maximum size of a $k$-quasi-planar graphs
Tue 10 Oct / 3:30 / (UBC) WMAX110 Joachim Rosenthal, U. Zurich Three challenges of Claude Shannon
Tue 17 Oct / 3:30 / ASB10908 Tomas Kaiser, U. West Bohemia Non-intersecting perfect matchings in cubic graphs
Tue 31 Oct / 2:30 / ASB10900 Dragos Cvetkovic, U. of Belgrade Signless Laplacians of finite graphs
Sat 11 Nov / 10:00 / Portland State U. 2006 Combinatorial Potlach Speakers: Brualdi + Gordon + DeVos
Tue 21 Nov / 3:30 / ASB10900 Kevin Purbhoo, UBC Puzzles, Tableaux, and Mosaics
Tue 05 Dec / 3:30 / (UBC) WMAX110 John Gimbel, University of Alaska Remarks on split graphs and related notions
Tue 12 Dec / 2:30 / ASB10900 Moshe Rosenfeld, University of Washington, Tacoma Spanning Graph Designs, an extension of the "Graph disease"
Tue 12 Dec / 3:30 / ASB10900 John Irving, St. Mary's University Counting Transitive Factorizations in the Symmetric Group
Summer 2006
   
Tue 7 May / 3:30 / ASB10908 Winfried Hochstaettler, Fern Univ at Hagen Online matching on a line
Thu 22 Jun / 9:30 / ASB10900 SFU Discrete Math Day Seven talks by distinguished visitors
Thu 29 Jun / 2:30 / AQ 3149 Winfried Hochstaettler, Fern Univ at Hagen On the game chromatic index of trees
Tue 4 Jul / 3:30 / K9509 Brian Lucena, American Univ. in Cairo Minimal forbidden minors for treewidth
Tue 8 Aug / 3:30 / ASB10900 Jacob Fox Ramsey-type results for intersection graphs:w
Spring 2006
Tue 24 Jan / 3:30 / ASB10900 Maria Chudnovski, Princeton U. The structure of bull-free graphs
Tue 14 Feb / 3:30 / ASB10900 Luis Goddyn, SFU Silver Cubes
Tue 28 Feb / 3:30 / (UBC) WMAX216 Shakhar Smorodinsky, Courant Inst. On K-sets in dimensions 2, 3 and 4.
Tue 14 Mar / 3:30 / ASB10900 Arie Bialostocki, University of Idaho Some Problems in View of Recent Developments of the Erdos Ginzburg Ziv theorem
Tue 21 Mar / 3:30 / ASB10900 Susan Barwick, University of Adelaide The geometry of linear perfect hash families
Tue 28 Mar / 3:30 / (UBC) WMAX216 Kee Yuen Lam, UBC The combinatorics of sums of squares as studied via topology
Tue 4 Apr / 3:30 / ASB10908 Aidan Roy, University of Waterloo Equiangular lines, mutually unbiased bases, and difference sets
Fall 2005
Tue 13 Sep / 3:30 / (UBC) WMAX216 Gabor Tardos, SFU Toward and Extremal Theory of Ordered Graphs
Tue 20 Sep / 3:30 / ASB10908 Brian Alspach, University of Regina Time constrained searching and sweeping
Tue 27 Sep / 3:30 / ASB10908 Richard Anstee, UBC Forbidden Configurations: An update
Tue 04 Oct / 3:30 / EAA1100 Matt DeVos, SFU Pentagon Colouring
Tue 11 Oct / 3:30 / ASB 10900 Bojan Mohar, SFU Quadrangulations, Eulerian triangulations, and 5-critical graphs
Tue 25 Oct / 3:30 / (UBC) WMAX216 David Kirkpatrick, UBC Minimizing precision/input in the evaluation of geometric primitives
Tue 08 Nov / 3:30 / (UBC) WMAX216 Luis Goddyn, SFU An Optimization Problem Arising from Video-on-Demand Broadcasting
Wed 09 Nov / 3:30 / ASB10908 Santosh Kabadi, U New Brunswick Integer Exact Network Synthesis Problem
Tue 15 Nov / 3:30 / ASB10908 Jonathan Jedwab, SFU Proof of the Barker Array Conjecture
Sat 19 Nov / 10:30 / Seattle U. 2005 Combinatorial Potlach Speakers: Mohar + Quinn + Caughman
Summer 2005
Tue 03 May / 3:30 / EAA1100 Cedric Chauve, Universite du Quebec a Montreal Conservation of combinatorial structure in genome rearrangement scenarios
Tue 17 May / 3:30 / EAA1100 Rados Radoicic, Rutgers University Intersection patterns of geometric objects
Tue 31 May / 3:30 / EAA1100 Danny Dyer, University of Regina Digraphs with small sweep number
Tue 21 Jun / 3:30 / EAA1100 Anna Galluccio, IASI-CNR, Roma, Italy Regular Join Graphs
Tue 28 Jun / 3:30 / ASB 10900 CANCELLED: Mordecai Golin, Hong Kong U. of Science The Knuth-Yao Quadrangle-Inequality & Total-Monotonicity
Wed 06 Jul / 3:30 / ASB 10900 Ebad Mahmoodian, Sharif University Problems and Motivations
Tue 19 Jul / 3:30 / EAA1100 Ron Aharoni, Technion Institute, Israel Topological Methods in Matching Theory
Spring 2005
Tue 18 Jan / 3:30 / EAA1100 Colin Percival, University of Oxford Matching with mismatches
Thu 10 Feb / 3:30 / EAA1100 Peter Horak, University of Washington Completing Latin squares
Tue 15 Feb / 3:30 / EAA1100 Binay Bhattacharya, Simon Fraser University Collection depots problem on networks
Tue 22 Feb / 3:30 / EAA1100 Evangelos Kranakis, Carleton University The Mobile Agent Rendezvous Problem
Mon 28 Feb / 4:00 / K9509 Chris Mitchell, Royal Holloway Cryptanalysis of methods for combining confidentiality and integrity
Tue 1 Mar / 3:30 / EAA1100 Nati Linial, U. Washington & Hebrew University Finite Metric Spaces - A quick overview
Tue 15 Mar / 3:30 / EAA1100 Frank Fiedler, Simon Fraser University The Search for More Golay Sequences
Tue 22 Mar / 3:30 / EAA1100 Petr Lisonek, Simon Fraser University Enumeration of Codes of Fixed Cardinality up to Isomorphism
Tue 29 Mar / 4:30 / AQ 3182 Laszlo Lovasz, Microsoft Research and Eotvos Lorand University Graph homomorphisms, statistical physics, and limits of graph sequences
Tue 05 Apr / 3:30 / EAA1100 Boaz Benmoshe, Simon Fraser University Guarding 1.5D terrains
Fall 2004
Tue 21 Sep / 2:30 / K9509 Abraham P. Punnen, University of New Brunswick The number of distinct tour values for the traveling salesman problem: one, two, three, all
Tue 28 Sep / 3:30 / EAA1100 Arash Rafiey, University of London Characterization of edge-colored complete graphs with properly colored Hamilton paths
Tue 5 Oct / 3:30 / EAA1100 Frank Fiedler, Simon Fraser On the degree of Mathon maximal arcs
Tue 12 Oct / 3:30 / EAA1100 Jonathan Jedwab, Simon Fraser A survey of the merit factor problem for binary sequences
Tue 19 Oct / 3:30 / EAA1100 Ladislav Stacho, Simon Fraser Asymptotics of random RNA
Tue 26 Oct / 3:30 / EAA1100 Jeffrey Farr, Simon Fraser Large caps with free pairs in PG(N,q)
Tue 2 Nov / 3:30 / EAA1100 Mohammad Ghebleh, Simon Fraser Circular chromatic number of even-faced torus graphs
Tue 9 Nov / 3:30 / EAA1100 Petr Lisonek, Simon Fraser Variable rate linear codes with an application to steganography
Tue 16 Nov / 3:30 / EAA1100 Luis Goddyn, Simon Fraser Two results for the Lonely Runner
Sat 20 Nov / 10:30 / Harbour Centre   Combinatorial Potlatch 2004
Tue 23 Nov / 3:30 / EAA1100 Pavol Hell, Simon Fraser Matrix partitions of perfect graphs
Tue 30 Nov / 3:45 / EAA1100 Xuding Zhu, National Sun Yat-sen University Circular coloring of Kneser graphs, Schrijver graphs and cones over graphs
Tue 7 Dec / 3:30 / EAA1100 Victor Dalmau, Universitat Pompeu Fabra Constraint Satisfaction Problems and Expressiveness
Summer 2004
Tue 18 May / 3:30 / EAA1100 Daniel Kral, Charles University Circular edge-colorings of graphs with large girth
Fri 28 May / 11:30 / EAA1100 Peter Pleasants, University of Queensland Almost disjoint families of 3-term arithmetic progressions
Fri 28 May / 2:30 / K9509 Nantel Bergeron, York University Combinatorial Hopf algebras
Mon 31 May / 2:30 / K9509 Bojan Mohar, University of Ljubljana Graph minors and graphs on surfaces
Tue 29 Jun / 2:30 / K9509 Marni Mishna, LaBRI, University of Bordeaux On the utility of effective D-finite symmetric functions in combinatorics
Tue 13 Jul / 3:30 / EAA1100 Bruce Reed, McGill University Vertex Colouring Edge Weightings
Tue 20 Jul / 2:30 / K9509 Nadya Shirokova, Inst. Hautes Etudes Sci. Space approach to invariants for families
Tue 27 Jul / 10:00 / Halpern Centre, Room 126 Roman Nedela, Slovak Academy of Sciences Regular maps - combinatorial objects relating different fields of mathematics
Tue 10 Aug / 3:30 / EAA1100 Moshe Rosenfeld, University of Washington Prisms over graphs
Tue 17 Aug / 3:30 / EAA1100 Tomas Kaiser, University of West Bohemia Eulerian colorings of graphs
Spring 2004
Tue 20 Jan / 3:30 / EAA1100 Jim Davis, Math & CS, U of Richmond Polynomial arithmetic behind the IEEE 802.12 standard for 100Mbit/s data transmission
Tue 27 Jan / 3:30 / EAA1100 Jeffrey Farr, Mathematics, SFU A new polynomial construction for some linear codes
Tue 03 Feb / 3:30 / EAA1100 Petr Lisonek, Mathematics, SFU Binary caps with many free pairs of points
Tue 10 Feb / 3:30 / EAA1100 Jan Manuch, Computing, SFU Inverse protein folding in 2D HP model
Tue 17 Feb / 3:30 / EAA1100 SEMINAR CANCELLED Reading break
Tue 24 Feb / 3:30 / EAA1100 Ladislav Stacho, Mathematics, SFU Traversal of quasi-planar subdivisions without using mark bits
Tue 01 Mar / 3:30 / EAA1100 Chris Mitchell, U of London, UK Universal cycles of permutations
Tue 02 Mar / 3:30 / EAA1100 Mahdad Khatirinejad Fard , Mathematics, SFU IC-Colorings and IC-indices of graphs
Thu 11 Mar / 11:30 / K9509 (!) Juergen Bierbrauer, Michigan Technological University Cyclic codes and their applications
Tue 16 Mar / 3:30 / EAA1100 Veselin Jungic, Mathematics, SFU Rainbow Ramsey Theory
Tue 23 Mar / 3:30 / EAA1100 Van Vu, Mathematics, UCSD Erdos-Folkman conjecture
Tue 30 Mar / 3:30 / EAA1100 Luis Goddyn, Mathematics, SFU From graceful labelings to Heawood embeddings
Tue 06 Apr / 3:30 / EAA1100 Jozsef Solymosi, Mathematics, UBC Applications of hypergraph regularity
Fall 2003
Tue 30 Sep / 3:30 / EAA1100 Jan Manuch, Math & CS, SFU On f-wise Arc Forwarding Index and Wavelength Allocations in Faulty All-optical Networks
Tue 07 Oct / 3:30 / EAA1100 Luis Goddyn, Mathematics, SFU Packing Group-non-vanishing A-paths
Tue 14 Oct / 3:30 / EAA1100 Ladislav Stacho, Mathematics, SFU Closure for the Property of Having a Hamiltonian Prism
Tue 21 Oct / 3:30 / EAA1100 Petr Lisonek, Mathematics, SFU A New Application of the Linear Programming Method in Coding Theory
Tue 04 Nov / 3:30 / EAA1100 Russel Martin, Computing, U of Warwick Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows
08-10 Nov / / UVic   Combinatorial Potlatch and 5th Coast Combinatorics Conference 
Thu 13 Nov / 3:30 / EAA1100 Zdenek Ryjacek, Mathematics, U of West Bohemia Closure Concepts, Stable Properties and Forbidden Subgraphs for Hamiltonicity
Tue 18 Nov / 3:30 / AQ 3149 Helaman and Claire Ferguson Mathematics in Stone and Bronze (The Alan Mekler Lecture)
Tue 25 Nov / 3:30 / EAA1100 Alireza Hadj Khodabakhshi, Computing, SFU A Fast Algorithm for Finding a Global Alignment Between Two Genomes
Spring 2003
Tue 07 Jan / 3:30 / EAA1100 Reza Naserasr, Mathematics, SFU Homomorphisms of Planar Graphs
Tue 14 Jan / 3:30 / EAA1100 Pavol Hell, Mathematics/Comp. Sci., SFU Interval Bigraphs and Circular Arc Graphs
Tue 21 Jan / 3:30 / EAA1100 Romeo Rizzi, University of Trento (Italy) Permutation Routing on POPS Networks
Tue 28 Jan / 3:30 / K9509 (!) Nantel Bergeron, Mathematics and Statistics, York University Quasi-symmetric Polynomials and Temperley-Lieb Invariants and Covariants
Tue 11 Feb / 3:30 / EAA1100 Tom Friedetzky, Comp. Sci., SFU A Proportionate Fair Scheduling Rule with Good Worst-case Performance
Tue 18 Feb / 3:30 / EAA1100 Jan Manuch, SFU Equations on Words and Defect Theorems
Tue 25 Feb / 10:30 (!) / K9509 Wendy Myrvold, University of Victoria Hunting for Torus Obstructions
Tue 25 Feb / 3:30 / EAA1100 Jaroslav Nesetril, Charles University, Prague Ramsey Classes and Homogeneous Graphs
Tue 04 Mar / 3:30 / EAA1100 Veselin Jungic, Mathematics, SFU Colorings of Plane Graphs with No Rainbow Faces
Tue 11 Mar / 3:30 / EAA1100 Jessie Zhu, SFU Phylogenetics Incorporating Stratophenetics
Tue 18 Mar / 3:30 / EAA1100 Riste Skrekovski, PIMS/SFU Coloring 1001 Maps on Surfaces
Tue 25 Mar / 3:30 / EAA1100 Stephanie van Willigenburg, Mathematics, U. British Columbia Acyclic Orientations and Excedence Permutations
Tue 15 Apr / 10:30 (!) / ASB 9896 (!) Yuri Gurevich, Microsoft Research What is Polynomial Time Anyway?
Tue 15 Apr / 3:30 / EAA1100 Joel Friedman, Mathematics, U. British Columbia A Proof of Alon's Second Eigenvalue Conjecture
Tue 29 Apr / 3:30 / EAA1100 Michael Molloy, Microsoft Research and University of Toronto Random Constraint Satisfaction Problems, aka Homomorphisms of Random Hypergraphs
Fall 2002
Tue 10 Sep / 2:00 / EAA1100 Juan Jose Montellano-Ballesteros, UNAM Mexico Polychromatic Cliques
Tue 17 Sep / 2:00 / EAA1100 Ladislav Stacho, Mathematics, SFU Edge-disjoint Spanners in Multi-dimensional Torus
Tue 24 Sep / 2:00 / EAA1100 Jan Manuch, SFU On the Descriptional and Computational Complexities of Infinite Words
Tue 01 Oct / 2:00 / EAA1100 Tom Brown, Mathematics, SFU On the Canonical Version of a Simple Theorem in Ramsey Theory
Tue 08 Oct / 2:00 / EAA1100 Petr Lisonek, Mathematics, SFU A Family of Complete Caps in PG(n,2)
Tue 15 Oct / 2:00 / EAA1100 Riste Skrekovski, PIMS/SFU Cyclic, Diagonal, and Facial Colorings
Tue 22 Oct / 2:00 / EAA1100 Veselin Jungic, Mathematics, SFU Radoicic's Conjecture and Tight Graphs
Tue 29 Oct / 2:00 / EAA1100 Bruce Reed, McGill University Tree Width and Excluded Minors
Tue 05 Nov / 2:00 / EAA1100 Richard Anstee, Mathematics, U. British Columbia Forbidden Configurations
Sat 09 Nov / 11-6 / UVic A. Proskurowski, B. Grunbaum, J. Siran Combinatorial Potlatch at UVic
Tue 12 Nov / 2:00 / EAA1100 Qianping Gu, Comp. Sci., SFU A 1.8-Approximation Algorithm for Embedding Hypergraphs in a Cycle
Tue 19 Nov / 2:00 / EAA1100 Daniel Kral, Charles University Channel Assignment Problem
Thu (!) 21 Nov / 2:00 / EAA1100 Vadim V. Lozin, Rutgers Boundary Classes of Graphs for NP-hard Problems
Tue 26 Nov / 2:00 / EAA1100 Ron Ferguson, PIMS/SFU Polyphase Sequences with Low Autocorrelation
Tue 03 Dec / 2:00 / EAA1100 Cynthia Loten , Mathematics, SFU Retractions and a Generalization of Chordal Graphs
Summer 2002    
Tue 14 May / 3:30 / EAA1100 Rados Rodoicic, MIT Rainbow Arithmetic Progressions
Tue 28 May / 3:30 / EAA1100 Sean McGuinness, U. Umea and Montana Circuits intersecting cocircuits in graphs and matroids.
Tue 11 Jun / 3:30 / EAA1100 Claude Tardif, U. Regina The projectivity of the graphs $G_d^k$
Tue 18 Jun / 3:30 / K9509 Joergen Bang-Jensen, U. Southern Denmark Steiner type problems in tournament-like digraphs
Tue 25 Jun / 3:30 / K 9500 (!) Winfried Hochstaettler, Brandenburg U. of Tech. Max-flow min-cut duality for a paint shop problem
Tue 02 Jul / 3:30 / EAA1100 Luis Goddyn, Mathematics, SFU Flows and Tensions on maps of high edge width.
Tue 09 Jul / 3:30 / EAA1100 Peter Higgins, Mathematics, Sur une Th\'eor\`eme de Sierpi\'nsk (In English!)
Tue 16 Jul / 3:30 / EAA1100 Khee-Meng Koh, Nat. U. of Singapore On the Chromaticity of graphs
Tue 23 Jul / 3:30 / EAA1100 UBC PiMS Event - Lovasz See their program for titles and abstracts.
Tue 30 Jul / 3:30 / EAA1100 Marnie Mishna Enumeration via D-finite Symmetric Functions
Tue 6 Aug / 3:30 / EAA1100 Luis Goddyn Chromatic numbers of matroids
Tue 6 Aug / 3:30 / EAA1100 Bill McCuaig Edmonds' arc-disjoint arborescences theorem
Spring 2002
Tue 05 Feb / 3:30 / EAA1100 Reza Naserasr, Math, SFU Homomorphisms from sparse graphs with large girth.
Tue 12 Feb / 3:30 / EAA1100 Qianping Gu, CS, SFU Permutation routing on WDM optical hypercubes I.
Tue 19 Feb / 3:30 / EAA1100 Qianping Gu, CS, SFU Permutation routing on WDM optical hypercubes II.
Tue 05 Mar / 3:30 / EAA1100 Luis Goddyn, Math, SFU Graph coloring and Matroids.
Tue 05 Mar / 3:30 / EAA1100 Tom Friedetzky, CS, SFU The Natural Work-Stealing Algorithm is Stable
Tue 19 Mar / 3:30 / EAA1100 Petr Lisonek, Math, SFU Caps and Binary Linear Codes
Tue 26 Mar / 3:30 / EAA1100 Petra Berenbrink, CS, SFU Simple routing strategies for Adversarial networks.
Tue 02 Apr / 3:30 / EAA1100 Pavol Hell, CS/Math, SFU Complexity of generalized list-colourings.
Tue 09 Apr / 3:30 / EAA1100 Laco Stacho, Math, SFU Edge-disjoint spanners in the Cartesian product of graphs
Fall 2001
Tue 18 Sep / 3:30 / EAA1100 Luis Goddyn, Math, SFU Binary Gray Codes with long bit runs.
Tue 25 Sep / 3:30 / EAA1100 Louis Ibarra, CS, SFU The clique-separator graph for chordal graphs and its subclasses.
Tue 02 Oct / 3:30 / EAA1100 Ladislav Stacho, Math, SFU New upper-bound for chromatic number.
Tue 09 Oct / 3:30 / EAA1100 Amitava Bhattacharya, TIFR A short proof of a EKR type theorem.
Tue 16 Oct / 3:30 / EAA1100 Juan Montellano, UNAM Anti-Ramsey Problems.
Tue 23 Oct / 3:30 / EAA1100 Ladislav Stacho, Math, SFU Spannin trees with bounded number of branch vertices.
Tue 30 Oct / 3:30 / EAA1100 Bill McCuaig, Math, SFU The Hat Game.
Tue 06 Nov / 3:30 / EAA1100 Mohammad Ghebleh, Math, SFU Uniuqely list colorable graphs.
Tue 13 Nov / 3:30 / EAA1100 Petr Lisonek, Math, SFU Geometric Representations of Graphs.
Tue 20 Nov / 3:30 / EAA1100 Luis Goddyn, Math, SFU Using the Nullstellensatz for edge list colouring.
Tue 27 Nov / 3:30 / EAA1100 Reza Naserasr, Math, SFU On the covering number of graphs.
Tue 04 Dec / 3:30 / EAA1100 Roded Sharan, Technion, Haifa Incomplete Directed Perfect Phylogeny.
Tue 11 Dec / 3:30 / EAA1100 Frederic Havet, CNRS, France Design of fault tolerant on-board networks with priorities
Tue 18 Dec / 3:30 / EAA1100 Mirka Miller, Newcastle, Australia Eccentric Digraphs
Summer 2001
Thu 10 May / 3:30 / EAA1100 John Mighton, Fields Inst. A New Reduction of Graph Theory and Binary Matroids
Tue 15 May / 3:30 / EAA1100 Sergei Bespamyatnikh, CS, U. British Columbia Graph of triangulations of convex polytopes in R^3
Tue 26 Jun / 3:30 / K9509 Matt DeVos, Princeton U. On Packing T-Joins
Tue 10 Jul / 3:30 / EAA1100 Moishe Rosenfeld, U. of Washington Hamiltonian Decomposition of Prisms over cubic graphs
Tue 17 Jul / 3:30 / K9509 Claude Tardif, U. of Regina Fractional aspects of Hedetniemi's conjecture
Spring 2001
Tue 30 Jan / 3:30 / K9509 Reza Naserasr, Math, SFU On $\Delta$-critical graphs
Wed 31 Jan / 2:30 / K9509 Brett Stevens, Math, SFU Packing and covering designs
Tue 06 Feb / 3:30 / K9509 Luis Goddyn, Math, SFU Range-restricted flows in regular matroids.
Tue 13 Feb / 3:30 / EAA1100 Jarik Nesetril, Charles University, Prague On a homomorphism duality for oriented trees.
Tue 20 Feb / 2:30 / EAA1100 Valentine Kabanets, Inst. for Advanced Study In search of an easy witness: Exponential time vs probabilistic polytime.
Tue 20 Feb / 3:40 / EAA1100 Wayne Broughton, Okanagan University Coll. Quasi-3 Designs and Hadamard Matrices.
Wed 28 Feb / 3:30 / K9509 Pavol Hell, SFU List homomorphisms and partitions
Tue 6 Mar / 3:30 / EAA1100 Steph Durocher, U. British Columbia The tangled tale of the rectilinear crossing number of K_n
Tue 13 Mar / 3:30 / EAA1100 Richard Anstee, U. British Columbia Small Forbidden Configurations
Tue 20 Mar / 3:30 / EAA1100 Brett Stevens, Math, SFU Packing Arrays II: Beyond Codes, the Triumphant Return of Designs!
Tue 27 Mar / 2:30 / EAA1100 Lou Ibarra, U. Victoria Dynamic algorithms for chordal and interval graphs.
Tue 27 Mar / 3:30 / EAA1100 Jonathan Jedwab, Hewlett-Packard Labs, Bristol Combinatorial Design Theory in an Industrial Research Lab
Wed 28 Mar / 2:30 / K9509 William Evans, U. British Columbia Recovering lines with fixed linear probes
Wed 28 Mar / 3:30 / K9509 Petr Lisonek, Math, SFU Classification of Binary Linear Codes with Small Codimension
Tue 3 Apr / 3:30 / EAA1100 Mateja Sajna, Capilano Coll. Decomposition of complete graphs into cycles of a fixed length
Wed 4 Apr / 3:30 / K9509 Veselin Jungic, Math, SFU Diophantine Ramsey Theory and Recurrence in Dynamical Systems
Tue 10 Apr / 3:30 / EAA1100 Ladislav Stacho, Math, SFU Edge Disjoint Cycles Through Prescribed Vertices
Tue 17 Apr / 3:30 / EAA1100 Nancy Neudauer, Pacific Lutheren U. Bicircular Matroids and Transversal Presentations