## Events Search and Views Navigation

## February 2022

### Atlantic Graph Theory Seminar: Margaret-Ellen Messinger (Mount Allison University)

Reconfiguration for Dominating Sets Given a problem and a set of feasible solutions to that problem, the associated reconfiguration problem involves determining whether one feasible solution to the original problem can be transformed to a different feasible solution through a sequence of allowable moves, with the condition that the intermediate stages are also feasible solutions. Any reconfiguration problem can be modelled with a reconfiguration graph, where the vertices represent feasible solutions and two vertices are adjacent if and only if…

Find out more »### Atlantic Graph Theory Seminar: Ferenc Bencs (University of Amsterdam)

In this talk, I will show regions that contain no complex zeros the edge-cover polynomials of hypergraphs. The edge cover polynomial of a graph $G$ is the generating function of edges that covers $V(G)$. It is known that the zeros of this polynomial have length at most $\frac{(2+\sqrt{3})^2}{1+\sqrt{3}}$, that we strengthen by showing that it is at most $4$. We use the general subgraph counting polynomial of Wagner to establish this result along with its generalization for the edge cover…

Find out more »## March 2022

### Atlantic Graph Theory Seminar: Pjotr Buys (University of Amdsterdam)

About a year ago Jason Brown spoke in our seminar (of the university of Amsterdam) about the two-terminal reliability polynomial and left us with some questions about the closure of the complex zeros of all such polynomials (the zero-locus). In this talk I will define a way to capture, for a certain parameter, whether the set of all two-terminal reliability polynomials behaves chaotically around this parameter or not, i.e. whether this parameter is active or passive. I call the set…

Find out more »### Atlantic Graph Theory Seminar: Theodore Kolokolnikov (Dalhousie)

We study the algebraic connectivity for several classes of random semi-regular graphs. For large random semi-regular bipartite graphs, we explicitly compute both their algebraic connectivity and as well as the full spectrum distribution. For an integer d in , we find families of random semi-regular graphs that have higher algebraic connectivity than a random d-regular graphs with the same number of vertices and edges. On the other hand, we show that regular graphs beat semi-regular graphs when d >8. More…

Find out more »## April 2022

### Atlantic Graph Theory Seminar: John Engbers (Marquette University)

Extremal questions for vertex colorings of graphs For graphs $G$ and $H$, an $H$-coloring of $G$ is a map from the vertices of $G$ to the vertices of $H$ so that an edge in $G$ is mapped to an edge in $H$. The graph $H$ can be thought of as the allowable coloring scheme: its vertices are the colors used and its edges indicating colors that can appear on the endpoints of an edge in $G$. When the graph $H$…

Find out more »### Atlantic Graph Theory Seminar: Aysel Erey (Gebze Technical University, Turkey)

Graph polynomials In this talk, I will discuss various aspects of several graph polynomials such as the location of their roots, their combinatorial properties and extremal questions. Join Zoom Meeting: link

Find out more »## November 2022

### Atlantic Graph Theory Seminar: Sebastian Cioaba, University of Delaware

Addressing graphs and hypergraphs In 1970s, Ron Graham and Henry Pollak introduced the notion of graph addressing which is a labeling of the vertices of an undirected graph by words of the same length over the alphabet {0,1,*} such that the distance between any two vertices equals the number of positions in their labels/addresses where one vertex has a 0 and the other one has a 1. The minimum of length of such words has been investigated by various people…

Find out more »## January 2023

### Atlantic Graph Theory Seminar: Pawel Pralat, Metropolitan University of Toronto

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…

Find out more »### Atlantic Graph Theory Seminar: Jane (Pu) Gao, University of Waterloo

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…

Find out more »## February 2023

### Atlantic Graph Theory Seminar: Jason Brown, Dalhousie University

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…

Find out more »