An Unsupervised Framework for Comparing Graph Embeddings The goal of many machine learning applications is to make predictions or discover new patterns using graph-structured data as feature information. In order to extract useful structural information from graphs, one might want to try to embed it in a geometric space by assigning coordinates to each node such that nearby nodes are more likely to share an edge than those far from each other. There are many embedding algorithms (based on techniques…

Conditions for perfect matchings in random sparse bipartite graphs Given a uniformly random sparse matrix A, with specified number of nonzero entries in columns and rows, we determine when A has full row rank over a finite field. As a corollary, by considering A as the adjacency matrix of a bipartite graph, our result determines the conditions for the existence of a perfect matching in various models of random sparse bipartite graphs. We will explore some useful insight from statistical…

Colourings, Polynomials and Roots A lot has happened since graph colourings first arose as an applied problem in cartography – do four colours always suffice to distinguish countries when colouring a map? Along the way to the proof, the related enumeration function to count the number of k-colourings was proposed. While the latter didn’t help much in the quest for the Four Colour Theorem, it did lead to a fascinating branch of graph theory, namely chromatic polynomials. While polynomials are…

Progress towards the Burning Number Conjecture The burning number b(G) of a graph G is the smallest integer k such that G can be covered by k balls of radii respectively 0,...,k-1, and was introduced independently by Brandenburg and Scott at Intel as a transmission problem on processors and Bonato, Janssen and Roshanbin as a model for the spread of information in social networks. The Burning Number Conjecture claims that b(G)<=\lceil\sqrt{n}\rceil, where n is the number of vertices of G. This bound is tight for paths. The previous best bound for this problem, by Bastide…

Speaker 1: Isaac McMullin Existence of Optimal Split Reliability Polynomials One of the most common models of robustness of a graph against random failures has all vertices operational, but the edges independently operational with probability p. On one hand, one can ask for the probability that all vertices can communicate (all-terminal reliability) while on the other hand, we can ask that two specific vertices (or terminals) can communicate with each other (two-terminal reliability). While both of these questions have been…

Avoiding additive powers in words A word is a sequence of symbols taken from some finite alphabet. A square is a word of the form xx, where x is a nonempty word. It is well-known that there are infinite words over an alphabet of size 3 that contain no squares. Suppose now that the alphabet is some finite subset of the integers. An additive square is a word of the form xx', where x and x' have the same nonzero…

Speaker 1: Caleb Jones, Memorial University   Title: Extending Graph Burning to Hypergraphs   Abstract: We introduce a round-based model much like graph burning which applies to hypergraphs. The rules for this new model are very natural,and generalize the original model of graph burning. We also introduce a variant called lazy hypergraph burning, along with a new parameter, the lazy burning number. Interestingly, lazily burning a graph is trivial, while lazily burning a hypergraph can be quite complicated. Moreover, the lazy burning model is…