Past Combinatorics Seminars

List of past schedules for the University of Manitoba Combinatorics Seminar.

• Fall 2019, Winter 2020, and Winter 2021 talks were posted to the mathematics department website.
• Fall 2021
• Winter 2019
• Fall 2018
• Winter 2018
• Fall 2017
• Winter 2017
• Fall 2016
• Winter 2016
• Fall 2015

Fall 2021 Schedule

Abstracts

24 September 2021, 2:30 pm, Zoom

Speaker: Christopher van Bommel (Manitoba, Math)
Title: Fidelity of Quantum State Transfer on Paths with Potentials

Abstract: Quantum computing is believed to provide many advantages over traditional computing, particularly considering the speed at which computations can be performed. One of the challenges that needs to be resolved in order to construct a quantum computer is the transmission of information from one part of the computer to another. This transmission can be implemented by spin chains, which can be modeled as a graph, and analyzed using algebraic graph theory. The goal of quantum communication is to transmit information with a high level of accuracy, or fidelity. We consider a continuous time quantum walk on an unweighted path on n vertices, to which a loop (potential) of weight w has been added at each end vertex and discuss the fidelity that can be achieved.
This talk is based on joint work with Steve Kirkland.

1 October 2021, 2:30 pm, Zoom

Speaker: Shahin Kamali (Manitoba, CS)
Title: Algorithms for Burning Graph Families

Abstract: Graph burning is a simple model for the spread of social influence in networks. The objective is to measure how quickly a "fire", e.g., a piece of fake news, can be spread in a network. The burning process takes place in discrete rounds. In each round, a new fire breaks out at a vertex, while the old fires extend to their neighbours and burn them. A burning schedule selects where the new fire breaks out at each round, and the burning problem asks for a schedule that burns all vertices in a minimum number of rounds. In this talk, we review some recent algorithmic results for burning families of graphs that include graphs of bounded path-wdith, tree-width, pathlength, and certain families of dense graphs.

8 October 2021, 2:30 pm, Zoom

Speaker: Narad Rampersad (Winnipeg)
Title: Computer proofs on some combinatorials congruences

Abstract: The classical congruence result of Lucas (1878) for the binomial coefficients "n choose m" modulo a prime p shows that looking at the base-p representations of n and m is often an efficient way to determine divisibility properties of the binomial coefficients modulo p. Many authors have studied divisibilty properties of famous combinatorial sequences along these lines. For instance, Alter and Kubota (1971) studied the Catalan numbers modulo p. Deutsch and Sagan (2006) looked at a variety of other sequences, such as the Motzkin numbers, central Delannoy numbers, Apery numbers, etc. Rowland and Yassawi (2015) and Rowland and Zeilberger (2014) showed that finite automata may be the most appropriate way to describe congruence properties of these types of sequences. In this talk we show how to combine the method of Rowland and Zeilberger with the computer software Walnut, which can prove many properties of so-called "automatic sequences", to give very quick, fully automated proofs of some of these congruence properties.

15 October 2021, 2:30 pm, Zoom

Speaker: Hermie Monterde (Manitoba, Math)
Title:Continuous-time quantum walks and twin vertices

Abstract: Undirected graphs are used to model quantum spin networks, with the vertices and edges representing the qubits and their interactions, respectively. Each of these qubits has an associated quantum state that contains information, and in order to construct an operational quantum computer, two tasks must be performed: the accurate transmission of quantum states from one location in the quantum computer to another, and the generation of entanglements between quantum states.

Let $G$ be an undirected graph, and $M$ be a Hermitian matrix associated with $G$. By axioms of quantum mechanics, the matrix $U(t)=e^{itM}$ governs the evolution of the quantum system represented by $G$ at any time $t$ and determines a continuous-time quantum walk on $X$. The entries of $U(t)$ give information about the probability of state transfer between any two vertices of $G$ at time $t$. In particular, if $|U(\tau)_{j,k}|^2=1$, then we say that perfect state transfer occurs from vertex $j$ to vertex $k$ at time $\tau$, while if $|U(\tau)_{j,k}|^2$ can be made arbitrarily close to 1 by appropriate choices of $\tau$, then we say that pretty good state transfer occurs from $j$ to $k$. On the other hand, if entries on the $j$th and $k$th columns of $U(t)$ are zero at time $\tau$ except for those indexed by $j$ and $k$, then we say that fractional revival occurs between vertices $j$ and $k$ at time $\tau$.

In this talk, we look at the properties perfect state transfer, pretty good state transfer and fractional revival, as well as determine which of these quantum phenomena occur between twin vertices in an undirected graph.

22 October 2021, 3:30 pm (Note the unusual time!), Zoom

Speaker: Kyle Murphy (Dakota State University)
Title: Maximizing five cycles in $K_r$-free subgraphs.

Abstract: Recently, Palmer and Gerbner defined the term $F$-Tur\'an Good to describe a graph $H$ which is unique maximized by the Tur\'an graph for all sufficiently large $F$-free graphs. Along with Bernard Lick\'y we used the flag algebra method to prove that $C_5$ is $K_{r+1}$-Tur\'an Good for $r \geq 3$. In this talk, I will discuss this result, in addition to giving a brief introduction to the flag algebra method.

29 October 2021, 2:30 pm, Zoom

Speaker: Marcelo Tadeu Sales (Emory)
Title: Ramsey and density results for approximate arithmetic progressions

Abstract: Let $AP_k = \{a,a+d,...,a+(k−1)d\}$ be an arithmetic progression of length k. For a given $\varepsilon > 0$, we call a set $AP_k(\varepsilon) = \{x_0,...,x_{k−1}\}$ an $\varepsilon$-approximate arithmetic progression of length k if for some a and d, $|x_i −(a+id)|< \varepsilon d$ holds for all $i \in \{0,1...,k−1\}. In this talk we discuss numerical aspects of Van der Waerden and Szemeredi type of results in which arithmetic progressions are replaced by their $\varepsilon$-approximation.

5 November 2021, 2:30 pm, Zoom

Speaker:Colin Desmarais (Uppsala)
Title: The size of the root cluster in preferential attachment trees after percolation

Abstract: A random recursive tree is a rooted tree constructed by successively choosing a node uniformly at random and adding a child to the selected node. A random preferential attachment tree is grown in a similar manner, but the node selection is made proportional to a linear function of the number of children of a node. Preferential attachment trees are the tree version of the Barabasi-Albert preferential attachment model.

In this talk, I will discuss Bernoulli bond percolation on random preferential attachment trees. For some value p between 0 and 1, every edge in the tree is either kept with probability p or removed otherwise, independently of all other edges. I will show how to use methods of analytic combinatorics to retrieve limiting distributions, after proper rescalings, for the size of the root cluster; the component containing the root after performing percolation.

19 November 2021, 2:30 pm, Zoom

Speaker:Neal Bushaw (Virgina Commonwealth)
Title: Rainbow Saturation

