# Schedule for: 23w5125 - Extremal Graphs arising from Designs and Configurations

Beginning on Sunday, May 14 and ending Friday May 19, 2023

All times in Banff, Alberta time, MDT (UTC-6).

Sunday, May 14 | |
---|---|

16:00 - 16:01 | Check-in begins (Juniper Front Desk) |

17:30 - 18:30 | Dinner Seating 1 (Juniper Bistro) |

18:30 - 19:30 | Dinner Seating 2 (Juniper Bistro) |

19:30 - 20:30 | Dinner Seating 3 (Juniper Bistro) |

Monday, May 15 | |
---|---|

07:30 - 08:30 | Breakfast Buffet (Juniper Bistro) |

09:00 - 09:10 | Introduction from BIRS Staff (Kiguli Room) |

09:30 - 10:00 |
Robert Jajcay: Advancing our understanding of cages through use of algebraic methods ↓ A $k$-regular graph of girth $g$ is is said to be a $(k,g)$-cage if its order $n(k,g)$ is the smallest among the orders of all $k$-regular graphs of girth $g$. The Cage Problem is the problem of finding cages and the corresponding values $n(k,g)$, for all parameter pairs $k$ and $g$. Cages are only known for very limited sets of parameter pairs, and progress in Cage Problem is unfortunately quite slow.
The aim of the presentation is to outline specific problems and questions concerning cages that appear to be particularly suitable for the use of algebraic methods. Notably, a significant proportion of the known cages exhibit a high level of symmetry; with many being vertex-transitive or even Cayley. This observation is the motivation behind restricting the general Cage Problem to the problem of finding smallest vertex-transitive graphs of given degree and girth. While focusing on vertex-transitive graphs may not necessarily directly lead to finding new cages, understanding the structure of small vertex-transitive graphs of given degree and girth adds to our understanding of the general Cage Problem and may even produce graphs that could possibly be altered to become cages (by giving up some of their symmetry properties).
In our talk, we will discuss connections between general and vertex-transitive
graphs of given degree and girth and the way progress in understanding either of these two classes may lead to progress in the other. (Kiguli Room) |

10:00 - 10:25 |
Gabriela Araujo: Bipartite biregular cages: block designs and generalized polygons ↓ A {\em bipartite biregular} $(m,n;g)$-graph $\Gamma$ is a bipartite graph
of even girth $g$ having the degree set $\{m,n\}$ and satisfying the additional property that
the vertices in the same partite set have the same degree.
The $(m,n;g)$-{\em bipartite biregular cages}, was introduced in 2019 by Filipovski, Ramos-Rivera, and Jajcay, they are bipartite biregular $(m,n;g)$-graphs
of minimum order. The authors calculate lower bounds on the orders of bipartite biregular $(m,n;g)$-graphs, and call the graphs that attain these bounds {\em bipartite biregular Moore cages}.
We improve the lower bounds obtained in the above paper. Furthermore, in parallel with the well-known classical results relating the existence of $k$-regular Moore graphs of even girths $g = 6,8 $ and $12$ to the existence of projective planes, generalized quadrangles, and generalized hexagons,
we prove that the existence of an $S(2,k,v)$-Steiner system yields the existence of a bipartite biregular
$(k,\frac{v-1}{k-1};6)$-cage, and, vice versa, the existence of a bipartite biregular $(k,n;6)$-cage whose
order is equal to one of our lower bounds yields the existence of an $S(2,k,1+n(k-1))$-Steiner system. Moreover, in the special case of Steiner triple systems,
we completely solve the problem of determining the orders of $(3,n;6)$-bipartite biregular cages for all integers $n\geq 4$.
Considering girths higher than $6$, we relate the existence of
generalized polygons (quadrangles, hexagons and octagons) to the existence of $(n+1,n^2+1;8)$-, $(n^2+1,n^3+1;8)$-, $(n,n+2;8)$-, $(n+1,n^3+1;12)$- and $(n+1,n^2+1;16)$-bipartite biregular cages, respectively. Using this connection, we also derive improved upper bounds for the orders of other classes of bipartite biregular cages of girths $8$, $12$, and $14$. (Kiguli Room) |

