Abstracts

Andrii Arman
University of Manitoba

Colorful matchings in a graph
Suppose a committee consisting of \(m\) members has to match \(n\) candidates to \(n\) different positions. Each member of the committee proposes a matching, however the proposed matchings totally disagree, i.e. every candidate is matched to \(m\) different positions according to the committee members. Can a committee always find a compromise matching, i.e. a matching of candidates to positions such that for every committee member a \(1/m\) proportion of all candidates are assigned according to that committee member suggestion?

In my talk I will consider several variations of such questions. The talk is based on joint work with Vojtech Rödl and Marcelo Sales.



Gary Au
University of Saskatchewan

Generalized Catalan and Schröder Numbers via Hypercube Partitions
One of the (many!) combinatorial interpretations of the Catalan number \(c(n)\) is that it counts the number of ways we can iteratively bisect the unit interval into \(n\) subintervals. In this talk, we look into what happens to the above if we replaced the unit interval by a \(d\)-dimensional unit hypercube, and if we replaced bisections with orthogonal partitions of arbitrary arity. Studying these hypercube partitions leads us on a combinatorial journey that includes some unsurprising suspects such as plane rooted trees and Dyck/Schröder paths, as well as less unsurprising ones such as exact covering systems of the integers.

This is joint work with Fatemeh Bagherzadeh and Murray Bremner.



Nancy Clarke
Acadia University

Cops and Robber: When the Cops Need Glasses
Cops and Robber is a well-studied pursuit-evasion game played on graphs. In this talk, I’ll discuss several variations of the game in which the cops' ability to see the robber is impaired. In the farsighted (hyperopic) version of the game, the robber is invisible to the cop side unless outside the neighbourhood of a cop. We present a variety of results, including a characterization of the graphs on which a single cop suffices to guarantee a win, and we also consider graphs in terms of diameter and planarity. In the nearsighted (limited visibility) version of the game, the cops can only see the robber when the distance between them is at most a fixed parameter \(l\). We will see that the cops' strategy consists of a phase in which they need to see the robber (i.e. move within distance \(l\) of the robber), followed by a phase in which they capture the robber. For some graphs, it is the first phase which is the most expensive in terms of cops while, for others, it is the second. Our results include a characterization of those trees on which \(k\) cops are sufficient to guarantee a win for all \(l > 1\).

Work on the first version is joint with A. Bonato, D. Cox, S. Finbow, F. Mc Inerney, and M. Messenger, and on the second with D. Cox, C. Duffy, D. Dyer, S. Fitzpatrick, and M. Messinger.



Mark Kayll
University of Montana

König-Egerváry and Egerváry graphs
Fifty-six years ago, Jack Edmonds published his elegant characterization of the perfect matching polytope \(\mathcal{P}\) of a graph \(G=(V,E)\), i.e., the convex hull of the characteristic vectors of the perfect matchings of \(G\). Edmonds described \(\mathcal{P}\) polyhedrally as the set of nonnegative vectors in \(\mathbb{R}^E\) satisfying two families of constraints: `saturation' and `blossom'. We now call graphs for which the blossom constraints are essential Edmonds graphs and those for which the blossom constraints are implied by the others Egerváry graphs (aka `BvN graphs'). As it turns out, the second graph class interacts nicely with more familiar classes. For example, bipartite graphs are Egerváry---an assertion equivalent to the Birkhoff-von Neumann Theorem on doubly-stochastic matrices. More generally, König-Egerváry graphs are Egerváry. This talk introduces these ideas and shares a few results on Egerváry graphs. (Joint work with Jack Edmonds and Craig Larson.)



Bobby Miraftab
University of Lethbridge

Canonical tree decompositions and their applications
Tree-Decompositions are the corner-stone of many topics in graph theory. In this talk, we show that every locally finite graph has a canonical tree-decomposition that distinguishes all principal tangles (these include the ends and various kinds of large finite dense structures) efficiently.

As an application of our result, we present a graph-theoretical version of Stallings' theorem for transitive graphs with more than one end and also some applications for accessible graphs, virtually free graphs, hyperbolic graphs, and planar groups.



Dave Morris
University of Lethbridge

Automorphisms of direct products of some circulant graphs
The direct product of two graphs \(X\) and \(Y\) is denoted \(X \times Y\). This is a natural construction, so any isomorphism from \(X\) to \(X'\) can be combined with any isomorphism from \(Y\) to \(Y'\) to obtain an isomorphism from \(X \times Y\) to \(X' \times Y'\). Therefore, the automorphism group \(\mathrm{Aut}(X \times Y)\) contains a copy of \((\mathrm{Aut}\, X) \times (\mathrm{Aut}\, Y)\). It is not known when this inclusion is an equality, even for the special case where \(Y = K_2\) is a connected graph with only \(2\) vertices.