Abstract: A graph G is `rainbow H-saturated' if there is some proper edge-coloring of G which is rainbow H-free (that is, it has no copy of H whose edges are all colored distinctly), but where the addition of any edge makes such a rainbow H-free coloring impossible. Taking the maximum number in such a saturated graph yields the rainbow Turan numbers (introduced formally by Keevash, Mubayi, Sudakov, and Verstraete, although they were implicit in some earlier work). In this talk we examine the corresponding rainbow saturation number -- the minimum number of edges among all rainbow H-saturated graphs. This is joint work with Dan Johnston and Puck Rombach.

3 December 2021, 2:30 pm, Zoom

Speaker:Adam Volk (Nebraska at Lincoln)
Title: Saturation Problems and an Introduction to Weak Saturation

Abstract: A graph is H-saturated if it does not contain any copy of H as a subgraph, but adding any missing edge creates at least one copy of H. A popular problem in extremal graph theory is finding the minimum number of edges in such graphs for various choices of H. In this talk, we will consider counting subgraphs other than edges in this context, as well as another potential domain: weakly saturated graphs.

10 December 2021, 2:30 pm, Zoom

Speaker: Andriy Prymak
Title: Every 3-dimensional convex body can be covered by 14 smaller homothetic copies

Abstract: We show that every 3-dimensional convex body can be covered by 14 smaller homothetic copies. The previous result was 16 established by Papadoperakis in 1999, while a conjecture by Hadwiger is 8. We modify Papadoperakis's approach and develop a discretization technique that reduces the problem to verification of feasibility of a number of linear programs with rational coefficients, which is done with computer assistance using exact arithmetic.

Winter 2019 Schedule

Abstracts

1 March 2019, 3:30 pm, 418 Machray Hall

Speaker: Rob Craigen
Title: Orthogonal matrices with zero diagonal

Abstract: TBA

15 March 2019, 3:30 pm, 418 Machray Hall

Speaker: William Kocay
Title:TBA

Abstract: TBA

28 March 2019 (Thursday), 4:00 pm, 418 Machray Hall

Speaker: Andriy Prymak
Title: On illumination of the boundary of a convex body in E^n, n=4,5,6.

Abstract: TBA

Fall 2018 Schedule

Abstracts

14 September 2018, 3:30 pm, 415 Machray Hall

Speaker: Colin Desmarais (Uppsala)
Title: Degree distributions of generalized hooking networks

Abstract: A hooking network is grown from a set of graphs called blocks, each block with a labelled vertex called a hook. At each step in the growth of the network, a vertex called a latch is chosen among the vertices of the hooking network, and a block is attached by joining the hook of the block with the latch. These graphs generalize trees, which can be thought of as hooking networks grown from a single edge as the only block.

In this talk, I will show how to use the theory of generalized Pólya urns to prove multivariate normal limit laws for the degree distributions of randomly grown hooking networks, where the latch and the block to be attached at each step are both chosen uniformly at random. I will also briefly mention how similar results are reached when the latch is chosen in a preferential attachment scheme, and when the blocks are chosen proportional to weights assigned to each block.

28 September 2018, 3:30 pm, 415 Machray Hall

Speaker:Ranganathan Padmanabhan
Title: $PG(2,3)$ exists over $k$ implies $3=0$ in $k$

Abstract: It is well known that the smallest projective plane exists in $PG(2, k)$ for some field $k$ if and only if $2 = 0$ in $k$ (see [1], [2] or [4]). However, it is suprising that a similar result about the next case has not been studied so far. Here we prove a similar theorem for projective planes of order 3 : the 13-point geometry $PG(2, 3)$ exists in $PG(2, k)$ for some field $k$ if and only if $3 = 0$ in $k$. Furthermore we show that the result can be generalized to a non-commutative skew-field as well i.e. If the finite projective plane $PG(2,3)$ exists in $PG(2,k)$ for some skew-field $k$, then $1+1+1=0$ in $k$. This was proved by Jeffrey Lanyon in his M.Sc thesis [3].

References
[1] G. Gordon, J. McNulty, Matroids a Geometric Introduction, Cambridge University Press, 2012 16.
[2] L. Kadison and M. Kromann, Projective Geometry and Modern Algebra, Birkhäuser 1996.
[3] J. Lanyon, Group Realizations of Configurations, Masters Thesis, University of Manitoba, 2018.
[4] J.H van Lint, R.M. Wilson, A Course in Combinatorics, Cambridge University Press, 1994 page 316.

19 October 2018, 3:30 pm, 415 Machray Hall

Speaker: Jane Breen
Title: Kemeny's constant and random walks on graphs

Abstract: This talk will provide an overview of Kemeny's constant and the role it plays in finite Markov chain theory. Interpreted as either the expected time to reach a randomly-chosen target state, or in terms of the expected time to mixing, it is a useful measure of how well-connected the states of a Markov chain are. By considering the random walk on a simple, undirected graph, we can also use Kemeny's constant as an interesting graph measure that describes how well-connected the graph is. I will describe some methods of calculating Kemeny's constant, as well as some known results and applications.

2 November 2018, 3:30 pm, 418 Machray Hall

Speaker: Sam Cole
Title: Planted problems in random graphs

Abstract: In general, finding the largest clique in an Erdős-Rényi random graph is conjectured to be a hard problem. But what if we take an E-R random graph and deterministically "plant" a very large clique in in? Can an algorithm determine exactly which vertices were part of the "plant" w.h.p.? This is known as the planted clique problem. In this talk, I will give a survey of the planted clique problem and the related planted partition problem, focusing on spectral algorithms, and present some of my results. These problems are of interest in computer science as they serve as a theoretical model for community detection.

9 November 2018, 3:30 pm, 418 Machray Hall

Speaker: Shahin Kamali
Title: A review of telephone broadcast problem

Abstract: In the telephone broadcast problem, the input is an undirected graph G=(V,E) and a source vertex r in V. The goal is to broadcast a message from r to all other vertices. Communication takes place in synchronous round. In each round, a vertex which has the message can send the message to at most one of its neighbors (this resembles a telephone call). The objective is to minimize the number of rounds at which the broadcast completes, that is, when all vertices receive the message.

This problem has been studied extensively by both Math and Computer Science communities. In this talk, I survey the telephone broadcast problem, from the initial results with respect to hardness and relationship with graph parameters to more recent results with respect to approximation algorithms. A few open questions and conjectures will be reviewed.

30 November 2018, 3:30 pm, 418 Machray Hall

Speaker: Avery Miller
Title: Labeling graphs for broadcast in radio networks

Abstract: Performing tasks in radio networks can be difficult due to signal interference that can occur due to simultaneous transmissions, made worse by the fact that nodes in a network behave without knowledge of the network topology. By modeling the network as a graph and assuming that each node has been assigned a unique integer label, a lot of progress has been made in designing algorithms for important tasks. This is because the labels can be used to coordinate the behaviour of the nodes, in particular, to break symmetries that might exist in the underlying graph. The question is: do we really need the labels to be distinct? Given a graph G, what is the fewest number of different labels we can assign to the nodes of G such that a given task is still algorithmically solvable? In this talk, I'll consider this question for the Broadcast task in radio networks. No prior knowledge about these topics will be assumed.

Winter 2018 Schedule

Abstracts

12 January 2018, 3:30 pm, 415 Machray Hall

Speaker: Michal Przykucki
Title: Parking on a random tree

Abstract: Consider the following problem, introduced in 1966 as a model of a simple protocol to resolve collisions in hashing functions. Let T be a rooted tree on n vertices (e.g., a directed path) with edges directed towards the root. We imagine that each node of T has space for a single car to park. A number m of cars arrive one by one, each at a node chosen independently and uniformly at random. If a car arrives at a space which is already occupied, it follows the unique path oriented towards the root until it encounters an empty space, in which case it parks there; if there is no empty space, it leaves T and the protocol fails.

We discuss some new results in the case when T is random. Joint work with Christina Goldschmidt.

26 January 2018, 3:30 pm, 415 Machray Hall

Speaker: Michael Doob
Title: Seeing the rank of a matrix

Abstract: Matroids have several equivalent definitions. One involves the definition of independent sets and while another uses the structure of cycles. It is this duality that allows some algebraic properties of graphs to be viewed geometrically. We'll see how this works. As an example, we'll look at the "geometry" of the rank of the incidence matrix of a graph.

2 February 2018, 3:30 pm, 415 Machray Hall

Speaker: William Kocay
Title:The Configurations (13_3)

Abstract: Grunbaum has conjectured that every configuration (n_3) that can be drawn in the plane with straight lines can be drawn with rational coordinates. There are 2036 configurations (13_3). We show how to coordinatize all of them with rationals. Elliptic curves make an appearance.

9 February 2018, 3:30 pm, 415 Machray Hall

Speaker: Bob Quackenbush
Title: Rectangular powers and Ramsey theory

Abstract: For a finite structure $A$ (e.g., a graph, poset, group, or lattice), let its set of finite powers be $Pow(A) = \{A^n | n \geq 0\}$ with $P_{m,n}(A)$ the set of all substructures of $A^n$ isomorphic to $A^m$.

Choose positive integers $n, m, k, c$ with $n > m > k$. Then we call an onto map $\Delta: P_{k,n}(A) \to [c] = \{1,...,c\}$ a $c$-colouring. We seek $B \in P_{m,n}(A)$ such that the restriction of $\Delta$ to $\{C \in P_{k,m}(A) | C \subseteq B \}$ is constant; such a $B$ is said to be monochromatic with respect to $\Delta$.

I will discuss the positive and negative results of this quest, couched in the language of rectangular powers and polymorphism clones.

See abstract: here

16 February 2018, 3:30 pm, 415 Machray Hall

Speaker: Amy Shaw
Title: Fast percolation

Abstract: Given a graph $G$ and a positive integer $r$, the $r$-neighbor bootstrap percolation process on $G$ is defined in the following way: A subset $A \subset V(G)$ of vertices is initially infected, and any vertex outside $A$ is healthy. We then successively infect each healthy vertex that has at least $r$ infected neighbours. If every vertex is eventually infected, say that $A$ percolates.

Bootstrap percolation has been the subject of much study in both the probabilistic and deterministic models, in particular on the grid $[n]^2$. The maximum time to percolation in $[n]^2$ has been determined precisely and in this talk, I will present some new results on how quickly a 'small' initial configuration can percolate.

This talk is based on joint work with Stefan David.

9 March 2018, 3:30 pm, 415 Machray Hall

Speaker: Shonda Gosselin (UW)
Title: Metric Dimension of Circulant Graphs and Cayley Hypergraphs

Abstract: A pair of vertices $x$ and $y$ in a graph (or hypergraph) $G$ are said to be resolved by a vertex $w$ if the distance from $x$ to $w$ is not equal to the distance from $y$ to $w$. We say that $G$ is resolved by a subset of its vertices $W$ if every pair of vertices in $G$ is resolved by some vertex in $W$. The minimum cardinality of a resolving set for $G$ is called the \emph{metric dimension} of $G$. The problem of determining the metric dimension of a graph is known to be NP-hard (Khuller et al 1994). The metric dimension of a graph has applications in network discovery and verification, combinatorial optimization, chemistry, and many other areas, and consequently this graph parameter has received a great deal of attention from researchers, the main goal being to determine the metric dimension of certain classes of graphs or to achieve asymptotic bounds. In particular, there is great interest in finding classes of graphs whose metric dimension does not grow with the number of vertices. Such graphs are said to have bounded metric dimension. In this talk, we bound the metric dimension of Cayley hypergraphs on finite Abelian groups with the canonical set of generators, and we show that the metric dimension of these hypergraphs is equal to the metric dimension of a Cartesian product of a circulant graphs of the form $C_n(1,2,\ldots,t)=Cay(\mathbb Z_n:\{\pm 1,\pm 2,\ldots,\pm t\})$. These circulant graphs have bounded metric dimension (Grigorious et al 2014). In fact, their metric dimension is determined by the congruence class of $n$ modulo $2t$. We present some background on the problem and some new results. We also bound the metric dimension of Cartesian products of these circulants, which yields bounds on the metric dimension of the corresponding Cayley hypergraphs. This is joint work with my students Adam Borchert and Kevin Chau.

16 March 2018, 3:30 pm, 415 Machray Hall

Speaker: Amy Shaw
Title: Orienting wide partitions

Abstract: Latin squares are square arrays filled with symbols so that every symbol appears exactly once in each row and column. For example, Cayley tables and sudoku solutions are Latin squares. While it is simple to construct a Latin square with $n$ symbols on a square array of size $n$, construction of Latin squares can become difficult when further constraints are imposed. Dinitz's conjecture, which was confirmed by Galvin, relates to the existence of Latin squares when different cells have different sets of available symbols, Rota's basis conjecture pertains to the problem when the symbols are vectors and rows/columns must be linearly independent, and the wide partition conjecture addresses the problem for shapes other than square arrays. I will discuss these problems and conjectures and my recent results on the wide partition conjecture. Based on joint work with Ping Kittipassorn.

Fall 2017 Schedule

Abstracts

15 September 2017, 3:30 pm, 418 Machray Hall

Speaker: David Gunderson
Title: Some of my favourite problems in combinatorial geometry

Abstract: The purpose of this talk is to popularize some problems or theorems from combinatorial geometry. For example, I will look at the Heilbronn problem, Monsky's theorem, Minkowski's theorem, and some recent results in Euclidean Ramsey theory. Here are a few motivating questions:

1. Place 5 points in a unit square, no three of which are collinear, and look at the 10 triangles thereby determined. How can these 5 points be placed so that the minimum area of any triangle is maximized?
2. Can a square be partitioned into 5 triangles of equal area? Does number theory hold the answer?
3. Can results in convex geometry be used to obtain number-theoretic results?
4. If points in a Euclidean space are coloured either red or blue, what patterns in one colour can be guaranteed?

22 September 2017, 3:30 pm, 418 Machray Hall

Speaker: Sergei Tsaturian
Title: Survey of Euclidean Ramsey Theory

Abstract:

29 September 2017, 3:30 pm, 418 Machray Hall

Speaker: Karen Gunderson
Title: Sets with no 3-term arithmetic progressions

Abstract: This is a survey talk in the area of additive combinatorics on the maximum size of sets in $\mathbb{Z}_n$ or $\mathbb{Z}_p^n$ with no arithmetic progressions. I will survey results in the area and sketch the proofs of some of the bounds on the sizes of these sets, including the bounds obtained by Fourier analysis and recent bounds using a polynomial method. This talk is for a general audience.

27 October 2017, 3:30 pm, 418 Machray Hall

Speaker: Ranganathan Padmanabhan
Title: Elliptic Curves in Combinatorics

Abstract: The adjective 'elliptic' in the above title comes from the so-called elliptic functions which arise from the problem of finding the arc length of an ellipse. Thus the origin of elliptic curves lies in complex analysis. However, the topic has penetrated many fundamental areas of mathematics including algebra, number theory, geometry, cryptography, combinatorics and even physics. In this talk, I will go through some typical examples and sketch the proofs illustrating the applications of elliptic curves in finite geometries and combinatorics. This talk is for a general audience.

References

1. Mendelsohn, N. S.; Padmanabhan, R.; Wolk, B. Block configurations on real cubic curves. J. Combin. Theory Ser. A 58 (1991), no. 1, 131-135
2. Mendelsohn, N. S.; Padmanabhan, R.; Wolk, B. Designs embeddable in a plane cubic curve. Note de Mat. (Italy) 7 (1987), no. 1, 113-148.

3 November 2017, 3:30 pm, 418 Machray Hall

Speaker: Avery Miller
Title: Treasure Hunting in Graphs Without a Map

Abstract: A mobile agent starts somewhere in an arbitrary graph, and traverses edges until it finds the single node in the graph that contains a treasure. The difficulty is, the agent doesn’t have a map of the graph. A further difficulty is that the nodes of the graph are not labeled, and the agent cannot leave marks or breadcrumbs to remember where it has been. At each time step, the agent is located at a node v, can only see the edges incident to this node, and these edges are labeled 0,…,deg(v)-1. In this talk, I will present some results that describe the relationship between: (i) how much information the agent knows about the graph, a priori, and (ii) the number of traversals used by the agent to find the treasure. On the one hand, we will look at a search strategy that works with limited information, and on the other hand, we will look at impossibility results of the form "if the agent must find the treasure within T steps, you must give the agent at least f(T) bits of information about the graph, no matter which strategy it uses".

10 November 2017, 3:30 pm, 418 Machray Hall

Speaker: Amy Shaw
Title: Catching a fast robber

Abstract: The game of Cops and Robbers is played on a graph by a set of cops and one robber. The game begins with the cops being placed onto vertices of their choice in $G$ and then the robber, being fully aware of the placement of the cops, positions himself on a vertex of his choosing. They then take turns moving along the edges of the graph, starting with the cops. During their turn, each cop may move to an adjacent vertex, or remain stationary, and the same goes for the robber. We also allow multiple cops to occupy the same vertex. The cops win if at some time there is a cop at the same vertex as the robber; otherwise, the robber wins. The minimum number of cops for which the cops have a winning strategy, no matter how the robber plays, is called the cop number of $G$. Our focus is on a variant on the $n \times n$ grid in which the robber may move faster than the cops, i.e. the robber may traverse several edges in one turn. We provide upper and lower bounds on the cop number for this version of the game.

24 November 2017, 3:30 pm, 418 Machray Hall

Speaker: Anthony Bonato (Ryerson)
Title: Burning spiders and path forests

Abstract: Graph burning is a simplified model for the spread of memes and contagion in social networks. A fire breaks out in each time-step and spreads to its neighbours. The burning number of a graph measures the number of time-steps it takes so that all vertices are burning. While it is conjectured that the burning number of a connected graph of order n is a most the ceiling of the square root of n, this remains open in general.

1 December 2017, 3:30 pm, 418 Machray Hall

Speaker: Shahin Kamali
Title: $k$-server problems: a review of the old results and recent developments

Abstract: k-server problem is a classic problem in the context of competitive analysis. Given an undirected graph and a sequence of requests to vertices of the graph, the goal is to move k servers in way that at least one server is present at each request and the total distance moved by servers is minimized. At the heart of the k-server problem lies the k-server conjecture, which states that there is a deterministic algorithm with competitive ratio of exactly k. In the first half of this talk, we review the existing results with respect to the k-server conjecture. This will include a lower bound for competitive ratio of deterministic algorithms, particular case of trees, and also the work-function algorithm which is conjectured to answer the k-server conjecture in the affirmative. In the past few years, there has been efforts to study k-server problem using alternative settings. One of them is advice model where the online constraint is relaxed and an online algorithm receives partial information about the input sequence. In the second part of the talk, we review the existing results on the advice complexity of the k-server problem. We conclude with discussing a few open problems.

8 December 2017, 3:30 pm, 418 Machray Hall

Speaker: Andrii Arman
Title: The crossing number of a graph

Abstract: A graph $G$ is called "planar" if $G$ can be drawn in the plane so that no edges cross. It is known that the graphs $K_5$ and $K_{3,3}$ are not planar. For a graph $H$ that is not planar, one can measure the "non-planarity" by counting its "crossing number", the minimum number of edge crossings required in any drawing of $H$ in the plane.

This talk surveys some facts about crossing numbers and their variants, some basic inequalities, and applications.

Winter 2017 Schedule

Abstracts

20 January 2017, 3:45 pm, 111 Armes

Speaker: Avery Miller (CS)
Title: Cover-Free Families of Sets with Applications

Abstract: A k-cover-free family of sets has the property that no set in the family is contained in the union of k of the other sets. These families can be used to solve certain puzzles that involve quickly finding a 'defect' in a large collection, such as finding a counterfeit coin using a scale, a diseased soldier using blood tests, or a poisoned bottle of wine using rats. These puzzles all fall under the umbrella of "combinatorial group testing". In this talk, I will give an introduction to cover-free families and the above examples, and then discuss a very different application: solving communication tasks in wireless networks. On the one hand, we can get efficient algorithms by using cover-free families when specifying radio transmission schedules, and on the other hand, we can prove lower bounds for certain tasks by showing that every algorithm produces a sequence of radio transmissions that corresponds to a cover-free family. If there is time, I will discuss an extension of cover-free families that includes an additional "thickness" parameter: this takes into account how many times a set is covered by the union of k other sets in the family. This extension allows us to solve a more general class of group testing problems, and gives more general results about communication in wireless networks. The talk will be self-contained, e.g., no familiarity with wireless network algorithms will be assumed.

27 January 2017, 3:30 pm, 111 Armes

Speaker: Sergei Tsaturian
Title: Some results in asymmetric Euclidean Ramsey theory

Abstract: A typical question in Euclidean Ramsey theory has the following form: is it true that for any colouring of Euclidean space E^n into two (or more) colours there exists a monochromatic copy of some fixed geometric configuration F? I will focus on the asymmetric version of this question - is it true that for any colouring of E^n in red and blue, there exists either a blue copy of F_1 or a red copy of F_2?

Most of the questions in this field are very easy to state, but even some simplest cases are still open. I will give a brief overview of known results. I will also present our recent result with Andrii Arman, that deals with the case of E^3, F_1 being the configuration of two points at distance 1 to each other, and F_2 being 6 points on a line with distance 1 between consecutive points.

3 February 2017, 3:30 pm, 111 Armes

Speaker: Julien Arino
Title: Some applications of graph theory to math biology

Abstract: Graph theory plays an important role in mathematical biology for a variety of reasons. Graphs, in particular directed graphs, help formalize the interactions between state variables. The structure of interaction graphs further determine the range of behaviours a model exhibits. Graphs also provide a means for describing some spatial processes such as those occurring in the spread of epidemics. I will present several examples illustrating the rich interconnection between graph theory and mathematical biology.

10 February 2017, 3:30 pm, 111 Armes

Speaker: Karen Gunderson
Title: Independence density in graphs and hypergraphs

Abstract: A set of vertices in a graph or hypergraph is said to be independent if it contains no edges. Of interest in this talk are the size, number, and distribution of the independent sets in hypergraphs. Relationships between these and other parameters can provide insight to applications not only from graph theory, but also to additive combinatorics and the hard-core model from statistical physics. In the case of infinite hypergraphs, one can also ask for a measure of the density of independent sets: if each vertex is chosen independently with a fixed probability, what is the probability that the selected set is independent? I will give some history on this topic and present new results on sets of real numbers that are the independence density of some countably infinite hypergraph. This is joint work with P. Balister and B. Bollobás.

17 February 2017, 3:30 pm, 111 Armes

Speaker: Narad Rampersad
Title: Computer Proofs of Results in Combinatorics on Words

Abstract: One of the main topics in combinatorics on words is the avoidability of patterns. An example of a pattern is XX, which denotes two consecutive repetitions of the same sequences of letters: for instance "tartar". Thue (1906) constructed an infinite word using just three symbols that contains no occurrence of XX. He also constructed an infinite word on two symbols that avoids XXX. Around 1979/80 mathematicians began to consider words avoiding patterns on several variables, such as XYZXZY. In most cases, if a pattern can be avoided, the typical way to construct a word avoiding it is by iterating a morphism of the free monoid: e.g., to avoid XXX, iterate the substitution rule 0 → 10, 1 → 10. This generates an infinite set of words avoiding XXX. However, the proof in each case is often an ad hoc argument based on the specific morphism used and the pattern to be avoided. In recent years, a computer algorithm has been developed that automates such proofs: provide the morphism and a description (in first order logic) of the pattern to be avoided, and the computer algorithm will produce a certificate that the words generated by the morphism avoid the pattern. We will give an overview of the method and some recent results proved with it.

17 March 2017, 3:30 pm, 111 Armes

Speaker: Andrii Arman
Title: An upper bound on the size of a $k$-uniform intersecting hypergraph with cover number $k$.

Abstract: A $k$-uniform hypergraph $F$ is called intersecting iff any two hyperedges of $F$ have non-empty intersection. A subset $C$ of vertices of $F$ is a called a cover of $F$ iff every hyperedge of $F$ intersects with $C$. The size of the smallest cover of $F$ is called the cover number of $F$. Define $r(k)$ to be the maximum size (number of hyperedges) of an intersecting $k$-uniform hypergraph $F$ with cover number $k$.

In 1975, Erdős and Lovász proved that $r(k)$ cannot exceed $k^k$. In this talk I will present the proof idea for an upper bound of order $k^{k-1}$ based on a Chooser-Guesser game played on a hypergraph $F$. This talk is based on a joint work with Troy Retter.

31 March 2017, 3:30 pm, 111 Armes

Speaker: Colin Desmarais
Title: A history of partition regularity on the integers

Abstract: What is today called arithmetic Ramsey theory has its origins with Hilbert's cube lemma of 1892, Schur's theorem of 1916, and van der Waerden's theorem of 1927; all of which predate Ramsey's publication of his now famous theorem in 1930. These results guarantee a monochromatic solution to a particular system of equations in any finite colouring of the positive integers: for example, Schur's theorem states that every finite colouring of the positive integers has a monochromatic solution to $x+y=z$. Such an equation or system of equations is called partition regular.

In this talk I will give an overview of early results in arithmetic Ramsey theory, including Rado's 1933 characterization of partition regular systems. I will also discuss Deuber's proof in 1973 of a conjecture of Rado's that in any finite colouring of the positive integers some colour class contains solutions to every partition regular system. Finally, I will briefly state results in infinite and nonlinear partition regular systems.

7 April 2017, 3:30 pm, 111 Armes

Speaker: Rob Craigen
Title: The double core and duality: where generalized Hadamard matrices, generalized weighing matrices and projective planes meet.

21 April 2017, 3:30 pm, 111 Armes

Speaker: Ortrud Oellermann
Title: On Mean Subtree Orders of Trees

Abstract: The study of the mean subtree order of a given tree was initiated in a 1983 paper of Jamison. While the structure of trees of a given order with minimum mean subtree order have been characterized, the problem of describing trees of a given order with maximum mean subtree order is still largely open. This talk begins with an overview of known results followed by recent results on trees of maximum subtree order within certain classes of trees. (New results are joint work with Lucas Mol.)

Fall 2016 Schedule

Abstracts

9 September 2016, 3:30 pm, 111 Armes

Speaker: Rob Craigen
Title: Algebraic design theory - Part 2

Abstract: Part 2 of talk from 8 April 2016.

Warwick de Launey pondered a series of ideas about how to create a basic framework for designs that would capture the entirety of the field using higher analytic tools more than case-by-case analysis, placing the entire field onto some common framework. He decided that the fundamental concept making the field what it is was a sort of "orthogonality" based on the pairwise relationship between two rows in an array of symbols. In the last 5 years of his life he developed these rudimentary ideas, with coauthor Dane Flannery, into an overarching theory in which algebra plays the part of an "engine" driving the various objects that arise in the theory and setting out pathways along which a panoply of other, even as-yet undiscovered, objects may be explored.

de Launey passed away to cancer in 2010 just as their book was still being completed. A couple of years later I had the privilege of writing its Math Review. Later, in 2014 I visited for 3 months with Flannery to discuss the development of ideas in the book, open questions that arise, and what future directions suggest themselves based on its framework.

In this talk I will survey the basic elements of the setup of Algebraic Design Theory, its key theorems and what, to me, are some of the more obvious deficiencies (and merits) of this approach. We will see some open questions.

23 September 2016, 3:30 pm, 111 Armes

Speaker: Michael Szestopalow
Title: Matchings and Covers in Hypergraphs

Abstract: A matching of a hypergraph H is a set of pairwise disjoint edges of H and a cover of H is a set of vertices that meets every edge of H. The well-known Konig-Egervary Theorem says that in a bipartite graph, the size of a maximum matching is equal to the size of a minimum cover. We will consider similar results for hypergraphs. In particular, we will discuss problems and results related to conjectures of Ryser and Tuza.

30 September 2016, 3:30 pm, 111 Armes

Speaker: Karen Gunderson
Title: Percolation and infinite trees

Abstract: A bootstrap process is a type of cellular automaton, acting on the vertices of a graph which are in one of two states: `healthy' or 'infected'. For any positive integer r, the r-neighbour bootstrap process is the following update rule for the states of vertices: infected vertices remain infected forever and each healthy vertex with at least r infected neighbours becomes itself infected. These updates occur simultaneously and are repeated at discrete time intervals. Percolation is said to occur if all vertices are eventually infected.

