Fall 2024
Speaker: Theodore Mishura (Toronto Metropolitan University)
Date and time: December 5 at 10:30 AM.
Location: N638/Ross, York University
Title: How to cool a graph
Abstract: We introduce a new graph parameter called the cooling number, inspired by the spread of influence in networks and its predecessor, the burning number. Given a graph G, the cooling number of G is determined via the following single player round-based process: Each round, all uncooled neighbors of each cooled vertex become cooled; then, an uncooled vertex is selected by the player and cooled. The maximum number of rounds any such process can take is the cooling number of G, and it measures the speed of a slow-moving contagion in a graph; the lower the cooling number, the faster the contagion spreads. We provide tight bounds on the cooling number via a graph’s order and diameter, determine the cooling number of certain special graph families, and discuss complexity results.
Speaker: Martijn Gösgens (Toronto Metropolitan University)
Date and time: November 7 at 10:30 AM.
Location: N638/Ross, York University
Title: The Erdős-Rényi Random Graph Conditioned on Every Component Being a Clique
Abstract: We consider an Erdős-Rényi random graph, conditioned on the rare event that all connected components are fully connected. Such graphs can be considered as partitions of vertices into cliques. Hence, this conditional distribution defines a distribution over partitions. Using tools from analytic combinatorics, we prove limit theorems for several graph observables: the number of cliques; the number of edges; and the degree distribution. We consider several regimes of the connection probability p as the number of vertices n diverges. For \(p=\frac{1}{2}\), the conditioning yields the uniform distribution over set partitions, which is well-studied, but has not been studied as a graph distribution before. For \(p<\frac{1}{2}\), we show that the number of cliques is of the order \(\frac{n}{\sqrt{\log n}}\), while for \(p>\frac{1}{2}\), we prove that the graph consists of a single clique with high probability. This shows that there is a phase transition at \(p=\frac{1}{2}\). We additionally study the near-critical regime \(p_n\downarrow \frac{1}{2}\), as well as the sparse regime \(p_n\downarrow 0.\)
Speaker: Mariia Sobchuk (University of Waterloo)
Date and time: October 24 at 10:30 AM.
Location: N638/Ross, York University
Title: Quantum isomorphisms
Abstract: In this talk I will talk about relationships between Godsil-McKay switching, coherent algebras and quantum isomorphisms as well as describe a new family of graphs with quantum symmetry.
Speaker: Sarobidy Razafimahatratra (Fields Institute)
Date and time: October 10 at 10:30 AM.
Location: N638/Ross, York University
Title: On cocliques in a Cayley graph of \(\operatorname{GL}_n(\mathbb{F}_q)\) generated by matrices with eigenvalue \(-1\)
Abstract: Let \(q\) be a prime power and \(n\geq 2\) an integer. Consider the graph \(\Gamma_q(n)\) whose vertex set is \(\operatorname{GL}_{n}({\mathbb{F}_q})\), and where two distinct elements \(A\) and \(B\) of \(\operatorname{GL}_{n}(\mathbb{F}_{q})\) are adjacent if \(A+B\) is singular. In [Linear Algebra Appl. 681 (2024):89–96], it was recently shown by Nica that \(\alpha(\Gamma_q(n))\leq q^{n^2-n+1}\) for all values of \(q\).
In this talk, I will show that Nica’s bound can be significantly improved in some cases. First, I will show for \(q\) a power of \(2\) that \(\alpha(\Gamma_q(n)) = {q^n-1}\). Then for the \(2\)-dimensional case, I will show that \(\alpha(\Gamma_q(2)) \leq \frac{q(q-1)^2}{2}\), when \(q\) is odd.
Speaker: Blake Shirman (York University)
Date and time: September 26 at 10:30 AM.
Location: N638/Ross, York University
Title: Using binary trees to count a special class of lattice paths
Abstract: After an introduction to NE (North, East) lattice paths, we rotate our frame of reference into UD (Up, Down) lattice paths and add a ‘(max) height’ constraint. We count NE lattice paths by two methods: first by encoding the steps as binary strings (a simple counting problem to solve); second by repeatedly applying Pascal’s recurrence to generate a decision tree, which can be carefully transformed back into a lattice grid. While logically circular for NE paths, this second method is surprisingly helpful for counting height-restricted UD paths. After one more reflection, we see that the UD path problem is equivalent to an NE lattice with different dimensions, deriving a nice, closed form! We close by considering some other bivariate sequences to see how far we can generalize the method. Results on height-restricted UD paths come from work on a recent submission by Acton, Petersen, Shirman, and Tenner https://arxiv.org/abs/2401.11680.