Recent work of B. Fernandez and A. Hujdurović solves this problem when \(X\) is a "circulant" graph with an odd number of vertices (and \(Y = K_2\)). We will present a short, elementary proof of this theorem, and discuss other recent developments.



Shahla Nasserasr
Rochester Institute of Technology

On the zero forcing number of graphs
Given an assignment of colours blue and white to the vertices of graph \(G\), the zero forcing rule determines a subset of white vertices to be re-coloured blue. The zero forcing process applies this rule in discrete time-steps until no more changes are possible. The zero forcing number of \(G\) is the minimum number \(Z(G)\) of vertices so that there exists an initial blue colouring with \(Z(G)\) vertices that is transformed to an all-blue colouring by the zero forcing process.

In this talk, some properties and applications of the zero forcing number will be discussed. Then an improvement of the best-known upper bound for the zero forcing number of claw-free cubic graphs will be given.



Ortrud Oellerman
University of Winnipeg

The threshold dimension and threshold strong dimension of a graph
Let \(G\) be a connected graph and \(u,v\) and \(w\) vertices of \(G\). Then \(w\) is said to resolve \(u\) and \(v\) if the distance from \(u\) to \(w\) does not equal the distance from \(v\) to \(w\). If there is either a shortest \(u-w\) path that contains \(v\) or a shortest \(v-w\) path that contains \(u\), then we say that \(w\) strongly resolves \(u\) and \(v\). A set \(W\) of vertices of \(G\) is a resolving set (strong resolving set), if every pair of vertices of \(G\) is resolved (respectively, strongly resolved) by some vertex of \(W\). A smallest resolving set (strong resolving set) of a graph is called a basis (respectively, a strong basis) and its cardinality, the metric dimension (respectively, the strong dimension) of \(G\). The threshold dimension (respectively, threshold strong dimension) of a graph \(G\), is the smallest metric dimension (respectively, strong dimension) among all graphs having \(G\) as a spanning subgraph. Graphs that are not spanning subgraphs of graphs with smaller metric dimension (or smaller strong dimension) are irreducible relative to the metric dimension (respectively, strong dimension). We present geometric characterizations for both the threshold dimension and threshold strong dimension of a graph and demonstrate the utility of these characterizations. We highlight some similarities and differences between these two invariants and show that they are not equal. We describe several bounds for these two invariants and discuss the existence of irreducible structures of a given order and dimension (strong dimension).

This is collaborative work of two research groups: Group 1: Lucas Mol, Matthew Murphy, Ortrud Oellermann; Group 2: Nadia Benakli, Novi Bong, Shonda Dueck, Linda Eroh, Beth Novick and Ortrud Oellermann.



Kris Vasudevan
University of Calgary

The role of random matrix theory (RMT) in neuronal correlations
Signed correlation matrices resulting from the BOLD fMRI or the intracranial EEG time-series provide an avenue to understand the interactions and information flow within a brain region or among different brain regions. One attribute that is commonly analyzed for interpretation purposes is the community structure of the correlation matrices. In this presentation, we focus on the use of random matrix theory (RMT) in separating out random correlations from empirical correlation matrices. We consider two examples of intracranial time-series, one from the CA1 region of the hippocampus of an anesthetized rat measured with multiple contact points of a single depth electrode and the other from the medial temporal lobe region and its neighbours of a human seizure patient collected with a surface-grid and depth electrodes. We examine the RMT to extract the nonrandom properties from the empirical correlation matrices and illustrate how spectral graph theory ideas may be used to analyze the community structure inherent in corresponding networks.

This is joint work with Michael Cavers.



Chi Hoi Yip
University of British Columbia

Van Lint--MacWilliams' conjecture and maximum cliques in Cayley graphs over finite fields
A well-known conjecture due to van Lint and MacWilliams states that if \(A\) is a subset of \(\mathbb F_{q^2}\) such that \(0,1 \in A\), \(|A|=q\), and \(a-b\) is a square for each \(a,b \in A\), then \(A\) must be a subfield \(\mathbb F_q\). This conjecture is often phrased in terms of the maximum cliques in Paley graphs. It was first proved by Blokhuis and later extended by Sziklai to generalized Paley graphs. In this talk, I will give a new proof of the conjecture and its variants, and show this Erdös-Ko-Rado property of Paley graphs extends to a larger family of Cayley graphs, which we call Peisert-type graphs. This is joint work with Shamil Asgarli (UBC).