Of interest is the random case, where each vertex is infected independently with a fixed probability p. For an infinite graph, one would like to know the values of p for which the probability of percolation is positive. I will give some of the history of this problem for infinite trees and present some new results on the possible values of critical probabilities for such processes on Galton-Watson trees.

This talk is based on joint work with Bollobás, Holmgren, Janson, and Przykucki.

14 October 2016, 3:30 pm, 111 Armes

Speaker: David Gunderson
Title: A result in finite projective planes used for dimension theory of posets

Abstract: A few weeks ago, at the 6th PCC in Poland, I attended a talk by Tom Trotter about posets. He mentioned a paper by Biró, Hamburger, Pór, and himself, where finite projective planes (FPPs) were used to produce a certain family of posets, thereby proving something about dimension of posets. Csaba Biró was at the conference, and it turned out that we shared a taxi to the airport. So I asked him about how FPPs fit into their work. He gladly gave me a minilecture. One result really caught my eye, and so I want to share it:

Theorem [BHPT, 2016]: Let Π be a FPP of order q, let X be a set of points in Π, and let Y be a set of lines in Π, each containing no point of X. Then |X| ⋅ |Y| ≤ q³.

I will give (or at least outline) two similar proofs of the above theorem, one of which was sent to me by Csaba just a few days ago. Both proofs use double counting (or some call it quadratic counting), and is very similar to the 1975 Bruen-Silverman proof for blocking sets.