10:25 - 10:50 |
Gyorgy Kiss: Girth-(bi)regular graphs and finite geometries ↓ Two new classes of graph regularities have been introduced recently.
Let $\Gamma$ denote a simple, connected, finite graph. For an edge e of $\Gamma$ let $n(e)$ denote
the number of girth cycles containing $e$. For a vertex $v$ of $\Gamma$ let $\{e_1, e_2, \ldots , e_k\}$
be the set of edges incident to $v$ ordered such that $n(e_1) \le n(e_2) \le \ldots\le n(e_k)$.
Then $ (n(e_1), n(e_2),\ldots, n(e_k))$ is called the signature of $v$. The graph $\Gamma$ is said
to be girth-(bi)regular if (it is bipartite, and) all of its vertices (belonging to the
same bipartition) have the same signature.
We show that girth-(bi)regular graphs are related to (biregular) cages, finite
projective and affine spaces and generalized polygons. We also provide a short,
concise introduction to these geometric objects. (Kiguli Room) |

10:50 - 11:20 | Coffee break (Kiguli Room) |

11:20 - 11:45 |
Christian Rubio-Montiel: Christian Rubio: On the harmonious chromatic number of Levi graphs ↓ The \textit{harmonious chromatic number} of a graph $G$ is the minimum number of colors that can be assigned to the vertices of $G$ in a proper way such that any two distinct edges have different color pairs. Therefore, if $G$ has order $v$ and diameter at most two, then $h(G)=v$. Therefore, if $G$ is the Levi graph of a linear space $\mathcal{S}$ of $n$ points, then $h(G)\geq n$, since every two points in $\mathcal{S}$ determine a line. In [1] is proved that:
1) If $G$ is the Levi graph of the finite projective plane of odd order $q$, then \[q^2+q+ 1\leq h(G) \leq q^2+q+ 2;\]
2) If $G$ is the Levi graph of the complete graph $K_n$, then \[\frac{3}{2}n\leq h(G) \leq \frac{5}{3}n +\theta(1).\]
A possible problem is to estimate the harmonious chromatic number of the $(q+1,8)$-cages (the Levi graphs of generalized quadrangles).}
References
[1] Araujo-Pardo, G., Montellano-Ballesteros, J. J., Olsen, M., and Rubio-Montiel, C. \textit{On the harmonious chromatic number of graphs}. arXiv preprint arXiv:2206.04822, 2022. (Kiguli Room) |

11:45 - 12:10 |
Mika Olsen: Using geometric properties to color Levi graphs of generalized quadrangles Q(4, q) ↓ Geometric properties can be used to determine chromatic classes of coloring
and chromatic classes can determine geometric properties. Packing
colorings and $L(h, k)$ colorings are somehow related. The packing chromatic
number, $χ_ρ(G)$, of a graph $G$ is the minimum number of colors (positive integer)
of a vertex coloring of $G$ such that vertices of color $i$ are at distance
at least $i + 1$. The $L(h, k)$ chromatic number, $λ_{h,k}(G)$, of a graph $G$ is the
minimum number of colors (non-negative integers) of a vertex coloring of $G$
such that the colors of adjacent vertices must differ in at least $h$ and the
colors of vertices of distance $2$ must differ at least $k$.
In [1] it was proved that:
• Let $q$ be an odd prime power. If $G$ is the Levi graph of a $Q(4, q)$, then
$(q^2 + 1)(q − 1) + 3 ≤ χ_ρ(G) ≤ (q^2 + 1)(q − 1) + 4.$
• A $Q(4, q)$ contains two disjoint ovoids or two disjoint spreads if and
only if $χ_ρ(G) = (q^2 + 1)(q − 1) + 3$, where G is its Levi graph.
In [2] it was proved that:
• The points of a $Q(4, q)$ have a partition into a daisy structure and the
lines of $Q(4, q)$ have a partition into a sunflower structure.
• If $G$ is the Levi graph of a $Q(4, q)$ and $q ≥ 5$ is a prime number then,
$(2q + 2)k ≤ λ{h,k}(G) ≤ (q + 1)2k/2 + h.$
A possible problem is to extend the results for Levy graphs of $Q(4, q)$ to Levi
graphs of generalized quadrangles which are not $Q(4, q)$, another possible
problem es improve the bounds for the packing chromatic number of $(q +
1, 12)$-cages or improve the bounds of $L(h, k)$ chromatic number of Levi
graphs of $Q(4, q)$.
References
[1] J. Fresán-Figueroa, D. González-Moreno, M. Olsen, On the packing chromatic
number of Moore graphs, Discrete App. Math. 289 (2021) 185–193.
[2] J. Fresán-Figueroa, D. González-Moreno, M. Olsen, Special structures in
$Q(4, q)$, projective planes and its application in $L(h, k)$ colorings of their
Moore Graphs, Discrete App. Math. 331 (2023) 31–37. (Kiguli Room) |

