Speaker: Christopher van Bommel (Guelph)
Title: Eternal Distance-2 Domination in Trees
Time: 1:00 pm
Room: Mathematics boardroom
Zoom link: https://umanitoba.zoom.us/j/66343288658 password is the first six Fibonacci numbers, starting with 11...
Abstract: A distance-k dominating set of a graph is a subset of the vertices such that every vertex of the graph is at distance at most k from a vertex in the subset. In the eternal distance-k dominating problem, we start with a distance-k dominating set of the graph, and then must respond to an infinite sequence of attacks at arbitrary vertices, where for each attack, we replace each vertex in the current distance-k dominating set with a vertex at distance at most k (which may be the same vertex) so that we obtain a new distance-k dominating set that contains the attacked vertex. The eternal distance-k domination number of a graph is the minimum possible cardinality of the initial set. We focus primarily on the eternal distance-2 domination number of trees, and discuss an algorithm for computing this value, bounds on the value, the trees that satisfy equality in these bounds, characterizing eternal distance-2 domination critical graphs, and extensions to eternal distance-k domination. This is joint work with Alexander Clow (SFU).
Speaker: Colin Desmarais (Vienna)
Title: Depths in random recursive metric spaces
Time: 1:00 pm
Room: Mathematics boardroom
Zoom link: https://umanitoba.zoom.us/j/66343288658 password is the first six Fibonacci numbers, starting with 11...
Abstract: As a generalization of random recursive trees and preferential attachment trees, we consider random recursive metric spaces. These spaces are constructed from random blocks, each a metric space equipped with a probability measure, containing a labelled point called a hook, and assigned a weight. Random recursive metric spaces are equipped with a probability measure made up of a weighted sum of the probability measures assigned to its constituent blocks. At each step in the growth of a random recursive metric space, a point called a latch is chosen at random according to the equipped probability measure and a new block is chosen at random and attached to the space by joining together the latch and the hook of the block.
In this talk, I will defined random recursive metric spaces, and outline the proofs of a law of large numbers and a central limit theorem for the insertion depth, the distance from the master hook to the latch chosen. A classic argument for random recursive trees shows that the insertion depth is distributed as a sum of Bernoulli random variables. This argument is generalized for random recursive metric spaces via a martingale central limit theorem.
Speaker: Atishaya Maharjan
Title: Exploring Perfect Binary Trees with relation to the HK-Property
Time: 1:00 pm
Room: Mathematics boardroom
Zoom link: https://umanitoba.zoom.us/j/66343288658 password is the first six Fibonacci numbers, starting with 11...
Abstract: A perfect binary tree is a full binary tree in which all leaves have the same depth. A set of cocliques of size $k$ ($k$-coclique) in a graph, containing a fixed vertex $v$ is called a star, and is denoted by $\mathcal{I}^n_G(v)$. We study the size of stars for different vertices in a perfect binary tree. This structure is useful in studying the Erd\H{o}s-Ko-Rado theorem. Hurbert and Kumar conjectured that in trees, the largest stars are on the leaves. The conjecture was shown to be false independently by Baber, Borg, and Feghali, Johnson and Thomas. However, in some classes of trees such as caterpillars, the conjecture holds true. In this paper, we study the perfect binary trees through the lens of star centers and seek to answer if the HK-property holds for perfect binary trees. We also aim to expand the definition of the flip function mentioned by Estrugo and Passtine in the context of perfect binary trees. We then use an algorithm by Niskanen and R. J. to generate all cocliques of a perfect binary tree of depth $d$ and compare the number of $k$-cocliques containing a vertex $v$ and a leaf $l$ to see if the HK-property holds for perfect binary trees.