If time allows, I hope to also give some idea as to how the above theorem translates into one about "standard examples" in posets and dimension theory. Instead of using incidences in FPPs (as is often the case in graph theory), their poset uses "anti-incidence".

21 October 2016, 3:30 pm, 111 Armes

Speaker: Ranganathan Padmanabhan
Title: Term Spectra and their Minimal Extensions

Abstract: For an algebra A, let p_n(A) denote the number of essentially n-ary term functions - that is those n-ary operations which are derived or generated from the basic operations of the algebra and which depend on all n variables. The p_n-sequence of A is the integer sequence

One can easily determine the free spectrum of the algebra from the sequence p(A) by a well-known combinatorial formula. In this talk, we give typical examples of the term spectra, their minimal extensions and the free spectra of certain equational classes which one often comes across in algebras and finite geometries.

References

1. G. Grätzer and R. Padmanabhan, On idempotent, commutative and non-associative groupoids. Proc. Amer. Math. Soc 28 (1971) 75-80.
2. G. Grätzer and A. Kisielewicz, A survey of some open problems on pn-sequences and the free spectra of algebras and varieties, Universal algebra and quasigroup theory, Haldermann Verlag, Berlin 1992, 57-88.
3. J. Dudek, Affine spaces over GF(3), Studia Logica 72 (2002), 363-366.
4. R. Padmanabhan, Free spectrum of shelf algebras, Rings and Modules Seminar, University of Manitoba, 06 October, 2015 (unpublished).

