Schedule for: 24w5298 - Movement and Symmetry in Graphs

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Informal Meet & Greet at the Professional Development Centre BIRS' Lounge

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

A brief introduction to BIRS with important logistical information, technology instruction, and opportunity for participants to ask questions.

Inverse Eigenvalue problems are an important area both linear algebra and related applied areas. Within the backdrop of graph theory, inverse eigenvalue problems have emerged as a key driver for many research problems with implications to both graph theory and matrix theory. This field is rich in history and continues to spawn several contemporary lines of inquiry recently. Under this umbrella we are proposing some problems that will hopefully appeal to researchers in both linear algebra and graph theory, along with those researchers that are more interested in possible related applications. These problems include: variations of zero forcing and their connections to graph searching; studies on the nullity of both the adjacency and generalized adjacency matrices of graphs; ordered multiplicity lists for generalized Laplacian matrices, characterizing the family of graphs for which the zero forcing number equals the path covering number over all induced subgraphs, the cardinality of the union of the spectra of the leading principal submatrices of a generalized adjacency matrix (principal spectra), and the number of distinct eigenvalues of the generalized Laplacian matrices.

A family of $r$ distinct sets $\{A_1,\ldots, A_r\}$ is an $r$-sunflower if for all $1 \le i < j\le r$ and $1 \le i' < j'\le r$, we have $A_i\cap A_j = A_{i'}\cap A_{j'}$. Erd\H{o}s and Rado conjectured in 1960 that every family $\mathcal{H}$ of $\ell$-element sets of size at least $K(r)^\ell$ contains an $r$-sunflower, where $K(r)$ is some function that depends only on $r$. We prove that if $\mathcal{H}$ is a family of $\ell$-element sets of VC-dimension at most $d$ and $|\mathcal H| > (C r(\log d+\log^\ast\ell))^\ell$ for some absolute constant $C > 0$, then $\mathcal{H}$ contains an $r$-sunflower. This improves a recent result of Fox, Pach, and Suk. When $d=1$, we obtain a sharp bound, namely that $|\mathcal H| > (r-1)^\ell$ is sufficient. Along the way, we establish a strengthening of the Kahn--Kalai conjecture for set families of bounded VC-dimension, which is of independent interest. It is joint work with {Anton Bernshteyn, Michelle Delcourt, Asaf Ferber, and Huy Tuan Pham.

The chromatic number of a graph is the minimum number of colors required so that each vertex can be assigned a color such that adjacent vertices receive different colors. The extremal values of the chromatic number, 1 and $n$ for an $n$-vertex graph, are easily achievable. In 1956, Nordhaus and Gaddum posed and answered a more interesting question: which graph and its complement maximize or minimize the sum or product of their chromatic numbers? Their work initiated a variety of question we now call Nordhaus-Gaddum problems: given some graph invariant $f$, which graphs are extremal for $f(G) + f(\overline{G})$ or $f(G)f(\overline{G})$? These questions have been asked for many flavors of chromatic number, domination number, eccentricity, connectivity, and more.

Recently, several investigators have looked at Nordhaus-Gaddum problems involving enumerative invariants, which is to say invariants counting the number of occurrences of some phenomenon in the graph, such as independent sets or dominating sets. We'll look at a few instances of this new type of problem, including an especially intriguing open problem.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Meet in foyer of TCPL to participate in the BIRS group photo. The photograph will be taken outdoors, so dress appropriately for the weather. Please don't be late, or you might not be in the official group photo!

We give a gentle introduction to the theory of characteristic polynomials of graphs, with an overview of the various graph objects that are enumerated by the characteristic polynomial. Topic will include the Harary-Sachs formula, walk-generating functions and the implications for the eigenvectors of a graph.

Given a finite transitive group $G\leq \operatorname{Sym}(\Omega)$, a set $\mathcal{F}\subset G$ is intersecting if, for any $g,h\in G$, there exists $\omega\in \Omega$ such that $\omega^g = \omega^h$. The intersection density $\rho(G)$ is the maximum ratio of $\frac{|\mathcal{F}|}{|G_\omega|}$, where $\mathcal{F}$ runs through all intersecting sets of $G$ and $G_\omega$ is the stabilizer of $\omega\in \Omega$ in $G$.

The problem of finding the intersection density of a finite transitive group $G\leq \operatorname{Sym}(\Omega)$ is equivalent to finding the size of the largest cocliques in the Cayley graph $\Gamma_G := \operatorname{Cay}(G,D_G)$, where $D_G$ is the set of all derangements of $G$. The graph $\Gamma_G$ is the so-called derangement graph} of $G$.

