The Twelfth Prairie Discrete Math Workshop will be held in Winnipeg, Manitoba 16-17 May 2016 at the University of Manitoba. The purpose of this two-day meeting is to bring together researchers in discrete mathematics from across the prairies and neighbouring provinces and states. The topics of the meeting will be areas of discrete mathematics including graph theory, design theory, combinatorial enumeration, and combinatorial algorithms.
This workshop is supported by PIMS and the University of Manitoba.
Location: University of Manitoba, Winnipeg, Manitoba, Canada
Dates: 16-17 May 2016
This meeting immediately follows the Western Canada Linear Algebra Meeting, also being held at the University of Manitoba.
Karen Gunderson (University of Manitoba)
Participants are required to register. Those submitting talks or applying for support must do so by 1 April 2016. There is no registration fee.
Submissions for contributed talks and applications for student support can be made during the registration process.
Those wishing to submit a talk or poster can do so during registration. Talks will be 20 minutes, followed by a 5 minute question period. Titles and abstracts for talks should be submitted by 1 April 2016.
Canad Inns Fort Garry, 1824 Pembina Highway Winnipeg, MB R3T 2G2
Phone: 1-888-33-CANAD (22623)
This hotel is approximately 2.7 km from the Department of
Mathematics, along a greenway path that connects to the university
(30 minute walk). It is also located along bus routes that go to
the university (buses 60 and 160).
Four Points by
Sheraton, Winnipeg South, 2935 Pembina Highway, Winnipeg, MB,
R3T 2H5
Phone: 866-716-8133
This hotel is approximately 4.1 km from the Department of Mathematics.
Those who wish to stay in residences on campus may book it directly:
Conferences
and short term stays.
2016 Short
stay application form
All talks will be held in the Robert B. Schultz Lecture Theatre, located in St. John's College. (Note: Changed from original location!) A google map with some locations marked is available here: Google map
Information on parking at the University is available here: Visitor parking
A small number of parking passes will be provided on a first-come, first-served basis. To request a parking pass, please contact the organizer.
Wireless internet access is available at the University of Manitoba via Eduroam, which is set up by your home institution if they are a participant.
Some funds may be available in support of accommodation costs for graduate students and early-career researchers. Preference for support will be given to those giving a talk. Those applying for support should do so using the registration form and must apply by 15 April 2016. (initial deadline was extended)
Participants requesting support must indicate this during the registration process and send a brief CV and a paragraph describing why they would like to attend to karen.gunderson@umanitoba.ca.
All talks will take place in the Robert B. Schultz Lecture Theatre. (Note: Changed from original location!)
| Time | Speaker | Title |
|---|---|---|
| 9:00-9:20 | Coffee | |
| 9:20-9:30 | Opening remarks | |
| 9:30-10:30 | Plenary: Jamie Radcliffe | The pleasures of counting (substructures in graphs) |
| 10:30-11:00 | Coffee | |
| 11:00-12:00 | Ortrud Oellermann | Progress on Saito's conjecture |
| 12:00-13:30 | Lunch | |
| 13:30-14:30 | Joy Morris | Colour-preserving automorphisms of Cayley graphs |
| 14:30-15:00 | Danny Rorabaugh | (3,1)-colorings of 4-regular graphs |
| 15:00-15:30 | Coffee | |
| 15:30-16:00 | Robert Craigen | An overlap graph technique for circulant partial Hadamard matrices |
| 16:00-16:30 | Robert Bailey | Generalized Howell designs with few empty cells |
| Time | Speaker | Title |
|---|---|---|
| 9:00-9:30 | Coffee | |
| 9:30-10:30 | Plenary: Brian Alspach | Cayley graphs and pancyclicity |
| 10:30-11:00 | Coffee | |
| 11:00-11:30 | Andrii Arman | On the maximal size of a k-uniform intersecting family with cover number k |
| 11:30-12:00 | Matthew Schmirler | Strand passage statistics in an interacting self-avoiding polygon model |
| 12:00-13:30 | Lunch | |
| 13:30-14:30 | Ben Li | Properties of total vertex covers and efficient
algorithms for computing minimum total vertex covers for some graph classes |
| 14:30-15:00 | Coffee | |
| 15:00-15:30 | Andriy Prymak | Lower bound on the number of 4-cliques in a strongly regular graph |
Speaker: Brian Alspach (University of Newcastle)
Title: Cayley graphs and pancyclicity
Abstract: A graph is pancyclic if it contains cycles of all possible lengths from 3 through the order of the graph. There are several obvious variations of this notion arising from features such as girth, bipartiteness, etc. In this talk I shall discuss the current state of affairs for Cayley graphs and pancyclicity.
Speaker: Andrii Arman (University of Manitoba)
Title: On the maximal size of a $k$-uniform intersecting family with cover number $k$
Abstract: A $k$-uniform hypergraph $\mathcal{F}$ is called an intersecting hypergraph iff any two edges of $\mathcal{F}$ have a non-empty intersection. A subset $C$ of vertices of $\mathcal{F}$ is called a cover (or a transversal) if every edge of $\mathcal{F}$ has a non-empty intersection with $C$. The cover number of $\mathcal{F}$ is the number of vertices in the smallest cover of $\mathcal{F}$. Define $r(k)$ to be the maximal size of intersecting hypergraph $\mathcal{F}$ with a cover number $k$. In 1975, Erdős and Lovász proved that $r(k)$ is at most $k^{k}$. In 1994, Tuza improved the upper bound by a constant factor. In this talk I will outline the proof of a new upper bound which is of the order $k^{k-1}$. This is a joint work with Troy Retter.
Speaker: Robert Bailey (Grenfell Campus, Memorial University)
Title: Generalized Howell designs with few empty cells
Abstract: A generalized Howell design, $\mathrm{GHD}(s,v)$, is an $s\times s$ array whose entries are either empty or contain a triple from a set of $v$ symbols, with the properties that (i) every symbol occurs exactly once in each row and each column, and (ii) no pair of symbols occurs in more than one entry of the array. GHDs may be obtained from mutually orthogonal Latin squares (if there are no empty cells), or from doubly resolvable designs (when the number of empty cells is a large as possible). In this talk, we will consider GHDs with one or two empty cells in each row and column.
This is joint work with Julian Abel, Andrea Burgess, Peter Danziger and Eric Mendelsohn.
Speaker: Robert Craigen (University of Manitoba)
Title: An overlap graph technique for circulant partial Hadamard matrices
Abstract: A partial Hadamard matrix is a rectangular $(1,-1)$-matrix whose rows are mutually orthogonal. It is circulant if it can be completed to a circulant matrix. Clearly all row sums are equal. If it is $k\times n$ with row sum $r$, we use notation $r-H(k\times n)$. The pertinent question: for given $n$ and $r$, maximize $k$. We show a digraph technique for attacking this question that generalizes the standard construction of de Bruijn graphs.
Speaker: Ben Li (University of Manitoba)
Title: Properties of total vertex covers and efficient algorithms for computing minimum total vertex covers for some graph classes
Abstract: This talk will focus mainly on a variation of vertex covers, known as total vertex covers. I will present some properties of total vertex covers and an algorithm for computing optimal total vertex covers in chordal graphs. I will also present an algorithm for computing a minimum-weight total vertex cover in weighted trees.
Speaker: Joy Morris (University of Lethbridge)
Title: Colour-preserving automorphisms of Cayley graphs
Abstract: A Cayley graph Cay$(G;S)$ on a group $G$ with connection set $S=S^{-1}$ is the graph whose vertices are the elements of $G$, with $g\sim h$ if and only if $g^{-1}h\in S$. Assign a colour $c(s)$ to each $s\in S$ so that $c(s)=c(s^{-1})$ and $c(s) \neq c(s')$ when $s'\neq s,s^{-1}$; this is a natural (but not proper) edge-colouring of the Cayley graph.
The most natural automorphisms of any Cayley graph are those that come directly from the group structure: left-multiplication by any element of $G$; and group automorphisms of $G$ that fix $S$ setwise. It is easy to see that these graph automorphisms either preserve or permute the colours in the edge-colouring defined above. Conversely, we can ask: if a graph automorphism preserves or permutes the colours in this natural edge-colouring, need it come from the group structure in one of these two ways?
I will explore the answer to this question for a variety of families of groups and of Cayley graphs on these groups.
Speaker: Ortrud Oellermann (University of Winnipeg)
Title: Progress on Saito's Conjecture
Abstract: For a given graph property $P$ we say a graph $G$ is locally $P$ or closed locally $P$ if the open neighbourhood (closed neighbourhood, respectively) of every vertex induces a graph that has property $P$. A graph $G$ is Chvátal-Erdős if its independence number is bounded above by the connectivity of $G$, i.e., $\alpha(G) \le \kappa(G)$. It is well-know that every Chvátal-Erdős graph of order at least $3$ is hamiltonian. Saito (2008) conjectured that every connected, closed locally Chvátal-Erdős graph of order at least 3 is hamiltonian. We define a graph to be $k$-$P_3$-connected if for any pair of nonadjacent vertices $u$ and $v$ there exist at least $k$ distinct $u$-$v$ paths of order $3$ each. The $P_3$-connectivity of a graph, denoted by $\kappa^{P_3}(G)$, is the smallest $k$ for which $G$ is $k$-$P_3$-connected. We make progress toward proving Saito's conjecture by showing that if $G$ is a connected graph of order at least $3$ such that $\alpha(\langle N[v] \rangle) \le \kappa^{P_3}(\langle N[v] \rangle)$ for all $v \in V(G)$, then $G$ is fully cycle extendable.
(This talk is based on joint work with S. van Aardt, M. Frick, J. Dunbar and J.P. de Wet.)
Speaker: Andriy Prymak (University of Manitoba)
Title: Lower bound on the number of $4$-cliques in a strongly regular graph
Abstract: I will present a new lower bound on the number of $4$-cliques in a strongly regular graph (SRG). This bound is obtained using Euclidean representation of SRGs and Cauchy-Schwarz inequality in a space of spherical harmonic polynomials. As an application, it will be shown that there is no SRG with parameters $(460,153,32,60)$, which is a new result. The bound was also used as the first step to establish non-existence of a $(76,30,8,14)$ SRG.
Speaker: Jamie Radcliffe (University of Nebraska, Lincoln)
Title: The Pleasures of Counting (substructures in graphs)
Abstract: Many graph theory questions concern things as the largest matching, the largest clique, or the largest independent set in a graph. I will discuss a range of problems that consider instead the number of matchings, the number of independent sets, etc. These problems have deep roots in the history of graph theory, but (relatively) recently the area has blossomed.
The problems have many pleasing features. They are fundamental and simple to state, yet attacking them has involved a wide range of approaches and techniques. Even better, fascinating problems in this area remain open.
Speaker: Danny Rorabaugh (Queen's University)
Title: $(3, 1)$-colorings of $4$-regular graphs
Abstract: Using edge cuts and Tutte's $1$-Factor Theorem, Tashkinov (1982) settled the Berge-Sauer conjecture: Every $4$-regular simple graph does indeed contain a $3$-regular subgraph. The question remains open, however, for $4$-regular pseudographs, that is, for graphs with loops and multi-edges allowed.
Bernshteyn (2014) introduced the use of edge-colorings as an approach to this problem, proving that a $4$-regular pseudograph contains a $3$-regular subgraph if and only if it admits an ordered $(3, 1)$-coloring. A $(3, 1)$-coloring of a $4$-regular graph is an edge coloring in which every vertex $v$ is incident to 3 edges of a color $i_v$ and $1$ edge of a different color $j_v$ . The coloring is ordered provided the colors are linearly ordered and $i_v < j_v$ at every vertex $v$. We completely characterize $(3,1)$-colorable pseudograph, though a characterization of the ordered-$(3, 1)$-colorable pseudograph remains at large.
This is joint work with Bernshteyn, Khormali, Martin, Rollin, Shan, and Uzzell.
Speaker: Matthew Schmirler (University of Saskatchewan)
Title: Strand Passage Statistics in an Interacting Self-Avoiding Polygon Model
Abstract: We model here the action of the enzyme type-II topoisomerase on circular DNA using self-avoiding polygons (SAPs) in the simple, face-centred and body-centred cubic lattices. Samples of essentially independent SAPs containing a specific fixed strand passage structure are generated via Composite Markov Chain Monte Carlo simulations. Strand passages are performed on these SAPs, the results of which are used to estimate probabilities of changing knot types as well as a knot comparison factor based on the local geometry at the strand passage site.