4 November 2016, 3:30 pm, 3M63 at the University of Winnipeg (not the usual location!)

Speaker: Asha Rao
Title: Low-density Parity-check codes

Abstract: Low-density parity-check codes were first discovered by Robert Gallager in 1962, and then left unnoticed for the next 30 years, until they were re-discovered in the 1990s by McKay and Neal. The main attraction of these codes is their ability to achieve rates close to the Shannon limit. The codes originally designed by Gallagher were pseudorandom and good LDPC codes were found mainly by computer searches. I will describe these codes and why there are of interest, and then give some insight into some, more recently discovered ways of constructing these codes from combinatorial structures.

25 November 2016, 3:30 pm, 111 Armes

Speaker: Andrii Arman and Sergei Tsaturian
Title: Maximum number of cycles in a graph

Abstract: A problem of bounding the number of cycles in a graph is more than a century old. In 1897, Ahrens gave bounds on the number of cycles using the cyclomatic number. Since then, there have been many results about maximum number of cycles for a graph with fixed number vertices, fixed cyclomatic number, and other restrictions.

In this talk we consider a question of determining the maximum number of cycles over two different classes of graphs: graphs with fixed average degree and graphs with fixed number of edges. Results of our recent joint work show that for both cases maximum number of cycles in a graph has bounds exponential in the number of edges of a graph. We will also present the solution of similar problems for multigraphs.