In [Meagher, Razafimahatratra and Spiga. On triangles in derangement graphs.J. Combin. Ser. A, 180, 2021], it was proved that if $G\leq \operatorname{Sym}(\Omega)$ is a transitive group with $|\Omega|\geq 3$, then $\rho(G)\leq \frac{|\Omega|}{3}$. This upper bound is sharp since it is attained by the groups:
TransitiveGroup(6,4)
TransitiveGroup(18,142)
TransitiveGroup(30,126), and
TransitiveGroup(30,233).
In particular, the group TransitiveGroup(6,4) is permutation equivalent to $\operatorname{Alt}(4)$ acting on the $2$-subsets of $\{1,2,3,4\}$, which is the smallest transitive group with intersection density larger than $1$. The derangement graphs of the transitive groups in (1)-(4) are all complete tripartite. Moreover, if $G$ is one of the groups in (1)-(4), then there exists a complete block system or a system of imprimitivity $\mathcal{B}$ of $G$ such that the induced action $\overline{G}$ of $G$ on $\mathcal{B}$ is permutation equivalent to TransitiveGroup(6,4).

The aim of this project is to answer the following questions and problems.
Problem: Find more examples of transitive groups whose derangement graphs are complete tripartite.
Question: If $\rho(G) = \frac{|\Omega|}{3}$, then is $\Gamma_G$ always complete tripartite?
Question: If $G\leq \operatorname{Sym}(\Omega)$ is transitive such that $\Gamma_G$ is complete tripartite, does $G$ always ``factor through'' TransitiveGroup(6,4)?

In [Fusari, Previtali, and Spiga. Cliques in derangement graphs for innately transitive groups. Journal of Group Theory, 2024], it was shown that if $G\leq \operatorname{Sym}(\Omega)$ is innately transitive (i.e., $G$ admits a transitive minimal normal subgroup) with $|\Omega|\geq 2$ and $\frac{|\Omega|}{4}< \rho(G) \leq \frac{|\Omega|}{3},$ then $|\Omega| = 3$. It is interesting to ask how this result generalizes to transitive groups, in general.

Question: Is there a transitive group $G\leq \operatorname{Sym}(\Omega)$ such that $\frac{|\Omega|}{4}< \rho(G) < \frac{|\Omega|}{3}$?

This talk will serve as an introduction to a later problem session. The problem we have in mind is to find constructions for locally finite graphs having eigenvectors of finite support, especially for "very symmetric" graphs, and over finite fields. We will give a bit of basic background, show some very basic constructions giving "somewhat symmetric" examples and also some obstructions ruling out some potential examples. We will also briefly explain the motivation.

Abstract A We discuss a discrete-time, dynamic process in which the goal is to maintain a dominating set in a graph over an infinite sequence of time steps. At each time step, some or all vertices in the current dominating set are replaced by neighbours in such a way that the reconfigured set is dominating and contains a specified vertex. The minimum number of vertices which allow for a dominating set to be dynamically maintained “forever” is the {\it eternal domination number} of the graph. After introducing the process and some fundamental results, we turn our attention to some directions for future research. Questions involving Cayley graphs, fractional solutions, different reconfiguration models, and dynamically maintaining different types of dominating sets will be raised. Abstract B While most introductions to eternal domination began in one's early youth with plans to take over the world, this talk will focus on Gary's personal journey to rule over his department and research colleagues. He will show how this can be modelled with graphs, which are homomorphic to most tyrants' plans to rule the world. For the more timid, this talk will also include a summary of plain old domination, with applications to getting free beer and forcing someone else to do your marking. For the podcast fans in the audience, this talk will also include tips on how to boost your listener numbers with broadcast domination. This talk may also include pursuit-evasion games, with a practical component that includes moderate to vigorous interaction with park officials (please bring appropriate footwear). (This abstract was entirely written by Karen Meagher, with no input from Gary at all.)

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Christopher Duffy: Distance 2 Convexity in Oriented Graphs

In the early 1970s Erdős et. al defined a notion of convexity for tournaments. One can extend this notion to all oriented graphs and arrive at a bootstrap percolation process where a vertex is turned on when at least one out-neighbour and one in-neighbour is turned on. In the early 2000’s Smolíková used this notion of convexity to prove a series of unexpected results about the oriented chromatic number for some families of oriented graphs. In this lightning talk, we introduce this notion of convexity, provide a few interesting examples, discuss some open problems in this area and consider why a good place to look for preliminary results would be arc-transitive directed graphs.

Peter Dukes: Balancing graphs, matrices, and polynomials

