Combinatorics Seminar

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.

Extremal C15-free graph

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.


Fall 2021 Schedule

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

Graph with every pair of vertices having
exactly 2 common neighbours

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.

These results are part of a larger work with Cecilia Holmgren and Stephan Wagner.

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.

26 November 2021, 2:30 pm, Zoom

Speaker:
Title:TBA

Abstract: TBA

3 December 2021, 2:30 pm, Zoom

Speaker:Adam Volk (Nebraska at Lincoln)
Title:TBA

Abstract: TBA

10 December 2021, 2:30 pm, Zoom

Speaker: Andriy Prymak
Title:TBA

Abstract: TBA