2 December 2016, 3:30 pm, 111 Armes

Speaker: Bob Quackenbush
Title: Ramsey Clones

Abstract: This is an introductory talk about Ramsey theory centered around the concept of a parameter set. It will be phrased in the language of universal algebra and, in particular, the concept of a clone of functions (a set of functions closed under composition of functions).

Winter 2016 Schedule

Abstracts

29 January 2016, 3:30 pm, 115 Armes

Speaker: Ranganathan Padmanabhan
Title: Sylvester-Gallai Configurations

Abstract: A finite set S of points in an affine or a projective plane over a field k is called a Sylvester-Gallai configuration if any line joining a pair of points of S contains at least three points of S. A finite set of collinear points in a plane is SG, called the trivial configuration.The now famous Sylvester-Gallai theorem states that the any SG-configuration in projective or affine plane over the field of all real numbers is trivial. A powerful consequence of this result is that any attempt to draw a non-trivial SG-configuration in the real plane, there must be at least one straight line which is not straight. Most well-known example of this kind is the familiar 7-point Fano configuration where one always gets at least one circle. By way of contrast, there are algebraically closed fields which admit non-trivial SG-configurations. Also, every finite field admits nontrivial SG-configurations (an example given below). In this talk, we will go through some of the proofs and non-trivial examples and also mention some new directions of research being done in this area.
Further details on the talk

12 February 2016, 3:30 pm, 115 Armes

Speaker: Sergei Tsaturian
Title: Triangle-free graphs with the maximum number of cycles

Abstract: One of the central questions in extremal graph theory is determining maximal possible number of edges in a graph with given number of vertices that doesn't contain a specific subgraph. Examples of such statements are famous Mantel's and Turan's theorems.
More general questions can be considered - determining how many copies of some fixed subgraphs (or collections of subgraphs) can be there in a graph that satisfies some conditions. I will talk about some results of that kind.
In particular, I will show the result of our recent work with A.Arman and D.Gunderson about maximal number of cycles in a graph that doesn't contain triangles, and discuss possible generalizations and open questions.

26 February 2016, 3:30 pm, 115 Armes

Speaker: Stephane Durocher
Title: The locality of route-finding in a graph

Abstract: We examine theoretical bounds on the locality of finding a path between two given nodes in a graph. A local forwarding algorithm A at a vertex v receives a message P and selects one of its neighbours to which to forward P using only local information. Specifically, in addition to knowing the node for which P is destined, algorithm A may also know the node from which P originated, the neighbour from which node v received P, and the subgraph corresponding to all nodes within distance k of node v. Our objective is to determine which of these parameters are necessary and/or sufficient to permit successful message delivery as k varies. We establish tight bounds on k for the feasibility of deterministic k-local path finding for various combinations of these parameters. Although motivated by applications in networks, this work consists of combinatorial and graph-theoretic arguments. This is joint work with Prosenjit Bose and Paz Carmi.

