Winter 2023 talks

Thursday 2 February 2023

Speaker: Myroslav Kryven (UManitoba CS)

Title: On Edge Density of arc-RAC Graphs

Time: 11:30 am

Abstract:

In a drawing of a graph crossings often clutter the drawing and make it hard to read. Therefore, crossing optimization is one of the fundamental problems in computer science. Since for many graphs (non-planar) we cannot get rid of crossings completely, the goal is to make them as distinguishable as possible. If the edges are drawn straight-line, we can maximize the crossing angle. Graphs that can be drawn with straight-line edges and right-angle crossings are called RAC graphs. They are well explored in the literature: they can have at most 4n − 10 edges (where n is the number of vertices) and this is tight, also their relation to other families of beyond-planar graphs (graphs that can be drawn with few crossings) is well understood.

In this talk we consider a generalization of RAC graphs where we allow drawing edges with circular arcs but still insist on right-angle crossings. We will discuss their edge density and look at some open problems around this class of graphs.

Thursday 9 February 2023

Speaker: Venkata Raghu Tej Pantangi (URegina)

Title: Cameron-Liebler Sets in Permutations Groups

Time: 11:30 am

Thursday 16 February 2023

Speaker: Ahmad Mojallal (Regina)

Title: Zero forcing number for the Cartesian products of graphs

Time: 11:30 am

Abstract:

The zero forcing number, Z(G), of a graph G is the minimum cardinality of a set S of black vertices (whereas vertices in V(G) \ S are coloured white) such that V(G) is turned black after finitely many applications of ``the color-change rule": a white vertex is converted to a black vertex if it is the only white neighbour of a black vertex. 

Let G and H be two connected graphs and let G◻︎H be the Cartesian product of the graphs G and H. In this talk we are trying to answer to the following question:

Is Z(G ◻︎H) ≥  Z(G)Z(H) + 1 for all connected graphs G and H?

Thursday 2 March 2023

Speaker: Hector Baños (Dalhousie)

Title: Network Inference Algorithm under the Coalescent Model

Time: 11:30 am

Abstract:

Phylogenetic networks are used to describe evolutionary relationships between species in the presence of hybridization. The network multispecies coalescent model (NMSC) is a standard probabilistic model describing the formation of gene trees in the presence of hybridization and incomplete lineage sorting. We present the outline of NANUQ, an algorithm to infer level-1 networks (Networks with no interlocking cycles) from gene trees sampled under the NMSC. Particularly, in this talk, I will focus on the combinatorial aspects of NANUQ, which involve representing evolutionary events in the presence of hybridization using "splits-graphs" and other combinatorial objects.

Thursday 9 March 2023

Speaker: Hanmeng (Harmony) Zhan (SFU)

Title: Discrete Quantum Walks on Graphs

Time: 11:30 am

Abstract:

Discrete quantum walks are motivated by search problems. One of the best known quantum algorithms, Grover’s search, is a discrete quantum walk on the complete graph with loops. From an algebraic perspective, a discrete quantum walk is determined by a unitary matrix that encodes some graph, and—just like the adjacency matrix and the Laplacian matrix—its spectrum contains important information about the graph, which can be used to study the behaviour of the walk. 

 

In this talk, I will give an overview of discrete quantum walks, show how properties of these walks relate to properties of the underlying graphs, and discuss some future directions in this area. Part of the talk is based on my joint book, Discrete Quantum Walks on Graphs and Digraphs, with Chris Godsil. No knowledge of quantum physics is required.


Thursday 16 March 2023

Speaker: Max Gutkin (UManitoba)

Title: The Kahn-Kalai Conjecture

Time: 11:30 am

Abstract:

If edges in a graph are generated randomly and independently with probability p, what can be said about the properties of the graph? For properties such as subgraph containment that are preserved by increasing families, increasing p can result in a sudden jump in the probability that the graph has the property of interest. The specific p at which the jump occurs is called a threshold, and there is a relationship between a threshold and the value of p for which the expected number of copies of a subgraph is greater than 0 (the expectation-threshold). The Kahn-Kalai expectation-threshold conjecture and its recent proof by Park and Pham specify the precise nature of this relationship by providing an upper bound on thresholds using the expectation-threshold. In this talk I will give an introduction to random graphs, thresholds for random graph properties, and a sketch of the main proof ideas in Park and Pham's paper.  

Thursday 30 March 2023

Speaker: Simona Bonvicini (Università degli studi Modena e Reggio Emilia)

Title: A graph theory problem related to the self-assembly of DNA structures

Time: 11:30 am

Abstract:

(based on a joint work with Margherita Maria Ferrari)

The self-assembly of DNA structures can be obtained by several methods that are based on the Watson-Crick complementary properties of DNA strands. We consider the method of branched junction molecules: star-shaped molecules whose arms have cohesive ends that allow the molecules to join together in a prescribed way and form a larger molecule (DNA complex). 

In graph theory terminology,  a branched junction molecule is called a tile and consists of a vertex with labeled half-edges; labels are the cohesive ends and belong to a finite set of symbols,  say {a, â: a ∈ Σ}.  A tile is denoted by the multiset consisting of the labels of the half-edges (the tile type).  We can create an edge between two vertices u, v if and only if u has a half-edge labeled by a and v has a half-edge labeled by â; the edge thus obtained is said to be a bond-edge of type aâ. By connecting the vertices according to the labels, we can construct a graph G representing a DNA complex. 

The following problem is considered: determine the minimum number of tile types and bond-edge types that are necessary to construct a given graph G.

In this seminar we discuss the above problem and show some techniques providing an upper bound for the number of bond-edge types that are necessary to construct an arbitrary graph. 

Thursday 13 April 2023

Speaker: Andrii Arman (UManitoba)

Title: On the chromatic number of Euclidean space

Time: 11:30 am

Thursday 27 April 2023

Speaker: Stephane Durocher (UManitoba)

Title: Geometric Data Depth

Time: 11:30 am

Abstract:


This talk provides a survey of depth measures for geometric data, with a focus on combinatorial depth measures. For each depth measure we examine its properties, algorithms for computing a depth query, and corresponding depth medians. 

Thursday 4 May 2023

Speaker: Stephane Durocher (UManitoba)

Title: Geometric Data Depth - Part II

Time: 11:30 am

Abstract:


Continuation of the 27 April talk: This talk provides a survey of depth measures for geometric data, with a focus on combinatorial depth measures. For each depth measure we examine its properties, algorithms for computing a depth query, and corresponding depth medians.