at 2:30pm
in SA6006
or via zoom

In pursuit-evasion games, a set of pursuers attempts to locate, eliminate, or contain an evader in a network. The rules, specified from the outset, greatly determine the difficulty of the questions posed above. For example, the evader may be visible, but the pursuers may have limited movement speed, only moving to nearby vertices adjacent to them.

Central to pursuit-evasion games is the idea of optimizing certain parameters, whether they are the search number, burning number, or localization number, for example. We report on progress in several pursuit-evasion games on graphs and conjectures arising from their analysis. Finding the values, bounds, and algorithms to compute these graph parameters leads to topics intersecting graph theory, the probabilistic method, and geometry.

at 2:30pm
in SA6006
or via zoom

(University of Lethbridge)

Let $G$ be a finite group acting transitively on $X$. We say $g,h \in G$ are intersecting if $gh^{-1}$ fixes a point in $X$. A subset $S$ of $G$ is said to be an intersecting set if every pair of elements in $S$ intersect. Cosets of point stabilizers are canonical examples of intersecting sets. The group action version of the classical Erdős-Ko-Rado problem asks about the size and characterization of intersecting sets of maximum possible size. A group action is said to satisfy the EKR property if the size of every intersecting set is bounded above by the size of a point stabilizer. A group action is said to satisfy the strict-EKR property if every maximum intersecting set is a coset of a point stabilizer. It is an active line of research to find group actions satisfying these properties. It was shown that all $2$-transitive satisfy the EKR property. While some $2$-transitive groups satisfy the strict-EKR property, not all of them do. However a recent result shows that all $2$-transitive groups satisfy the slightly weaker "EKR-module property" (EKRM), that is, the characteristic vector of a maximum intersecting set is a linear span of characteristic vectors of cosets of point stabilizers. We will discuss about a few more infinite classes of group actions that satisfy the EKRM property. I will also provide a few non-examples and a characterization of the EKRM property using characters of $G$.

at 2:30pm
in SA6006
or via zoom

In this talk, we introduce the notions of matching matrices in groups and vector spaces, which lead to some necessary conditions for existence of acyclic matching in abelian groups and its linear analogue. We also discuss the linear local matching property in field extensions to find a dimension criterion for linear locally matchable bases. We provide an upper bound for the dimension of primitive subspaces in a separable field extension.We finally provide an application of matchings about the fundamental theorem of algebra. Our tools mix combinatorics and linear algebra.

at 2:30pm
in SA6006
or via zoom

A directed graph $H$ consists of a set $V (H)$ of vertices together with a subset $A(H)$ of $V (H) \times V (H)$ which are called arcs. A hamiltonian dipath in a digraph is a dipath that visits each vertex exactly once. The Cartesian product $H_1 \mathbin{\Box} H_2$ of two digraphs $H_1$ and $H_2$ is the digraph with vertex set $V (H_1) \times V (H_2)$ where the vertex $(u_1, v_1)$ is joined to $(u_2, v_2)$ by an arc if and only if either $u_1 = u_2$ and $v_1 v_2 \in A(H_2)$ or $v_1 = v_2$ and $u_1 u_2 \in A(H_1)$. The Cartesian product $C_m \mathbin{\Box} C_n$, where $C_m$ and $C_n$ are two dicycles, is called the toroidal digrid with $m$ rows and $n$ columns. In this talk, we see that there exist two arc-disjoint hamiltonian dipaths in every toroidal digrid.

in SA6006
or via zoom

Shortcut graphs are graphs in which long enough cycles cannot embed without metric distortion. Shortcut groups are groups which act properly and cocompactly on shortcut graphs. These notions unify a surprisingly broad family of graphs and groups of interest in geometric group theory and metric graph theory including: systolic and quadric groups (in particular finitely presented $C(6)$ and $C(4)$–$T(4)$ small cancellation groups), cocompactly cubulated groups, hyperbolic groups, Coxeter groups and the Baumslag-Solitar group $\mathrm{BS}(1,2)$. Most of these examples satisfy a strong form of the shortcut property. I will discuss some of these examples as well as some general constructions and properties of shortcut graphs and groups.