11 March 2016, 3:30 pm, 115 Armes

Speaker: Rob Craigen
Title: Survey of negacyclic weighing matrices

Abstract: A square or rectangular matrix is circulant if every row after the first is a right circular shift of its predecessor. Negacyclic matrices are defined the same way except that the first entry of each row is negated after circulating the preceding row. A partial Hadamard matrix is a rectangular kxn (1,-1)-matrix M satisfying MM^T = nI. In the summer of 2013 I hired four sharp undergraduate students to tackle a problem about circulant partial Hadamard matrices. The question of existence of certain negacyclic weighing matrices kept coming up, so we devoted some energy to exploring this largely uncultivated territory. In the end we produced, apparently for the first time, a fairly comprehensive survey of these objects, their structure, why certain classes exist and others cannot. The flavour of the existence questions for this class of weighing matrices is decidedly different from that of group-developed form, even though much of the theory is the same. We discuss some situations in which negacyclic weighing matrices naturally appear, and conclude with some tantalizing new open questions arising from the work.

1 April 2016, 3:30 pm, 115 Armes

Speaker: Steve Kirkland
Title: Kemeny's Constant and an Analogue of Braess' Paradox for Markov chains

Abstract: A square matrix that is entrywise nonnegative and has all row sums equal to 1 is called a stochastic matrix, and such matrices play a central role in the study of Markov chains. Given a stochastic matrix A, Kemeny's constant K(A) measures the expected number of steps required for the Markov chain to transition from a given initial state to a randomly chosen final state.

In this talk, we will begin by giving an introduction to Kemeny's constant. We will then go on to explore an analogue of Braess' paradox (wherein adding a road to a network can have the counter-intuitive effect of increasing travel times). Specifically, we will discuss how adding an edge into an undirected graph can increase the value of Kemeny's constant for a certain Markov chain that is naturally associated with the graph.

8 April 2016, 3:30 pm, 115 Armes

Speaker: Rob Craigen
Title: Algebraic design theory

Abstract: Warwick de Launey pondered a series of ideas about how to create a basic framework for designs that would capture the entirety of the field using higher analytic tools more than case-by-case analysis, placing the entire field onto some common framework. He decided that the fundamental concept making the field what it is was a sort of "orthogonality" based on the pairwise relationship between two rows in an array of symbols. In the last 5 years of his life he developed these rudimentary ideas, with coauthor Dane Flannery, into an overarching theory in which algebra plays the part of an "engine" driving the various objects that arise in the theory and setting out pathways along which a panoply of other, even as-yet undiscovered, objects may be explored. de Launey passed away to cancer in 2010 just as their book was still being completed. A couple of years later I had the privilege of writing its Math Review. Later, in 2014 I visited for 3 months with Flannery to discuss the development of ideas in the book, open questions that arise, and what future directions suggest themselves based on its framework. In this talk I will survey the basic elements of the setup of Algebraic Design Theory, its key theorems and what, to me, are some of the more obvious deficiencies (and merits) of this approach. We will see some open questions.

Fall 2015 Schedule

11 September 2015, 3:30 pm, 115 Armes

Speaker: Karen Gunderson
Title: Saturation and graph processes

Abstract: Saturation is a type of extremal problem for graphs and hypergraphs that was introduced by Erdős, Hajnal, and Moon in 1964. A graph G is said to be F-saturated if G contains no copies of F and the addition of any further edge to G creates a copy of F. A more general notion, introduced by Bollobás in 1968 is a weakly F-saturated graph, which is a graph G for which there is an ordering of the non-edges of G so that adding the non-edges one by one to the graph creates a new copy of F at each step. The central question is, for a given graph F and natural number n, what is the fewest number of edges in either an F-saturated or weakly F-saturated graph on n vertices? I will give some of the history of these problems and sketch the proofs of some of the central tools that answer these questions for complete graphs. Finally, I will discuss the edge-adding graph process arising from weak saturation and some of my recent work on this in an Erdős-Rényi random graph.

18 September 2015, 3:30 pm, 115 Armes

Speaker: Andrii Arman (Manitoba)
Title: Fibonacci-sum graphs

Abstract: For each positive integer n, the Fibonacci-sum graph G_n is the graph with vertex set V(G_n)= {1,2,..., n} and edge set consisting of those pairs that sum to a Fibonacci number. Properties of G_n were investigated in 2014, when K. Fox, Kinnersley, McDonald, Orlow, and Puleo characterized those n for which G_n has a Hamiltonian path and described all such paths. In this talk I will show other properties of G_n, namely that G_n is connected, bipartite, planar and that the automorphism group of G_n is of order at most 2. This is joint work with Gunderson and Li.

25 September 2015, 3:30 pm, 115 Armes

Speaker: Ben Li (Manitoba)
Title: Minimum total vertex covers and algorithms for computing them

Abstract: Let G=(V,E) be a simple, undirected, connected graph with at least two vertices. A total vertex cover (TVC) of G is a vertex cover C of G with the additional property that each connected component of the subgraph of G induced by C contains at least two vertices. The total vertex cover problem is to find a total vertex cover of G of minimum size.
I will show that this problem is NP-Hard, talk briefly about parameterized algorithms for this problem and give an efficient algorithm for finding a minimum-cardinality total vertex cover in a tree. I will conclude with some open problems that I am currently working on.

2 October 2015, 3:30 pm, 115 Armes

Speaker: Rob Craigen (Manitoba)
Title: Matrices equivalent to their transpose by permutation

Abstract: We consider the following question: what can be said about matrices M such that PMQ = M^t, where P and Q are permutation matrices (that is, matrices permutation equivalent to their transpose)? In particular, is M permutation equivalent to a symmetric matrix (clearly the converse is true)? These questions arise in combinatorial matrix theory. We show that the answer to the latter question is ''no'', and that if it does not hold for M, then M is permuation equivalent to a matrix which may be nontrivially decomposed into circulant submatrices.

9 October 2015, 3:30 pm, 115 Armes

Speaker: Stephane Durocher (Manitoba)
Title: Local Geometric Routing in Convex Subdivisions

Abstract: In various wireless networking settings, node locations and proximity to neighbouring nodes determine a network's topology, allowing the network to be modelled by a geometric graph drawn in the plane. Without any additional information, local geometric routing algorithms can guarantee delivery to the target node only in restricted classes of geometric graphs, such as triangulations. In order to guarantee delivery on more general classes of geometric graphs (e.g., convex subdivisions or planar subdivisions), previous local geometric routing algorithms required O(log n) state bits to be stored and passed with the message. We present the first local geometric routing algorithm using only one state bit to guarantee delivery on convex subdivisions and the first local geometric memoryless routing algorithm that guarantees delivery on edge-augmented monotone subdivisions (including all convex subdivisions) when the algorithm has knowledge of the incoming port (the preceding node on the route).

16 October 2015, 3:30 pm, 115 Armes

Speaker: David S. Gunderson (Manitoba)
Title: Ramsey arrows for induced graphs

