 |
|
||||
- ROBERT BAILEY, University of Regina
Metric dimension of distance-regular graphs: an update [PDF]
-
A {\em resolving set} for a graph $G$ is a collection of vertices chosen so that any vertex of $G$ is uniquely identified by the list of distances to the chosen few. The {\em metric dimension} of $G$ is the smallest size of a resolving set.
At the 2009 CMS Summer Meeting in St. John's, I gave a talk entitled "Metric dimension of distance-regular graphs". Since that time, several papers on the subject have been written by myself and others. In this talk, I will give an overview of some recent results for various families of distance-regular graphs, and also some computer calculations determining the metric dimension of some small distance-regular graphs.
- ANDREA BURGESS, Ryerson University
Cops and robbers on graphs based on designs [PDF]
-
In the game of cops and robbers, a set of cops and a single robber occupy vertices of a graph, with cops and robber playing alternately, in each turn moving to an adjacent vertex or passing. The cops win if one of them occupies the same vertex as the robber, and the robber wins if he evades capture indefinitely. The {\em cop number} $c(G)$ is the smallest number of cops which guarantee that the cops win on the graph $G$.
Meyniel's conjecture states that for a connected graph $G$ on $n$ vertices, $c(G)=O(\sqrt{n})$; families of graphs which attain the conjectured asymptotically largest cop number are known as {\em Meyniel extremal}. Known Meyniel extremal families arise from incidence graphs of projective and affine geometries. Motivated by such results, we investigate the cop number of various graphs based on combinatorial designs, such as incidence graphs, point graphs and block intersection graphs. We give bounds on the cop number of such graphs, and in some cases find new Meyniel extremal families.
This is joint work with Anthony Bonato.
- SOPHIE BURRILL, Simon Fraser University
Combinatorics in arc diagrams: crossings, nestings and topology [PDF]
-
A variety of combinatorial objects, including matchings, set partitions and permutations, can be modelled using arc diagrams- a set of vertices on a horizontal line with arcs possibly connecting them. There are two natural ways to parameterize these diagrams: 1) by considering the number of arcs that mutually cross (crossings), and 2) by genus. We explore (also using nestings, an additional companion statistic to crossings) these two methods from an enumerative standpoint, providing links between them where appropriate.
- YI CAO, University of Alberta
DP-complete Problems Derived from Extremal NP-complete Properties [PDF]
-
In contrast to the extremal variants of coNP-complete problems, which are frequently DP-complete, many extremal variants of NP-complete problems are in P. We investigate the extremal variants of two
NP-complete problems, the extremal colorability problem with restricted degree and the extremal unfrozen non-implicant problem, and show that both of them are DP-complete. As far as we know, no extremal variant of an NP-complete problem has been shown to be DP-complete before.
This is a joint work with Dr. Joseph Culberson and Dr. Lorna Stewart.
- MICHAEL CAVERS, University of Calgary
Graphs with large distinguishing chromatic number [PDF]
-
The distinguishing chromatic number $\chi_D(G)$ of a graph $G$ is the minimum number of colours required to properly colour the vertices of $G$ so that the only automorphism of $G$ that preserves colours is the identity. It is known that for a graph $G$ of order $n$, the bound $1\leq\chi_D(G)\leq n$ holds, with equality in the upper bound only for complete multipartite graphs. We discuss properties of graphs with large distinguishing chromatic number and characterize the graphs $G$ of order $n$ satisfying $\chi_D(G)=n-1$ or $\chi_D(G)=n-2$.
- ADA CHAN, York University
Trivial Nomura algebra [PDF]
-
First introduced by Sylvester in 1867 as inverse orthogonal matrices, a type~II matrix
is an invertible $n\times n$ matrix that has no zero entry, whose inverse can be easily obtained by
inverting every entry, taking the transpose and multiplying by $n^{-1}$.
Hadamard matrices and spin models are well known examples of type~II matrices.
Nomura gave a construction of a formally dual pair of association schemes from each type~II matrix. Despite the potential of finding new dual pairs of association schemes from Nomura's construction, almost all of the type~II matrices we have examined yield the trivial association schemes. In this talk, we discuss what we can say in this disappointing situation.
- PETER DUKES, University of Victoria
Intersections of Latin Squares [PDF]
-
If we superimpose two latin squares on the same symbols and count the number of agreements, this is the \emph{intersection number} of the pair. Here, we consider the problem of determining which intersection numbers are possible, given the order of the squares.
Early considerations solved this problem when the two squares have the same order, say $n$. Roughly speaking, the result is that every value in $[0,n^2]$ is possible, except for a few values near the top of the interval.
Here, we consider and completely solve the following two parameter version of the problem. {\sl For fixed $m$ and $n$, $n<m$, what are the realizable intersection numbers for two latin squares, one of order $m$ and the other of order $n$}?
This is joint work with Jared Howell.
- CHRIS GODSIL, University of Waterloo
Graphs, Polytopes, Quadrics [PDF]
-
Let $X$ be a graph with adjacency matrix $A$ and eigenvalue $\theta$. The projections of the standard basis vectors onto the $\theta$-eigenspace of $A$ generate a convex polytope, and properties of this polytope relate in an interesting way to properties of $X$. We can use knowledge of the facets to derive the Erd\H{o}s-Ko-Rado theorem. We can also use information about the real quadrics that contain the vertices of the polytope to constrain the structure of $X$. In my talk I will explain these connections.
- ANGELE HAMEL, Wilfrid Laurier University
A Generalized Anonymity Metric for Probabilistic Attacks [PDF]
-
In theory, an anonymity network allows two participants, Alice and Bob, to communicate without an adversary being aware that the message Alice sends is the same one that Bob receives. However, in practice, a statistical attack on such a system is possible through observation of the patterns of sending and receiving. How anonymous is the communication really, and how can this anonymity be measured? In 2007 Edman et al. proposed a combinatorial model for this problem. In this talk we show how, by interpreting the problem in terms of contingency tables, we can define a new measure of the anonymity provided by the system. This measure generalizes two existing measures, and provides a new framework for future results. (Joint work with Jean-Charles Grégoire).
- PENNY HAXELL, University of Waterloo
Packing and covering in $r$-partite hypergraphs [PDF]
-
We give the first known nontrivial upper bound (for $r>3$) on the following old
problem known as Ryser's Conjecture. For an
$r$-partite $r$-uniform
hypergraph $H$, suppose the maximum size of a matching in $H$ is
$k$. Does there exist a cover of $H$ of size at most $(r-1)k$? Here a
cover is a set of vertices meeting all edges of $H$. It is immediate
that $H$ has a cover of size $rk$. We show that for the cases $r=4$
and 5,
there exists $x>0$ such that $H$ has a cover of size at most $(r-x)k$.
(Joint work with Alex Scott)
- GLENN HURLBERT, Arizona State University
EKR on Graphs and Lattices [PDF]
-
The classic theorem of Erd\H os, Ko, and Rado has generated a lot of activity in recent years. One new idea explores the structure of intersecting families of maximum size under the restriction that certain pairs of elements cannot be in the same set. This corresponds to investigating the largest intersecting family of independent sets of a graph. If some such family forms a star -- some element is in every set -- the graph is said to have the EKR property. A second consideration studies intersection of other objects, such as permutations and partitions (defined by sharing the same coordinate or block, respectively), and asking the usual Erd\H os-Ko-Rado and Hilton-Milner type questions. A third notion defines the intersection of elements of a lattice by to the rank of their meet. Here, a lattice is said to be EKR if a largest intersecting family of elements forms a star; that is, it is the upset of an atom. We discuss current advances in these areas, including joint work with Bekmetjev, Brightwell, Czygrinow, Fishel, Kamat, and Meagher.
- SAMUEL JOHNSON, Simon Fraser University
The exponential growth of restricted lattice paths [PDF]
-
Restricted lattice paths are effective statistical mechanical models of physical and chemical phenomena. The exponential growth factor of the number of lattice paths of size $n$ corresponds to the entropy in the statistical mechanical system. We give a systematic method for proving factors for families of models sharing a common submodel with known exponential growth. This is joint work with Marni Mishna.
- BEN LI, University of Manitoba
friendship 3-hypergraphs [PDF]
-
Let $(X,\mathcal{B})$ be a set system in which $\mathcal{B}$ is a set of 3-subsets of $X$. Then $(X,\mathcal{B})$ is a \textit{friendship $3$-hypergraph} if it satisfies the following property:
for distinct elements $u,v,w \in X$, there exists a unique fourth element $x \in X$
such that $\{u,v,x\}, \{u,w,x\}, \{v,w,x\} \in \mathcal{B}$. If a friendship $3$-hypergraph contains an element $f \in X$ such that $\{f,u,v\} \in B$ for all $u,v \in X \setminus \{f\}$, then it is called a \textit{universal friend $3$-hypergraph} and the element $f$ is called a \textit{universal friend} of the hypergraph.
In this presentation, we will discuss what we know about friendship $3$-hypergraphs and universal friend $3$-hypergraphs.
- JESSICA MCDONALD, Simon Fraser University
Average Degree in Graph Powers [PDF]
-
The $k$th power of a simple graph $G$, denoted $G^k$, is the graph with vertex set $V(G)$ where two vertices are adjacent if they are within distance $k$ in $G$. In this talk we are interested in finding lower bounds on the average degree of $G^k$, a problem that is related to both additive number theory (via Cayley graphs) and the famous Caccetta-H\"{a}ggkvist Conjecture. Here we share essentially best possible lower bounds when $k=4$ or $k\equiv 2$ (mod 3). Joint work with M. DeVos and D. Scheide.
- KAREN MEAGHER, University of Regina
Sperner partition systems [PDF]
-
A Sperner set system is a set system in which no set is a subset
of another. Sperner proved that the maximum size of a Sperner set
system on $\{1,2,\dots,n\}$ is $\binom{n}{\lfloor
\frac{n}{2}\rfloor }$ and the only systems meeting this bound are
the middle levels of the poset of sets ordered by inclusion.
A \textsl{Sperner partition system} is a set of partitions with the
property that no class from one partition is the subset of a class
from another partition. A Sperner partition system can be considered
to be a resolvable Sperner set system. In 2005 Lucia Moura,
Brett Stevens and I proved a bound on the size of a Sperner partition
system and showed that this bound can be met if the size of the
classes in the partitions are all equal. Recently, P. C. Li and I
determined bounds on the sizes of some Sperner partition systems when the
sizes of the classes cannot be all the same.
- MARNI MISHNA, Simon Fraser University
Towards generating random mammalian genomes [PDF]
-
Genome arrangements, a major mechanism of evolution, shuffle genetic material along chromosomes. Thus, a now standard approach models groups of close genomes as signed permutations. The correct data structure to study permutations in this context is the common interval tree. In this talk we will describe the process of considering tree parameters to refine the class of common interval trees (hence permutations) to those that represent mammalian genomes well. These refinements are particularly amenable to Boltzmann random generation and analytic enumerative techniques. Work in collaboration with Mathilde Bouvel, Cedric Chauve, Rosemary McCloskey, Cyril Nicaud and Carine Pivoteau.
- JOY MORRIS, Lethbridge
Structure of circulant graphs [PDF]
-
Some fairly recent deep results using Schur rings have provided a means of classifying circulant graphs. I will present this classification, and discuss some asymptotic and other results that follow from it.
- ORTRUD OELLERMANN, University of Winnipeg
The Average Connectivity of Graphs and Digraphs [PDF]
-
The connectivity between a pair $u,v$ of vertices in a graph $G$ is the maximum number of pairwise internally disjoint $u$--$v$ paths in $G$. The average connectivity of $G$ is the average connectivity between pairs of vertices of $G$ taken over all pairs. Analogous concepts can be defined for digraphs. We survey known results on this subject and present several open/partially solved problems including: (i) the problem of finding the maximum connectivity of a subgraph in a graph with a given average connectivity; (ii) the problem of finding the maximum average connectivity among all orientations of a given graph $G$; (iii) the maximum average connectivity among all graphs with a given degree sequence.
- ALISON PURDY, University of Regina
EKR-type results using the method of Ahlswede and Khachatrian [PDF]
-
In 1997, Ahlswede and Khachatrian published what is now commonly known as the Complete EKR Theorem. Although there have been numerous papers proving EKR-type results for objects other than sets, the techniques used by Ahlswede and Khachatrian do not appear to have received the attention that the significance of the theorem warrants. In this talk I will discuss attempts to adapt these techniques for use on other objects. This is joint work with Karen Meagher.
- MATEJA SAJNA, University of Ottawa
On Sheehan's Conjecture for graphs with symmetry [PDF]
-
It is known that every simple regular graph of degree $d$ that has a Hamilton cycle in fact possesses a second Hamilton cycle if $d$ is odd or $d \ge 300$. Sheehan conjectured that the statement is also true for $d=4$, which would imply that it is true for every $d > 2$. Fleischner showed that Sheehan's conjecture fails for 4-regular multigraphs. In this talk, we show that Sheehan's conjecture is true for 4-regular vertex-transitive simple graphs, and present some other recent results on the conjecture for regular simple graphs with a sufficiently large automorphism group. This is joint work with Andrew Wagner.
- CHRIS SOTEROS, University of Saskatchewan
Self-Avoiding Polygon Models of Polymer Entanglements [PDF]
-
With the goal of understanding polymer entanglements, for over 20 years there has been interest in questions about knotting and linking of self-avoiding polygons on the simple cubic lattice. Notably, in 1988 Sumners and Whittington proved that all but exponentially few sufficiently long self-avoiding polygons are knotted. This proved the long standing Frisch-Wasserman-Delbruck conjecture that sufficiently long ring polymers will be knotted with high probability. Since then there has been progress both theoretically and numerically using lattice polygon models to investigate polymer entanglements. Much of this progress has been motivated by questions arising from the study of DNA topology. For lattice models, these questions lie at the interface between statistical mechanics, enumerative combinatorics, topology, graph theory and applied probability/Monte Carlo methods. I will review progress made and highlight new results and open problems, especially in the context of extensions of the Sumners and Whittington theoretical approach to questions about knotting and linking in self-avoiding polygon models.
- BRETT STEVENS, Carleton University
Linear feedback shift registers and covering arrays [PDF]
-
The set of fixed length subintervals of a linear feedback shift register form a linear code. A very nice theorem of Bose from 1961 proves that these codewords form the rows of a covering array of strength $t$ if and only if the dual linear code has minimum weight $t+1$. Munemasa observed that whenever the length of the intervals is less than a generous bound, the dual code is the Hamming code which has minimum distance 3 and this the covering array is guaranteed to have strength 2. In fact the only 3-coverage that is missing corresponds to the weight-3 multiples of the generating polynomial of the LFSR. We use this and results on difference sets over finite fields to construct a new famlily of strength 3 covering arrays which improve many best known upper bounds on covering arrays
- AMY WIEBE, Simon Fraser University
Golay sequence and array pairs [PDF]
-
Golay complementary sequence pairs solve several problems in digital information processing. They have a rich existence pattern which includes several infinite families over different alphabets. Many families of Golay sequence pairs can be viewed as the projection of Golay array pairs. This multi-dimensional viewpoint considerably simplifies the construction and enumeration of Golay sequence pairs. We give an unexpected application of this approach which allows a simple reinterpretation of some classical and recently-discovered Golay sequence pairs.
This is joint work with Jonathan Jedwab and Matthew Parker.
- KAREN YEATS, Simon Fraser University
Feynman graphs and a chord diagram expansion [PDF]
-
Feynman graphs have a lot of fun combinatorial structure. Without expecting any background in physics, I will set up the situation and discuss how by playing with some recurrences we can get an expansion in terms of chord diagrams for some Green functions.