at 2:30pm
in SA6006
or via zoom

(University of Lethbridge)

Harary and Sabidussi were the first to study the automorphisms of repeated graphs using the wreath product. Later Hemminger would go on to provide necessary and sufficient conditions for these of repeated automorphisms through the introduction of smorphisms and partitions of graphs. This notion of the wreath product tends to vary depending on the author, and comes under many different guises, including both the lexicographic product and gruppenkranz. We seek to find a generalised/alternate form of this notion and the theorem, to describe the automorphisms of any arbitrary finite connected graph $G$ using its symmetries and tree decomposition. One method for doing this is by studying the vertex connectivity of a graph $\kappa(G)$, and the associated separating sets with size equal to $\kappa(G)$. Following this we can decompose the graphs into blocks based upon these separating sets and construct the tree decomposition. Then we conjecture that the automorphisms of $G$ will be: the direct product of the automorphism of elements (excluding those in a separating set) in each block, with those automorphisms that are compatible with those in the separating set; in addition, to the semidirect product of a subset of the tree decompositions. For the case in which the vertex connectivity is one, we will present the definitive results which are currently in the process of being proved. For higher dimensional cases of vertex connectivity, we will present some of our latest findings and updated conjectures.

in SA6006
or via zoom

Associating graphs with groups date back to Arthur Cayley. In this lecture, we will discuss about another graph, called co-maximal subgroup graph $\Gamma(G)$ introduced by Akbari et al. in [1]. The co-maximal subgroup graph $\Gamma(G)$ of a group $G$ whose vertices are non-trivial proper subgroups of $G$ and two vertices $H$ and $K$ are adjacent if $HK = G$. Though the definition allows the possibility of $G$ to be infinite, in our discussion, we will focus mainly on finite groups. We discuss various graph parameters like diameter, connectedness, existence of isolated vertices, girth, bipartiteness etc. Finally, we will highlight some problems on realizability and graph isomorphisms, and some partial solutions to those questions in terms of properties of $G$. Most of the results presented in the lecture can be found in [1] and [2].

References.

1. S. Akbari, B. Miraftab and R. Nikandish: Co-maximal Graphs of Subgroups of Groups, Canadian Math Bulletin, Vol. 60(1), pp.12-25, 2017.
2. A. Das, M. Saha and S. Alkaseasbeh: On Co-Maximal Subgroup Graph of a Group, https://arxiv.org/abs/2103.14284

via zoom

The talk is about finite connected 4-valent graphs admitting an edge-transitive and vertex-transitive subgroup \(G\) of automorphisms which preserves an orientation of the edges. But I will first talk about the general approach to describing families of graphs with strong symmetry properties using certain quotients.

A connected \(G\)-edge-transitive oriented 4-valent graph is basic if each quotient, modulo the orbits of a normal subgroup of \(G\) is degenerate: it is either a cycle (oriented or unoriented) or consists of a single vertex or a single edge. In other words, these are the graphs which are basic relative to normal quotient reduction. I will discuss the structure of these basic graphs using both group theoretic and combinatorial information. There are three kinds of basic examples: quasiprimitive, bi-quasiprimitive, and cyclic types. Apart from six infinite families of well-understood examples, the group \(G\) has a unique minimal normal subgroup \(N=T^k\), for some simple group \(T\), and the integer \(k\) is bounded: \(k\in \left\{1, 2\right\}\) for quasiprimitive type; \(k \in \left\{1, 2, 4, 8\right\}\) for bi-quasiprimitive type; and \(k\) is bounded above by certain explicit functions of \(r\) for cycle type, where the quotient modulo the \(N\)-orbits is a cycle of length \(r\). All the bounds are tight, and in all cases we have constructed infinite families of examples meeting the bounds.

