Karen Gunderson, University of Manitoba
Karen Meagher, University of Regina
Bojan Mohar, Simon Fraser University
Joy Morris, University of Lethbridge
Given a group $G$ and $S \subset G$, the Cayley (di)graph Cay$(G,S)$ is the graph whose vertex set is $G$ with an arc from $g$ to $h$ if and only if $hg^{-1}\in S$. Although the graph isomorphism problem in general is only known to be quasipolynomial, for some families of Cayley (di)graphs it reduces to understanding the automorphisms of the groups that are involved. The question of when this happens is known as the Cayley Isomorphism (CI) problem.
I will provide an overview of the current state of the CI problem for both finite and infinite groups.
The celebrated Erdos-Ko-Rado theorem can be interpreted as a characterization of the size and structure of independent sets/co-cliques of maximum size in Kneser Graphs. Similar characterizations have been observed in a few other classes of Distance Regular Graphs. In this talk, we will consider a closely related problem of finding the size and structure of the biggest induced forest in a graph. This question is inspired by a graph process known as `Bootstrap Percolation’. In this process, given a fixed threshold $r$ and a set of ‘initially infected’ vertices, the states of vertices (either healthy or infected) are updated indiscrete time steps: any healthy vertex with at least $r$ infected neighbours becomes itself infected. An initially infected set of vertices percolates if the infection spreads to the entire graph. One of the extremal questions related to this process is to find the smallest percolating set. In the special case of $d$-regular graphs, when $r=d$, a set percolates exactly when its complement is independent. Meanwhile, in the case $r=d−1$, a set percolates if its complement is a set of vertices that induce a forest. We will characterize maximum induced forests in the Kneser graph and some other families of Distance Regular Graphs.
A linear space is a point-line incidence structure such that each pair of points is incident to exactly one line. It is regular if all lines are incident to the same number of points. (This is equivalent to a balanced block design with $\lambda=1$.)
I will discuss linear spaces which admit a very special class of groups of automorphisms, called extremely primitive groups. Together with Melissa Lee, we have almost finished the classification of these linear spaces. In the process, we discovered some new interesting constructions which I will describe.
A set of permutations $\mathcal{F} \subset Sym(V)$ is said to be intersecting if any two of its elements agree on some element of $V$. The intersection density, $\rho(G)$, of a finite transitive permutation group $G \leq Syn(V)$, is the maximum ratio $\frac{|\mathcal{F}| |V|}{|G|}$ where $\mathcal{F}$ runs through all intersecting sets of $G$. If the intersection density of a group is equal to 1, we say that a group has the Erdos-Ko-Rado property. The intersection density for many groups has been considered, mostly considering which groups have the Erdos-Ko-Rado property. In this talk I will consider the intersection density of a vertex-transitive graph which is defined to be the maximum value of $\rho(G)$ where is a transitive subgroup of the automorphism group of $X$. I will focus on the intersection density of the Kneser graph $K(n,3)$, for $n\geq 7$.
In 1975, Szemeredi proved that for every real number $\delta > 0 $ and every positive integer $k$, there exists a positive integer $N$ such that every subset $A$ of the set ${1, 2, \cdots, N }$ with $|A| \geq \delta N$ contains an arithmetic progression of length $k$. There has been a plethora of research related to Szemeredi’s theorem in many areas of
mathematics. In 1990, Cameron and Erdos proposed a conjecture about counting the number of subsets of the set ${1,2, \dots, N}$ which do not contain an arithmetic progression of length $k$. In the talk, we study a natural higher dimensional version of this conjecture by counting
the number of subsets of the $k$-dimensional grid ${1,2, \dots, N}^k$ which do not contain
a $k$-dimensional corner that is a
set of points of the
form ${ a } \cup { a+ de_i : 1 \leq i \leq k }$ for some $a \in {1,2, \dots, N}^k$ and $d > 0$, where $e_1,e_2, \cdots, e_k$ is the standard basis of $\mathbb{R}^k$.
Our main tools for proof are the hypergraph container method and the supersaturation result
for $k$-dimensional corners in sets of size $\Theta(c_k(N))$, where $c_k(N)$ is the maximum size of a $k$-dimensional corner-free subset of ${1,2, \dots, N}^k$.
We would like to know for which function f(k) it is true that any oriented graph of minimum semidegree at least f(k) necessarily contains a given oriented path with k edges. For the directed path, f(k)=k/2 works, and perhaps this is true for other orientations as well. We show that this is approximately the case for large antidirected paths, and more generally, for large antidirected trees of bounded maximum degree. This is joint work with Camila Zárate.
It is a classical problem to determine the minimum and maximum genus of a $2$-cell embedding of a graph $G$. However there will be many other embeddings with a genus between these two values: we will study the average genus across all of these embeddings.
We give an overview of recent work on the average genus for fixed graphs. We also discuss extensions of the problem to random graphs and random maps, and links with representation theory.
The symmetry of a discrete object (such as a graph, map or polytope, and even a Riemann surface or 3-manifold) can be measured by its automorphism group – the group of all structure-preserving bijections from the object to itself. (For example, an automorphism of a map takes vertices to vertices, edges to edges, faces to faces, and preserves incidence among these elements.) But also/conversely, objects with specified symmetry can often be constructed from groups.
In this talk I will give some examples showing how this is possible, and some methods which help, and describe some significant outcomes of this approach across a range of topics. Included will be some very recent developments, including a few unexpected discoveries.
The game of Cops and Robber is traditionally played on a finite graph. But one can define the game that is played on an arbitrary geodesic space (a compact, path-connected space endowed with intrinsic metric). It is shown that the game played on metric graphs is essentially the same as the discrete game played on abstract graphs and that for every compact geodesic surface there is an integer $c$ such that $c$ cops can win the game against one robber, and $c$ only depends on the genus $g$ of the surface. It is shown that $c=3$ for orientable surfaces of genus $0$ or $1$ and nonorientable surfaces of crosscap number $1$ or $2$ (with any number of boundary components) and that $c=O(g)$ and that $c=\Omega(\sqrt{g})$ when the genus $g$ is larger. The main motivation for discussing this game is to view the cop number (the minimum number of cops needed to catch the robber) as a new geometric invariant describing how complex is the geodesic space.
For $r\geq 1$, a graph has $r$-friendship property if every pair of vertices has exactly $r$ common neighbours. The motivation for this definition is from the Friendship theorem, which is on the graphs with $1$-friendship property. The Friendship theorem, first proved by Erdős, Rényi, and Sós in 1966, states that if $G$ is a graph in which every pair of vertices has exactly one common neighbour, then $G$ has a universal vertex $v$ adjacent to all others, and the graph induced by $V(G)\setminus {v }$ is a matching. In this presentation, we study graphs with $r$-friendship property, where $r\geq 2$. We show all such graphs are strongly regular. Furthermore, we prove that for any $r\geq 2$, there are only finitely many graphs with $r$-friendship property. This is an ongoing joint work with Karen Gunderson.
Graphs having three distinct eigenvalues are a fundamental object of study in spectral graph theory. Strongly regular graphs are the most well-studied examples. In 1995, at the 15th British Combinatorial Conference, Willem Haemers asked do there exist any connected graphs having three distinct eigenvalues apart from strongly regular graphs and complete bipartite graphs. Haemer’s question prompted responses from Muzychuk-Klin and Van Dam who found new families of nonregular graphs having three distinct eigenvalues.
Muzychuk and Klin initiated the study of a graph with three distinct eigenvalues via its Weisfeiler-Leman closure. They classified such graphs whose Weisfeiler-Leman closure has rank at most 7. In this talk, we extend this classification up to rank 9. Our results include a correction of the literature (where the rank 8 case was erroneously claimed to be impossible) and discussion of further study.
When considering proper colourings of oriented graphs, one possible approach is to insist that the colouring be consistent with the orientation: all edges between two colour classes should be oriented in the same way. The oriented chromatic number of an oriented graph is the least $k$ so that there is a homomorphism from the oriented graph to some tournament of order $k$. In this talk, I will present new work with Nir on the oriented chromatic number of random models of oriented graphs of bounded degree. Previous extremal results can be used to bound the oriented chromatic number of a random $d$-regular oriented graph between $\Omega(\sqrt{2}^d)$ and $O(d^2 2^d)$. Using colourings by doubly-regular tournaments, we improve the upper bound to $O(\sqrt{e}^d)$. I will present these results and discuss an optimization result for functions over doubly stochastic matrices that extends the optimization result of Achlioptas and Naor that was central to results on chromatic numbers of unoriented random graphs.
One of the central objects of interest in additive combinatorics is the sumset $A+B= {a+b:a \in A, b \in B}$ of two sets $A,B$ of integers. Our main theorem, which improves results of Green and Morris, and of Mazur, implies that the following holds for every fixed $\lambda > 2$ and every $k>(\log n)^4$: if $\omega$ goes to infinity as $n$ goes to infinity (arbitrarily slowly), then almost all sets $A \subseteq [n]$ with $|A| = k$ and $ |A + A| < \lambda k$ are contained in an arithmetic progression of length $\lambda k/2 + \omega$. This is joint work with Marcelo Campos, Mauricio Collares, Rob Morris and Victor Souza.
In classical homotopy theory, two spaces are considered homotopy equivalent if one space can be continuously deformed into the other. This theory, however, does not respect the discrete nature of graphs. For this reason, a discrete homotopy theory that recognizes the difference between the vertices and edges of a graph was invented. This theory is called A-homotopy theory in honor of Ron Aktin, who created the foundations of this theory in Q-analysis in the 1970s. A-homotopy theory allows us to compare graphs and to compute invariants for graphs. The intended use of these invariants is to find areas of low connectivity in a large network where information might be missing or where the network might be made more efficient.
In algebraic topology, each space $X$ has associated spaces $\widetilde{X}$ and continous maps $p: \widetilde{X} \to X$, and each pair together $(\widetilde{X}, p)$ is called a covering space of $X$. Under certain conditions, a space has a covering space with special properties, called a universal cover. Among other things, universal covers allow us to factor maps between topological spaces, which can be quite useful. In this talk, I will give a brief introduction to A-homotopy theory and discuss the universal covers I developed for graphs with no 3 or 4-cycles as well as the covering graphs obtained from quotienting these universal covers. I will end by mentioning some of the useful properties of these universal covers.