Organizers: David
Gunderson, Karen Gunderson, JD Nir, and Andrii Arman

Time: Fridays 2:30pm

Zoom link: https://zoom.us/j/98499266029, password is the first six Fibonacci numbers, starting with 11...

Mailing list: https://lists.umanitoba.ca/mailman/listinfo/comb-sem

Topics including graphs and hypergraphs, algebraic graph theory, finite geometries, random processes, extremal or Ramsey theory, applications of combinatorics, combinatorial geometry, partial orders, design theory, combinatorial matrix theory, additive combinatorics.

Talks can be surveys, works in progress, introductions to an area, or recent results. All are welcome to attend and to volunteer talks. Talks should be aimed at a wide audience of combinatorialists and should be understandable to graduate students.

Subscription to the calendar is available via:

https://www.google.com/calendar/ical/4aq25ijhgs0tb19k9cni79ucps%40group.calendar.google.com/public/basic.ics

Schedules for past seminars are available here.

Date | Speaker | Title |
---|---|---|

24 Sep 2021 | Christopher van Bommel | Fidelity of Quantum State Transfer on Paths with Potentials |

1 Oct 2021 | Shahin Kamali | Algorithms for Burning Graph Families |

8 Oct 2021 | Narad Rampersad | Computer proofs on some combinatorials congruences |

15 Oct 2021 | Hermie Monterde | Continuous-time quantum walks and twin vertices |

22 Oct 2021 | Kyle Murphy | Maximizing five cycles in $K_r$-free subgraphs. |

29 Oct 2021 | Marcelo Tadeu Sales (Emory) | Ramsey and density results for approximate arithmetic progressions |

5 Nov 2021 | Colin Desmarais | TThe size of the root cluster in preferential attachment trees after percolation |

19 Nov 2021 | Neal Bushaw | Rainbow Saturation |

26 Nov 2021 | TBA | |

3 Dec 2021 | Adam Volk | TBA |

10 Dec 2021 | Andriy Prymak | TBA |

**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.

**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.

**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.

**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.

**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.

**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.

**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.

These results are part of a larger work with Cecilia Holmgren and Stephan Wagner.
**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.

**Speaker**:

**Title**:TBA

**Abstract: **
TBA

**Speaker**:Adam Volk (Nebraska at Lincoln)

**Title**:TBA

**Abstract: **
TBA

**Speaker**: Andriy Prymak

**Title**:TBA

**Abstract: **
TBA