Perhaps the most startling case is where the quotient mod \(N\) is an unoriented cycle \(C\) of length \(r\), and \(N = T^k\) with \(T\) a nonabelian simple group. In this case our bound is \(k\leq r2^r\). Here we have given examples meeting the bound only for \(r=3\), hence \(k=24\), and for any simple group \(T\) which can be generated by elements \(a, b\) of orders 2 and 3, respectively.

Collaborators. The work on the quasiprimitive case is joint with Jehan Al-bar, Ahman Al-kenani, Najat Muthana, and Pablo Spiga, published in 2016 and 2017. The other cases are a collaboration with Nemanja Poznanovic; the bi-quasiprimitive type has just been published in Algebraic Combinatorics, while the results for cycle type will first appear in Nem's thesis from the University of Melbourne.

This talk is intended to be accessible to beginning graduate students / students with a bachelor's degree in Mathematics.

Registration: Register here to receive the meeting link.
CRG on Movement and Symmetry in Graphs Distinguished Lecture Series

at 2:30pm
in SA6006
or via zoom

In this talk I will present a study on the Gromov's hyperbolicity of some product of graphs. The presentation is based on joint works that studied hyperbolicity of the lexicographic product, tensor product and graph join of two graphs, respectively. Product of graphs is a topic that has widely been study due to its applications in networks and regular structures. We characterize the hyperbolicity of these products

Lexicographic product: the lexicographic product graph $G_1\circ G_2$ is hyperbolic if and only if $G_1$ is (unless if $G_1$ is trivial). In particular, we obtain the sharp inequalities $\delta(G_1)\leq\delta(G_1\circ G_2)\leq\delta(G_1)+3/2$, if $G_1$ is not a trivial graph, and we prove that second inequality is attained only if $G_1$ is a tree.

Tensor product: the tensor product graph $G_1\times G_2$ is hyperbolic, then one factor is bounded and the other is hyperbolic. Besides, we prove that this necessary condition is also sufficient in many cases. In other cases, we find (not so simple) characterizations of hyperbolic tensor products.

Graph join: the graph join $G_1+G_2$ is always hyperbolic since it's bounded. Moreover, we prove that for every two graphs $G_1$ and $G_2$ the hyperbolicity constant of its graph join $\delta(G_1+G_2)$ belongs to $\{ 0,\frac34, 1, \frac54, \frac32\}$ characterizing them in each case. Furthermore, we obtain sharp bounds, and even formulas in many cases, for the hyperbolicity constant.

at 2:30pm
in SA6006
or via zoom

A perfect matching ($\mathcal{PM}$) in the complete graph $K_{2k}$ is a set of edges by which every vertex is covered exactly once. Two $\mathcal{PM}$s are said to be $t$-intersecting if they have at least $t$ edges in common. Another type pf intersection that we can define on $\mathcal{PM}$s is set-wise intersection. Two $\mathcal{PM}$s $P$ and $Q$ of a graph on $2k$ vertices are said to be set-wise $t$-intersecting if there exist edges $P_{1}, \ldots, P_{t}$ in $P$ and $Q_{1}, \ldots, Q_{t}$ in $Q$ such that the union of edges $P_{1}, \ldots, P_{t}$ has the same set of vertices as the union of $Q_{1}, \ldots, Q_{t}$. In this talk we show an extension of the famous Erdős-Ko-Rado theorem to intersecting and set-wise intersecting $\mathcal{PM}$ for $t=2$ and $t=3$.

at 2:30pm
in SA6006
or via zoom

Consider a group $G$ acting transitively on the vertices of an infinite, cubic (3-regular) graph $\Gamma$ such that the vertex stabilizers are infinite. We will see that if $G$ is also edge-transitive on $\Gamma$, then $\Gamma$ is the infinite cubic tree, and if not, then $G$ has precisely two orbits on the edges. I will then focus on the latter case, with the added assumption that the graph has exactly two ends.

The talk is based on joint work with Waltraud Lederle and Rögnvaldur Möller, arxiv.org/abs/2101.04064.