Fall 2023 talks

Thursday 28 September 2023

Speaker: Raghu Pantangi (URegina)

Title: Random analogues of Erdös-Ko-Rado type results

Time: 11:30 am

• • Room: 115 Armes

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

Thursday 5 October 2023

Speaker: Stephane Durocher (UM CS)

Title: Minimum Ply Covering of Points with Unit Disks

Time: 11:30 am

• • Room: 115 Armes

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

Abstract: Let P be a set of points and let U be a set of unit disks in the Euclidean plane. A minimum ply cover of P with U is a subset of U that covers P and minimizes the number of disks that share a common intersection. The size of a minimum ply cover is called the minimum ply cover number. Biedl et al. [Comput. Geom., 94:101712, 2020] showed that determining the minimum ply cover number for a set of points by a set of unit disks is NP-hard, and asked whether there exists a polynomial-time O(1)-approximation algorithm for this problem. They showed the problem to be 2-approximable in polynomial time for the special case when the minimum ply cover number is constant.  In this paper, we settle the question posed by Biedl et al. by providing a polynomial-time O(1)-approximation algorithm for the minimum ply cover problem. This is joint work with Debajyoti Mondal and Mark Keil at the University of Saskatchewan. 

Thursday 12 October 2023

Speaker: Chi Hoi Yip (UBC)

Title: Prime powers in extremal set theory

Time: 11:30 am

• • Room: 115 Armes

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

Thursday 19 October 2023

Speaker: Andrii Arman (UM)

Title: Covering problems related to Borsuk’s conjecture.

Time: 11:30 am

• • Room: 115 Armes

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

Thursday 26 October 2023

Speaker: Max Gutkin (UM)

Title: Pebbling in Erdos-Renyi random graphs

Time: 11:30 am

• • Room: 115 Armes

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

Abstract: Graph pebbling is a game in which a collection of pebbles is placed on the vertices of a connected graph. A pebbling move consists of removing two pebbles from one vertex and placing a pebble on any adjacent vertex. Of interest is the pebbling number of a graph G: the least k such that for any collection of k pebbles on V(G) and any target vertex r, there exists a sequence of pebbling moves placing a pebble on r. It is well-known that the pebbling number of a graph G is at least |V(G)| and is, in general, bounded above by an exponential function of |V(G)|.  

The pebbling game has also been explored through Erdos-Renyi random graphs, with a focus on finding the smallest number m(n) of edges such that a graph on n vertices and m(n) edges with high probability has pebbling number n. 

In this talk, I will present two original results on the pebbling game in Erdos-Renyi random graphs, as well as their implications in the usual graph setting. First, I demonstrate an improvement on the current best-known result for the above question regarding graphs of pebbling number n. Second, I will show that although there exist graphs whose pebbling number is exponential in n, such graphs are extremely uncommon. Specifically, even on graphs with a relatively small number of edges, with high probability the pebbling number of a graph on n vertices is bounded above by a linear function of n. 

Thursday 2 November 2023

Speaker: Colin Krisko (UM)

Title: Labeling Schemes for Deterministic Radio Multi-Broadcast

Time: 11:30 am

• • Room: 115 Armes

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

Abstract: We consider the multi-broadcast problem in arbitrary connected radio networks consisting of n nodes. There are k designated source nodes and each has a distinct piece of information that it wants to share with the network.

We set out to determine the shortest possible labels so that multi-broadcast can be solved deterministically in the labeled radio network by some universal deterministic distributed algorithm.

First, we show that every radio network G with maximum degree ∆ can be labeled using O(min{log k, log ∆})-bit labels in such a way that multi-broadcast with k sources can be accomplished.

This bound is tight, in the sense that there are networks such that any labeling scheme sufficient for multi-broadcast with k sources requires Ω(min{log k, log ∆})-bit labels.

However, there are networks where significantly shorter labels are sufficient.

For example, we show how to construct a tree with maximum degree Θ(√n) in which multi-broadcast can actually be solved after labeling the nodes with O(1)-bit labels. So, we set out to find a labeling scheme that uses the optimal number of distinct labels in every network.

For all trees, we provide a labeling scheme and accompanying algorithm that will solve gossiping, and, we prove an impossibility result that demonstrates that our labeling scheme is optimal for gossiping in each tree.

In particular, we prove that Θ(log D(G))-bit labels are necessary and sufficient in every tree G, where D(G) denotes the distinguishing number of G.

Thursday 9 November 2023

Speaker: Myroslav Kryven (UM)

Title: Cops and Robbers on 1-Planar Graphs

Time: 11:30 am

• • Room: 115 Armes

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

Abstract: Cops and Robbers is a well-studied pursuit-evasion game in which a set of cops seeks to catch a robber in a graph G, where cops and robber move along edges of G. The cop number of G is the minimum number of cops that is sufficient to catch the robber. Every planar graph has cop number at most three, and there are planar graphs for which three cops are necessary [Aigner and Fromme, DAM 1984]. We study the problem for beyond-planar graphs, that is, graphs that can be drawn in the plane with few crossings. In particular, we focus on 1-planar graphs, that is, graphs that can be drawn in the plane with at most one crossing per edge. In contrast to planar graphs, we show that some 1-planar graphs have unbounded cop number. Meanwhile, for maximal 1-planar graphs, we prove that three cops are always sufficient and sometimes necessary. In addition, we characterize outer 1-planar graphs with respect to their cop number.

Thursday 14 December 2023

Speaker: Hermie Monterde (UManitoba)

Title: How do quantum states move across a graph?

Time: 11:30 am

• • Room: 115 Armes

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

Abstract: A network of interacting qubits (usually subatomic particles) can be modelled by a connected weighted undirected graph $G$. The vertices and edges of $G$ represent the qubits and their interactions in the network, respectively. Quantum mechanics dictate that the evolution of the quantum system determined by $G$ over time is completely described by the unitary matrix $U(t)=\exp(itA)$, where $A$ is the adjacency matrix of $G$. Here, we interpret the modulus of the $(u,v)$ entry of $U(t)$ as the probability that the quantum state at vertex $u$ is found in $v$ at time $t$. In this talk, we discuss the role of the underlying graphs in the study of quantum state transfer.