12:00 - 13:30 | Lunch Buffet (Juniper Bistro) |

13:30 - 13:45 | Group Photo (Meet at Bistro Patio (Weather Permitting)) |

14:00 - 14:30 |
Grahame Erskine: Totally regular mixed graphs in the diameter, girth and geodecity problems ↓ Mixed graphs can be viewed as generalisations of both undirected graphs and
digraphs. The problems of the largest (totally regular) mixed graph of given degree and
diameter and the smallest such graph of given degree and girth (or geodecity) share some
features in common with those for undirected and directed graphs. However, the mixed
graph problems have certain unique aspects. We will outline some results from the last few
years, and note some open problems and possible lines of attack. (Kiguli Room) |

14:30 - 14:55 |
Geoffrey Exoo: Negative Results on Cages and Degree Diameter Graphs ↓ Some problems on cages and degree diameter graphs are surveyed. The focus is on
problems where a computational approach to the problem has fallen short, and for
which a little non-computer based analysis might be enough to make the computations
feasible. (Kiguli Room) |

14:55 - 15:20 |
Nacho López: Measuring the closeness to mixed Moore graphs ↓ Moore graphs are extremal graphs that appear as solutions of a combinatorial problem
known as the degree/diameter problem. This problem is key to the design of topologies for
interconnection networks and other questions related to data structures and cryptographic
protocols. Besides, the relationship between vertices or nodes in communication networks
can be undirected or directed depending on whether the communication between nodes
is two-way or only one-way. Mixed graphs arise in this case and it is therefore natural
to consider network topologies based on mixed graphs, and investigate the corresponding
degree/diameter problem and their solutions (mixed Moore graphs). In this talk we
present mixed radial Moore graphs as an approximation of mixed Moore graphs and
we describe how to measure they closeness to the properties that a mixed Moore graph
should have.
References
[1] C. Capdevila, J. Conde, G. Exoo, J. Gimbert, N. Lopez, Ranking measures for radially
Moore graphs, Networks, 56(4): (2010) 255{262.
[2] C. Dalfo, M. A. Fiol, and N. Lopez, Sequence mixed graphs, Discrete Applied Math. 219
(2017) 110{116.
[3] C. Dalfo, M. A. Fiol, and N. Lopez, An improved upper bound for the order of mixed
graphs, Discrete Math. 341 (2018), no. 10, 2872{2877.
[4] G. Exoo, J. Gimbert, N. Lopez, J. Gomez, Radial moore graphs of radius three, Discrete
Applied Math., 160(10), (2012), 1507{1512.
[5] M. Miller and J. Siran, Moore graphs and beyond: A survey of the degree/diameter
problem, Electron. J. Combin. 20(2) (2013) #DS14v2.
[6] M. H. Nguyen, M. Miller, and J. Gimbert, On mixed Moore graphs, Discrete Math. 307
(2007) 964{970. (Kiguli Room) |

15:20 - 16:00 | Coffee break (Kiguli Room) |

16:00 - 16:25 |
Linda Lesniak: On the existence of $(r,g,\chi)$-cages ↓ For integers $r \ge 2$ and $g \ge 3,$ an $(r,g)$-\emph{graph} is and $r$-regular graph with girth $g$, and an $(r,g)$-\emph{cage}
is an $(r,g)$-graph of minimum order. It is conjectured that all $(r,g)$-cages with even $g$ are bipartite, that is, have chromatic number $2$. Here we introduce the idea of an $(r,g, \chi)$-\emph{graph}, an $r$-regular graph with girth $g$ and chromatic number $\chi$. We investigate the existence of such graphs and study in detail the $(r,3,3)$-graphs of minimum order. We also consider $(r,g, \chi)$-graphs for which there is a $\chi$-coloring where the color classes differ by at most $1$. (Kiguli Room) |

16:25 - 16:50 |
Marco Buratti: An overview of my dearest differences ↓ I will try to give an overview of the main constructions for
classic designs and graph decompositions that my collaborators and I
obtained over the years with the so-called {\it method of differences} and its many variants. (Kiguli Room) |

17:30 - 18:30 | Dinner Seating 1 (Juniper Bistro) |

18:30 - 19:30 | Dinner Seating 2 (Juniper Bistro) |

19:30 - 20:30 | Dinner Seating 3 (Juniper Bistro) |

Tuesday, May 16 | |
---|---|

07:30 - 08:30 | Breakfast Buffet (Juniper Bistro) |

09:30 - 12:00 |
Work in groups ↓ Available rooms for group work:
Keguli Room (Main Lecture room)
Vermillion Room (Buffet room)
3rd floor suite (Follow stairs outside of the bistro entrance to top floor)
Cabin (Across the parking lot - check with organizer for Cabin number) (Other (See Description)) |

10:30 - 11:00 | Coffee Break (Kiguli Room) |

12:00 - 13:30 | Lunch Buffet (Juniper Bistro) |

14:00 - 17:30 |
Work in groups ↓ Available rooms for group work:
Keguli Room (Main Lecture room)
Vermillion Room (Buffet room)
3rd floor suite (Follow stairs outside of the bistro entrance to top floor)
Cabin (Across the parking lot - check with organizer for Cabin number) (Other (See Description)) |

15:00 - 15:30 | Coffee Break (Kiguli Room) |

17:30 - 18:30 | Dinner Seating 1 (Juniper Bistro) |

18:30 - 19:30 | Dinner Seating 2 (Juniper Bistro) |

19:30 - 20:30 | Dinner Seating 3 (Juniper Bistro) |

Wednesday, May 17 | |
---|---|

07:30 - 08:30 | Breakfast Buffet (Juniper Bistro) |

09:00 - 09:30 |
Cristina Dalfó: On the spectra of token graphs of a cycle - Part I ↓ The $k$-token graph $F_k(G)$ of a graph $G$ is the graph whose vertices are the $k$-subsets of vertices from $G$, two of which being adjacent whenever their symmetric difference is a pair of adjacent vertices in $G$.
In this talk, through lift graphs and voltage assignments, we first show the spectrum of a $k$-token graph of a cycle $C_n$ for some $n$. Since this technique does not give the results for all possible $n$, we introduce a new method that we called over-lifts. This method allows us to present the spectra of any $k$-token graph of any cycle $C_n$. (Other (See Description)) |

09:30 - 10:00 |
Miguel Àngel Fiol: On the spectra of token graphs of a cycle - Part II ↓ The $k$-token graph $F_k(G)$ of a graph $G$ is the graph whose vertices are the $k$-subsets of vertices from $G$, two of which being adjacent whenever their symmetric difference is a pair of adjacent vertices in $G$.
In this talk, through lift graphs and voltage assignments, we first show the spectrum of a $k$-token graph of a cycle $C_n$ for some $n$. Since this technique does not give the results for all possible $n$, we introduce a new method that we called over-lifts. This method allows us to present the spectra of any $k$-token graph of any cycle $C_n$. (Other (See Description)) |

10:00 - 10:30 |
Mónica Reyes: On the spectra of token graphs of a cycle - Part III ↓ The $k$-token graph $F_k(G)$ of a graph $G$ is the graph whose vertices are the $k$-subsets of vertices from $G$, two of which being adjacent whenever their symmetric difference is a pair of adjacent vertices in $G$.
In this talk, through lift graphs and voltage assignments, we first show the spectrum of a $k$-token graph of a cycle $C_n$ for some $n$. Since this technique does not give the results for all possible $n$, we introduce a new method that we called over-lifts. This method allows us to present the spectra of any $k$-token graph of any cycle $C_n$. (Other (See Description)) |

10:30 - 11:00 | Coffee Break (Kiguli Room) |

11:00 - 11:25 |
Dimitri Leemans: Edge-girth-regular graphs arising from biaffine planes and Suzuki groups ↓ An edge-girth-regular graph $egr(v,k,g,\lambda)$, is a $k$-regular graph of order $v$, girth
$g$ and with the property that each of its edges is contained in exactly $\lambda$ distinct
$g$-cycles. An $egr(v,k,g,\lambda)$ is called extremal for the triple $(k,g,\lambda)$ if $v$ is
the smallest order of any $egr(v,k,g,\lambda)$.
In this talk, I will show two families of edge-girth-regular graphs. The first one is a family of
extremal $egr(2q^2,q,6,(q-1)^2(q-2))$ for any prime power $q\geq 3$. The second one is a
family of $egr(q(q^2+1),q,5,\lambda)$ for $\lambda\geq q-1$ and $q\geq 8$ an odd power of
$2$. In particular, if $q=8$ we have that $\lambda=q-1$. (Other (See Description)) |

11:25 - 12:15 | Intermediate reports (Other (See Description)) |

12:00 - 13:30 | Lunch Buffet (Juniper Bistro) |

13:30 - 17:30 | Free Afternoon - Shuttle Service to Banff town (Banff National Park) |

17:30 - 18:30 | Dinner Seating 1 (Juniper Bistro) |

18:30 - 19:30 | Dinner Seating 2 (Juniper Bistro) |

19:30 - 20:30 | Dinner Seating 3 (Juniper Bistro) |

Thursday, May 18 | |
---|---|

07:30 - 08:30 | Breakfast Buffet (Juniper Bistro) |

09:30 - 12:00 |
Work in groups ↓ Available rooms for group work:
Keguli Room (Main Lecture room)
Vermillion Room (Buffet room)
3rd floor suite (Follow stairs outside of the bistro entrance to top floor)
Cabin (Across the parking lot - check with organizer for Cabin number) (Other (See Description)) |

10:30 - 11:00 | Coffee Break (Kiguli Room) |

12:00 - 13:30 | Lunch Buffet (Juniper Bistro) |

14:00 - 17:30 |
Work in groups ↓ |

15:00 - 15:30 | Coffee Break (Kiguli Room) |

17:30 - 18:30 | Dinner Seating 1 (Juniper Bistro) |

18:30 - 19:30 | Dinner Seating 2 (Juniper Bistro) |

19:30 - 20:30 | Dinner Seating 3 (Juniper Bistro) |

Friday, May 19 | |
---|---|

07:30 - 08:30 | Breakfast Buffet (Juniper Bistro) |

09:30 - 12:00 | Final reports (Other (See Description)) |

10:00 - 10:30 | Coffee Break (Kiguli Room) |

12:00 - 13:30 | Lunch Buffet (Juniper Bistro) |