Abstract: A simple form of Ramsey's theorem says that for any positive integer m, there exists an n = R(m) so that no matter how the pairs of an n-set are partitioned into two colours, some m-subset has all its pairs the same colour. In terms of graphs, this says if the edges of a K_n are 2-coloured, a monochromatic copy of K_m (as a subgraph) can always be found. An edge can also be thought of as the graph K₂. Such a statement is often expressed in “Ramsey arrow” notation. There have been many generalizations of Ramsey questions for numbers and for graphs. In this survey, the focus is on some of the special situations where induced subgraphs are used instead of just subgraphs.

23 October 2015, 3:30 pm, 115 Armes

Speaker: Bill Kocay (Manitoba)
Title: Constructing Graphs with a High Reconstruction Number

Abstract: Ulam's conjecture, also known as the Graph Reconstruction Conjecture, states that the structure of a graph is determined by its subgraphs. A method will be described for constructing a pair of graphs G, H on 2n vertices such that G and H have n vertex-deleted subgraphs in common. The method uses Paley groups from finite field theory.

30 October 2015, 3:30 pm, 115 Armes

Speaker: Vaclav Linek (Winnipeg)
Title: Polyhedral Designs

Abstract: Take 40 identical pieces of paper, each shaped as an equilateral triangle, one side white and one side black. For each 3-subset {x,y,z} of {1,2,3,4,5,6} take a triangle and write x, y, z at the corners on the white side. Then take another triangle and write x, z, y at the corners on the white side, i.e., this time write the numbers in the opposite orientation. Can you assemble these 40 triangles into 5 octahedrons so that the white sides face outward and at each corner all the labels agree?
Five such octahedra make an oriented OCT(6) design, an oriented OCT(v) design being defined similarly. An unoriented OCT(v) design is made from triangles that are white on both sides and labelled on both sides. Hanani (1978) settled the existence of unoriented octahedral designs. We show that an oriented OCT(v) design exists iff v = 1,2,6 (mod 8), and we solve the subsystem problem for octahedral designs. We will also give the existence result for cube designs, and shall say what is known about designs based on the other Platonic solids as well as the deltahedra.
This is joint work with Brett Stevens and Leonard Soicher.

6 November 2015, 3:30 pm, 115 Armes

Speaker: Ortrud Oellermann (Winnipeg)
Title: Progress on the Oberly-Sumner Conjecture

Abstract: For a given graph property P we say a graph G is locally P if the open neighbourhood of every vertex induces a graph that has property P. Oberly and Sumner (1979) conjectured that every connected, locally k-connected, K_{1,k+2}-free graph of order at least 3 is hamiltonian. They proved their conjecture for k=1, but it has not been settled for any k at least 2. 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. We make progress toward proving the Oberly-Sumner conjecture by showing that every connected, locally k-P_3-connected, K_{1,k+2}-free graph of order at least 3 is hamiltonian and, in fact, fully cycle extendable. (This is joint work with S. van Aardt, M. Frick, J. Dunbar and J.P. de Wet.)

13 November 2015, 3:30 pm, 115 Armes

Speaker: Colin Desmarais (Manitoba)
Title: Norm-graphs and their applications

Abstract: For finite fields K of order q and F of order q^m, so that F extends K, the Field Norm of an element α ∈ F is defined as N(α) = (α)^{1 + q + ... + q^{m-1}}. I will discuss some basic properties of this norm, and demonstrate constructions of so called "Norm-Graphs". The extremal number ex(n;F) is the largest number of edges in a graph G on n vertices that does not contain F as a weak subgraph. I will demonstrate how the Norm-Graphs are used to improve on the lower bound for ex(n;K_3,3), and more generally on the lower bound for ex(n; K_{s, (s-1)!+1}). Next, I will provide generalizations of these constructions that improve on the lower bounds for hypergraph extremal problems. Finally, I will discuss the impact of Norm-graphs on a graph-Ramsey problem.

20 November 2015, 3:30 pm, 115 Armes

Speaker: Sergei Tsaturian (Manitoba)
Title: Counting certain subgraphs in a graph and its complement

Abstract: For a graph G on n vertices, what is the minimal number of triangles in G or its complement? In 1959, A.W. Goodman proved that this number is at least roughly n³/24. The more general question can be asked: for a fixed graph H, and a graph G on n vertices, how many copies of H are guaranteed to be in either G or its complement? In my talk, I will show known results on this topic, and some further generalizations.

27 November 2015, 3:30 pm, 115 Armes

Speaker: Bob Quakenbush (Manitoba)
Title: Asymptotic philatelic enumeration or: Counting directly irreducible algebras in finite varieties

Abstract: A finite variety is a class of finite algebras which is closed under homomorphic images, subalgebras, and finite direct products; familiar examples are FBA (finite boolean algebras), FAB (finite abelian groups), FV(q) (finite-dimensional vector spaces over the field of order q), and FL (finite lattices). We are interested in computing the ratio of the number of directly irreducible algebras of size ≤ n to the number of all algebras of size ≤ n; I assume that the finite variety has unique direct factorization. For instance, for FBA, FAB, and FV(q), the ratio goes to 0. For finite varieties of lattices, I will give an easy proof that the ratio goes to 1.

For an arbitrary finite variety A, the ration need not converge. So we consider the limit set of the sequence of ratios for A (consisting of all limit points of convergent subsequences). This is a closed subset of [0, 1]; are there further restrictions? I will present an easy proof that for any a ∈ [0, 1], there is a finite variety A_a whose ratio converges to a. The algebras in A_a will all have cardinality a power of 5; this changes a more difficult multiplicative problem into an easier additive problem and yields a problem in the theory of Asymptotic Philatelic Enumeration (an explanation will be given).

What I don't know is whether there is an A whose ration limit set is {0, 1}.

4 December 2015, 3:30 pm, 115 Armes

Speaker: Jason Semeraro (Bristol)
Title: Hypergraph Turán densities for r-triangles

Abstract: The Turán number ex(H, n) for H is the maximum number of hyperedges in any r-uniform hypergraph on n vertices containing no copy of H. The Turán density of H is defined to be π(H) = lim_{n → ∞} ex(H, n) (n \choose r)^{-1}. π(H) always exists, but is notoriously hard to calculate in general, so we focus on a special case: Define an r-triangle H_r to be an r-hypergraph on r+1 vertices with three r-hyperedges having pairwise intersection of size r-1. By Mantel's Theorem, π(H_2)=1/2, with complete bipartite graphs realizing the extremal case. In general, it is known that π(H_r) <= 1/r. When r=3, Frankl-Füredi showed that π(H_3) >= 2/7, and various results (using flag algebra techniques) suggest that equality should also hold in this case. Baber has shown that π(H_4)=1/4 using a tournament construction. Motivated by Baber's work, we develop new methods for bounding π(H_r) (r > 3) using switching classes of tournaments. These methods have their origins in group theory via the action of PGL(2,q) on the extended Paley tournament. So far, we have been able to produce an infinite family of extremal examples in the case r=4 (simultaneously giving a new proof of the fact that π(H_4)=1/4), and to establish a new lower bound in the case r=6: π(H_6)>=9/64.