Given a polynomial $f(x_1,\dots,x_n)$ with integer coefficients, its balancing index is the least positive sum of coefficients in any linear combination of `permuted copies’ $f(x_{\sigma(1)},\dots,f_{\sigma(n)})$, $\sigma \in S_n$, which equals a symmetric polynomial. For instance, $f(x,y)=x^2+xy$ is not symmetric, but $f(x,y)+f(y,x)$ is symmetric, so we say the balancing index of $f$ equals $2$. Graphs (including digraphs and multigraphs), and integer matrices more generally, can be studied as special cases. In this short talk, I’ll summarize what is presently known and unknown about the balancing index.

Bobby Miraftab: Locally finite graphs with eigenvectors of finite support

In this brief talk, we’ll highlight some key ideas about locally finite graphs and their eigenvectors with finite support over finite fields, particularly in the context of symmetric graphs. We’re interested in constructing such graphs while addressing obstructions that arise in some cases.

JD Nir: The Second Common Neighbourhood Conjecture

The Second Common Neighbourhood Conjecture is a question about the structure of shared neighbours in a graph. It requires only a basic understanding of graph theory to state, but, if true, immediately improves the best known bound of an Enumerative Nordhaus-Gaddum problem counting the number of dominating sets in a graph and its complement.

Gary MacGillivray : The Greatest Short Talk of all Time

Gary will introduce an open problem that will both amaze you and affirm your decision to become a mathematician. A solution would be so powerful a result that it would lead to successful NSERC grant applications, plenty of exercise, and a healthy lunch every day. I would advise against missing this. (This abstract was written by Karen with Gary's knowledge and permission)

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

Recall that Cayley graphs of groups are always vertex-transitive but they are not necessarily edge-transitive. On the other hand, Cayley graphs of semigroups are neither necessarily vertex-transitive nor necessarily edge-transitive. Studying symmetric properties of Cayley graphs of groups and Cayley graphs of semigroups yields to the study of automorphism groups of Cayley graphs and determining their well-behaviour subgroups. In fact, by knowing these subgroups and their transitive actions on edges (vertices), we are able to present stronger symmetric properties (e.g. normal edge-transitive or color vertex-transitive) and determine them in proper families of groups or semigroups. In the first part of the talk, we will discuss these topics and their related problems.

In the next part, after discussing about the interactions between graph theoretical properties and algebraic properties of Cayley graphs, we show that symmetric properties of Cayley graphs of groups (semigroups) yield to special algebraic structures (e.g subgroups, factorizations or subfactorizations) which enable us to present new families of Cayley graphs with symmetric properties.

Cayley graphs are an important notion in algebraic graph theory as they connect the structures of groups and graphs. The concept of Cayley incidence graphs was first introduced by Evra et al in 2023 (referred to as Cayley bigraphs). They are bipartite, biregular graphs arising from Cayley graphs and in this talk we will explore their properties and connections with other algebraic structures. This is joint work with Alexey Gordeev, Sabrina Lato, Tovohery Randrianarisoa and Joannes Vermant.

A vertex in a graph is said to be sedentary if a quantum state assigned on that vertex tends to stay on that vertex. In this talk, we survey known results about vertex sedentariness, present new constructions, and discuss its connections to other types of state transfer. If time permits, then we also discuss open problems.

Coined quantum walks are motivated by quantum search algorithms. In this talk, I will discuss how different coins translate into different properties of the graph, and use them to construct examples of quantum walks that exhibit desired quantum phenomena.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

The classical Erdős-Ko-Rado (EKR) theorem and some of its variants can be viewed as characterizations of maximum independent sets of unions of graphs in some commutative Schurian (Orbital) schemes. For example, the classical EKR theorem characterizes independent sets of the Kneser graph, which is graph in the Johnson Scheme. Some other EKR-type results on vertices of Schurian schemes include the EKR theorem on subspaces and the EKR theorem on perfect matchings in a complete graph. Taking inspiration from algebraic proofs of the above-mentioned classical results, we attempt to identify Schurian schemes that are amenable to these algebraic methods and obtain some new EKR-type results in other domains.

The $Q$-polynomial property is an algebraic property of distance-regular graphs, that was introduced by Delsarte in his seminal work on association schemes and coding theory.

In 2023, Paul Terwilliger generalized the $Q$-polynomial property to graphs that are not necessarily distance regular. In [J.~Combin.~Theory Ser.~A, 205:105872, 2024], it was shown that the Hasse diagrams of the so-called attenuated space posets, which can be viewed as the $q$-analogs of Hamming posets, are $Q$-polynomial. However, the Hasse diagrams of Hamming posets were not studied in the context of the $Q$-polynomial property. Motivated by this, I will show that these are also $Q$-polynomial.

Let $G_n$ as the smallest integer such that for any finite family $\mathcal{F}$ of pairwise intersecting closed balls in $\mathbb{R}^n$ there exists a piercing set (a transversal of $\mathcal{F}$) of cardinality $G_n$. Gallai raised a question of determining $G_2$, which was shown to be $4$ by Danzer. However, for $n\geq 3$, the exact values of $G_n$ are unknown. In this talk I will prove new bounds $$\left(\frac{2}{\sqrt{3}}+o(1)\right)^{n}\leq G_n\leq \left(\sqrt{\frac{3}{2}}+o(1)\right)^n.$$

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Francis Clavette, Mahsa Shirazi (anyone is free to offer a lightning talk in this time! It just has to math and short!)

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

A Cayley graph whose group of symmetries is as small as its underlying group is called a graphical regular representation (GRR for short) of the group. In this talk, we study the existence of cubic GRRs of some families of classical groups and, based on some previously known results, confirm that almost every finite non-abelian simple group is the symmetry group of a certain cubic Cayley graph.

We study simplicial complexes (hypergraphs closed under taking subsets) that are the intersection of a given number $k$ of matroids. We prove bounds on their chromatic numbers (the minimum number of edges required to cover the ground set) and their list chromatic numbers. Settling a conjecture of Kiraly and Berczi--Schwarcz--Yamaguchi, we prove that the list chromatic number is at most $k$ times the chromatic number. The tools used are in part topological.

The talk is based on works joint with Ron Aharoni, Eli Berger, and Daniel Kotlar. In this talk, there is no assumption about background knowledge of matroid theory or algebraic topology.

A generalized Paley graph is a Cayley graph defined over a finite field with the connection set being a multiplicative subgroup of the field. Little is known about the structure of the large cliques in generalized Paley graphs of square order. In this talk, I will report some partial progress towards proving possible analogues of the celebrated Chvátal's conjecture, Erdős-Ko-Rado theorem, and Hilton-Milner theorem in this generalized Paley graph setting and the more general cyclotomic graph setting. Joint work with Shamil Asgarli and Greg Martin.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

In recent years, I have been working with students on cataloguing distance-regular graphs with primitive automorphism groups, using the libraries of primitive groups in the GAP computer algebra system. In this talk, I will discuss some of the more curious observations we made, and present some open questions that have arisen from this work. These in turn relate to topics such as Cayley graphs, association schemes and finite geometries, as well as permutation groups.

The study of combinatorial designs has a rich history spanning nearly two centuries. In a recent breakthrough, the notorious Existence Conjecture for Combinatorial Designs dating back to the 1800s was proved in full by Keevash via the method of randomized algebraic constructions. Subsequently Glock, Kuhn, Lo, and Osthus provided an alternate purely combinatorial proof of the Existence Conjecture via the method of iterative absorption. We introduce a novel method of “refined absorption” for designs; in this talk, as our first application of the method we provide a new alternate proof of the Existence Conjecture. If time permits, we will discuss applications to high girth designs, thresholds for designs, and finding clique decompositions of random graphs and random regular graphs. Joint work with Luke Postle and Tom Kelly.

A classical question in extremal (hyper)graph theory asks for tight minimum degree conditions which force the existence of certain spanning structures in large graphs, generalising Dirac's theorem from 1952. One aspect of this concerns tiling graphs with identical vertex disjoint copies of a small subgraph. For example, asking for tight minimum codegree conditions in a k-uniform hypergraph which force a perfect matching (under the obvious additional necessary condition that the number of vertices is divisible by k). Whilst there has been a lot of interest in these types of tiling problem, still very few results are known. We share a new result in this area, which is joint work with Amarja Kathapurkar, Natasha Morrison and Richard Mycroft.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

The spread of influence is a major topic in network science, where contagion like COVID-19 spreads from vertex-to-vertex by prescribed rules. We consider a new such process called cooling, which spreads in graphs as slowly as possible. Cooling can be thought of as the dual to burning, which is a well-studied topic introduced a decade ago. We survey results on cooling, including bounds and exact values on graph families, and isoperimetric inequalities with applications to grids.

A directed graph is hamiltonian decomposable if it admits a decomposition into directed hamiltonian cycles. In this talk, we will consider the following conjecture which first appears in Alspach et al. (1987): given two hamiltonian decomposable directed graphs $G$ and $H$, the wreath (lexicographic) product of $G$ with $H$ is also hamiltonian decomposable. Ng (1998) affirmed this conjecture when $|V(G)|$ is odd and $|V(H)| > 2$. We will consider the case when $|V(G)|$ is even and affirm this conjecture when $|V(H)| > 3$ except when $|V(H)|$ is even, $G$ is a directed cycle, and $H$ admits a decomposition into an odd number of directed hamiltonian cycles.

Given a graph $H$, we say a graph $G$ is properly rainbow $H$-saturated if there is a proper edge-coloring of $G$ which contains no rainbow copy of $H$, but adding any edge to $G$ makes such an edge-coloring impossible. The proper rainbow saturation number is the minimum number of edges in an n-vertex properly rainbow $H$-saturated graph. In this talk, we discuss new bounds on the proper rainbow saturation number for odd cycles, paths, and cliques.

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

5-day workshop participants are welcome to use BIRS facilities (TCPL ) until 3 pm on Friday, although participants are still required to checkout of the guest rooms by 11AM.