Speaker: Myroslav Kryven (UManitoba CS)
Title: On Edge Density of arc-RAC Graphs
Time: 11:30 am
Room: 418 Machray Hall
Zoom link: https://umanitoba.zoom.us/j/66343288658 password is the first six Fibonacci numbers, starting with 11...
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.
Speaker: Venkata Raghu Tej Pantangi (URegina)
Title: Cameron-Liebler Sets in Permutations Groups
Time: 11:30 am
Room: 418 Machray Hall
Zoom link: https://umanitoba.zoom.us/j/66343288658 password is the first six Fibonacci numbers, starting with 11...
Speaker: Ahmad Mojallal (Regina)
Title: Zero forcing number for the Cartesian products of graphs
Time: 11:30 am
Room: 418 Machray Hall
Zoom link: https://umanitoba.zoom.us/j/66343288658 password is the first six Fibonacci numbers, starting with 11...
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?
Speaker: Hector Baños (Dalhousie)
Title: Network Inference Algorithm under the Coalescent Model
Time: 11:30 am
Room: 418 Machray Hall
Zoom link: https://umanitoba.zoom.us/j/66343288658 password is the first six Fibonacci numbers, starting with 11...
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.
Speaker: Hanmeng (Harmony) Zhan (SFU)
Title: Discrete Quantum Walks on Graphs
Time: 11:30 am
Room: 418 Machray Hall
Zoom link: https://umanitoba.zoom.us/j/66343288658 password is the first six Fibonacci numbers, starting with 11...
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.
Speaker: Max Gutkin (UManitoba)
Title: The Kahn-Kalai Conjecture
Time: 11:30 am
Room: 418 Machray Hall
Zoom link: https://umanitoba.zoom.us/j/66343288658 password is the first six Fibonacci numbers, starting with 11...
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.
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
Room: 418 Machray Hall
Zoom link: https://umanitoba.zoom.us/j/66343288658 password is the first six Fibonacci numbers, starting with 11...
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.
Speaker: Andrii Arman (UManitoba)
Title: On the chromatic number of Euclidean space
Time: 11:30 am
Room: 418 Machray Hall
Zoom link: https://umanitoba.zoom.us/j/66343288658 password is the first six Fibonacci numbers, starting with 11...
Speaker: Stephane Durocher (UManitoba)
Title: Geometric Data Depth
Time: 11:30 am
Room: 418 Machray Hall
Zoom link: https://umanitoba.zoom.us/j/66343288658 password is the first six Fibonacci numbers, starting with 11...
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.
Speaker: Stephane Durocher (UManitoba)
Title: Geometric Data Depth - Part II
Time: 11:30 am
Room: 418 Machray Hall
Zoom link: https://umanitoba.zoom.us/j/66343288658 password is the first six Fibonacci numbers, starting with 11...
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.