Difference between revisions of "Mirka Miller's Combinatorics Webinar Series"
From Combinatorics Wiki
(→Talk 33: James Tuite (Open University, UK)) |
|||
(9 intermediate revisions by 2 users not shown) | |||
Line 5: | Line 5: | ||
<!--'''Meeting link:''' [https://meet.google.com/kgc-uwpc-ngp https://meet.google.com/kgc-uwpc-ngp]--> | <!--'''Meeting link:''' [https://meet.google.com/kgc-uwpc-ngp https://meet.google.com/kgc-uwpc-ngp]--> | ||
+ | '''Meeting link:''' [https://meet.google.com/kgc-uwpc-ngp https://meet.google.com/kgc-uwpc-ngp] | ||
− | ==Upcoming Talks== | + | ==Upcoming Talks: == |
+ | |||
+ | ===Banff designs: difference methods for coloring incidence graphs - Prof. Francesca Merola - Roma Tre University (Italy)=== | ||
+ | |||
+ | '''Date: Wednesday May 22nd 2024''' | ||
+ | |||
+ | '''Time: 17:00 (CEST)''' | ||
+ | |||
+ | '''Speaker: Prof. Francesca Merola''' | ||
+ | |||
+ | '''Title: Banff designs: difference methods for coloring incidence graphs''' | ||
+ | |||
+ | '''Abstract:''' A harmonious coloring of a graph is a proper vertex-coloring such that every pair of colors appears on at most one pair of adjacent vertices, and the harmonious chromatic number h(G) of a graph G is then the minimum number of colors needed for a harmonious coloring of G. It is easily seen that the harmonious chromatic number of the incidence graph of a 2-(v, k, λ)-design must be at least v, the number of points of the design. In this talk, I will present some applications of difference methods to study and construct Banff designs, that is designs having harmonious chromatic number of the incidence graph exactly equal to the lower bound v. (Joint work with Marco Buratti, Anamari Nakić, Christian Rubio-Montiel). | ||
+ | |||
+ | '''Link:''' [https://meet.google.com/kgc-uwpc-ngp https://meet.google.com/kgc-uwpc-ngp] | ||
+ | |||
==Previous Talks== | ==Previous Talks== | ||
Line 686: | Line 702: | ||
---- | ---- | ||
+ | |||
+ | |||
=== Talk 33: James Tuite (Open University, UK) === | === Talk 33: James Tuite (Open University, UK) === | ||
Line 708: | Line 726: | ||
'''Meeting link:''' [https://eu.bbcollab.com/guest/5dd6af40782341b8a4b56dd7d505a8f5 https://eu.bbcollab.com/guest/5dd6af40782341b8a4b56dd7d505a8f5] | '''Meeting link:''' [https://eu.bbcollab.com/guest/5dd6af40782341b8a4b56dd7d505a8f5 https://eu.bbcollab.com/guest/5dd6af40782341b8a4b56dd7d505a8f5] | ||
+ | |||
+ | '''Slides''': [https://drive.google.com/drive/folders/1h-72Zzto5PCmo1ThgZdzYUJlMseS_6XS https://drive.google.com/drive/folders/1h-72Zzto5PCmo1ThgZdzYUJlMseS_6XS] | ||
'''Video''': [https://drive.google.com/drive/folders/1hFfJqLIR4NEMd-4Wr8WOOkv4-jcjgJ5H https://drive.google.com/drive/folders/1hFfJqLIR4NEMd-4Wr8WOOkv4-jcjgJ5H] | '''Video''': [https://drive.google.com/drive/folders/1hFfJqLIR4NEMd-4Wr8WOOkv4-jcjgJ5H https://drive.google.com/drive/folders/1hFfJqLIR4NEMd-4Wr8WOOkv4-jcjgJ5H] | ||
+ | |||
+ | |||
---- | ---- | ||
Revision as of 06:48, 8 May 2024
Welcome to the home page for Mirka Miller's Combinatorics Webinar Series.
Meeting link: https://meet.google.com/kgc-uwpc-ngp
Contents
- 1 Upcoming Talks:
- 2 Previous Talks
- 2.1 Talk 1: Celebrating Mirka's life - Prof. Camino Balbuena
- 2.2 Talk 2: May there be many more repeats - Prof. Jozef Širáň
- 2.3 Talk 3: The Domination Blocking Game - Prof. Dominique Buset
- 2.4 Talk 4: The story about graphs CD(k,q) - Prof. Felix Lazebnik
- 2.5 Talk 5: A Journey with Antimagic Labeling - Prof. Kiki Ariyanti Sugeng
- 2.6 Talk 6: Biregular Cages - Prof. Robert Jajcay
- 2.7 Talk 7: Open problema in Distance-based Graph Labelings - Prof. Rinovia Simanjuntak
- 2.8 Talk 8: On the existence of almost Moore digraphs - Prof. Edy Tri Baskoro
- 2.9 Talk 9: Strong cliques in diamond-free graphs - Prof. Berenice Martinez Barahona
- 2.10 Talk 10: Perfect Matchings in Regular Graph with Given Connectivity - Prof. Yuqing Lin
- 2.11 Talk 11: Colorings of Moore graphs - Prof. Mika Olsen
- 2.12 Talk 12: Four families of polynomials in spectral graph theory - Prof. Miquel Àngel Fiol
- 2.13 Talk 13: Berge’s conjecture for cubic graphs with small colouring defect - Prof. Edita Máčajová
- 2.14 Talk 14: Measuring the closeness to Moore graphs - Prof. Nacho López
- 2.15 Talk 15: On mixed cages - Prof. Diego González
- 2.16 Talk 16: On weight-equitable partitions of graphs - Prof. Aida Abiad
- 2.17 Talk 17: Spectral Moore theorems for graphs and hypergraphs - Prof. Sebastian Cioaba
- 2.18 Talk 18: On hamiltonian paths of the complete graph with prescribed edge-lengths - Prof. Anita Pasotti
- 2.19 Talk 19: Mixed graphs with small excess - Prof. Grahame Erskine
- 2.20 Talk 20: Approaching the Moore bound in the degree-diameter problem by Cayley graphs - Prof. Jana Šiagiová
- 2.21 Talk 21: L(h,k)-colorings of some Moore graphs via some special structures - Prof. Julián Fresán
- 2.22 Talk 22: A variant of the algebraic connectivity and grid drawings of complete multipartite graphs - Prof. Clemens Huemer
- 2.23 Talk 23: Results on Problems I Learned About on the Mirka Miller Webinar - Prof. Geoffrey Exoo
- 2.24 Talk 24: On the spectra of token graphs of a cycle - Mónica Reyes, Prfo. Cristina Dalfó and Prof. Miquel Àngel Fiol
- 2.25 Talk 25: Biregular (and regular) planar cages - Natalia García-Colín
- 2.26 Talk 26: Regular graphs of given chromatic number of minimum order - Christian Rubio
- 2.27 Talk 27: New incidence geometries related to the classical generalized hexagons and triality - Klara Stokes
- 2.28 Talk 28: Heffter arrays: from the applications to a generalization - Tommaso Traetta
- 2.29 Talk 29: Properties of Villarceau Torus - Paul Manuel
- 2.30 Talk 30: Constructing small totally regular mixed graphs of given degrees and girth - Tatiana Jajcayová
- 2.31 Talk 31: Revisiting the Degree-Diameter Problem: A Six-Decade Perspective - Francesc Comellas
- 2.32 Talk 32: On the existence of (r, g, χ)-cages - Linda Lesniak
- 2.33 Talk 33: James Tuite (Open University, UK)
- 3 Mirka's Research and related works
- 4 Photos
- 5 Organisers
Upcoming Talks:
Banff designs: difference methods for coloring incidence graphs - Prof. Francesca Merola - Roma Tre University (Italy)
Date: Wednesday May 22nd 2024
Time: 17:00 (CEST)
Speaker: Prof. Francesca Merola
Title: Banff designs: difference methods for coloring incidence graphs
Abstract: A harmonious coloring of a graph is a proper vertex-coloring such that every pair of colors appears on at most one pair of adjacent vertices, and the harmonious chromatic number h(G) of a graph G is then the minimum number of colors needed for a harmonious coloring of G. It is easily seen that the harmonious chromatic number of the incidence graph of a 2-(v, k, λ)-design must be at least v, the number of points of the design. In this talk, I will present some applications of difference methods to study and construct Banff designs, that is designs having harmonious chromatic number of the incidence graph exactly equal to the lower bound v. (Joint work with Marco Buratti, Anamari Nakić, Christian Rubio-Montiel).
Link: https://meet.google.com/kgc-uwpc-ngp
Previous Talks
Talk 1: Celebrating Mirka's life - Prof. Camino Balbuena
Date: March 8 2021
Time 17:00 (CET)
Celebrating Mirka's life
Chair: Prof. Gabriela Araujo-Pardo
"Remembering Prof. Mirka Miller"
by Prof. Cristina Dalfó
Speaker: Prof. Camino Balbuena
Title: On the Moore cages with a prescribed girth pair
Abstract: https://drive.google.com/file/d/11r-TY8NswuKZkT7LOfkl-4yy1d72aF-w/view?usp=sharing
Slides: https://drive.google.com/file/d/1GkbwwNYSLBgRGjE8z7n1ckuXbXb6sRrN/view?usp=sharing
Video: https://drive.google.com/file/d/1DuWvsAsxMoIzCH4wr_hpGqUCx5uv89SU/view?usp=sharing {Chair: Prof. Gabriela Araujo-Pardo (minute 0:00-04:08) - "Remembering Prof. Mirka Miller" by Prof. Cristina Dalfó (minute 04:08-17:44) - Speaker: Prof. Camino Balbuena On the Moore cages with a prescribed girth pair (minute 17:44-end)}
Talk 2: May there be many more repeats - Prof. Jozef Širáň
Date: Wednesday April 14 2021
Time: 1000 Bratislava (0900 UK)
Speaker: Prof. Jozef Širáň
Title: May there be many more repeats
Abstract: This is my reminiscence on two mathematical aspects of my collaboration with Mirka Miller in the degree-diameter problem: the lifting technique in constructions of `large' examples and her method of repeats in non-existence proofs.
Video: https://drive.google.com/file/d/1Ss2xvDP9UAIebNUnIr2U6J01wixUJFkK/view?usp=sharing {Chair: Prof. Camino Balbuena (minute 0:00-02:26) - Speaker: Prof. Jozef Širáň May there be many more repeats (minute 02:26-end)}
Talk 3: The Domination Blocking Game - Prof. Dominique Buset
Date: Wednesday May 12 2021
Time: 11:00 (CET) - one hour later than the previous one
Speaker: Prof. Dominique Buset
Title: The Domination Blocking Game
Abstract: We introduce a new game on a simple, finite and undirected graph: “the domination tracking game”. Two players (the Dominator and the Enemy), each one playing alternatively, take a not occupied vertex on the graph. When the dominator (resp. the enemy) takes a vertex, he controls the vertex and all its neigbours (resp. just the vertex taken). The purpose of the game is for the dominator to control all the vertices, and for the enemy to avoid the dominator to win (i.e. to take one vertex and all his neighbours). We determine for some categories of graphs a winning strategy either for the Dominator or the Enemy. These situations, give a partition of those graphs into three classes. https://drive.google.com/file/d/1V8WY_qlqCDHdZLFsTokOQ-7t7KBtnqSG/view?usp=sharing
As part of the initiatives of Women in Mathematics Day
Video: https://drive.google.com/file/d/1HIv1fixjrWZfcRYHwN3QgntBKMoMK1Mt/view?usp=sharing
{Chair: Prof. Cristina Dalfó - Speaker: Prof. Dominique Buset The Domination Blocking Game }
Talk 4: The story about graphs CD(k,q) - Prof. Felix Lazebnik
Date: Wednesday June 16 2021
Time: 18:00 (CET)
Speaker: Prof. Felix Lazebnik
Title: The story about graphs CD(k,q)
Abstract: In this talk I will present the main ideas and history behind the construction of the family of graphs that is usually denoted by CD(k,q), where k is a positive integer, and q is a prime power. It is known that the girth of CD(k,q) (the length of its shortest cycle) is at least k+5, and these graphs provide the best known asymptotic lower bound for the greatest number of edges in graphs of a given order and given girth at least g, where g ≥ 5 and g distinct from 11, 12. We survey some old and new results, and mention several open questions related to these graphs or to similarly constructed graphs.
Slides: https://drive.google.com/file/d/13G9bVkwBEXgA6bkX4MJOgoAJsFRNorMs/view?usp=sharing
YouTube version of Cohen’s `Anthem’: https://youtu.be/c8-BT6y_wYg
Lev Arkad'evich Kaluznin (with M.H. Klin, G. Pöschel, V.I. Suschansky, V.A. Ustimenko, V.I. Vyshensky),
Applicandae Matematicae, 52:(1998) 5--18 MR 99m: 01091. https://drive.google.com/file/d/1Ak_MAzyE2FEW6kEflHi_1hDMghOiVp48/view?usp=sharing
General properties of some families of graphs defined by systems of equations. (joint work with A.J. Woldar),
Journal of Graph Theory, 38, (2001), 65--86. MR 2002k: 05108. https://drive.google.com/file/d/1vJCV9CXeOyfCoGp0Epmatw2n4BLu9be3/view?usp=sharing
Some Families of Graphs, Hypergraphs and Digraphs Defined by Systems of Equations: A Survey. (with Shuying Sun and Ye Wang),
Lecture Notes of Seminario Interdisciplinare di Matematica , Vol. 14 (2017), pp. 105–-142. https://drive.google.com/file/d/13HV9UrloLrxGt62_YOOJ-WT4cgDOZAiN/view?usp=sharing
Talk 5: A Journey with Antimagic Labeling - Prof. Kiki Ariyanti Sugeng
Date: Wednesday July 14 2021
Time: 15:00 (CEST)
Speaker: Prof. Kiki Ariyanti Sugeng
Title: A Journey with Antimagic Labeling
Abstract: Antimagic labeling is defined as an assignment from the element of a graph to usually a set of integers such that the weight of the element of the graph is all different. There are many variations of antimagic labeling, depending on which element of graph is labeled and how the weight is calculated. One of the definitions is as follows: A graph G is called antimagic if the edges can be labeled with the integers 1,2,...,q such that the sum of labels at any given vertex is different from the sum of the labels at any other vertex, i.e., no two vertices have the same sum. In this talk, I would like to share my journey with antimagic labeling through many variations of this labeling. https://drive.google.com/file/d/11AXXVAbNeJ9LbskDD_jZNoC9O2-XLHkP/view?usp=sharing
Slides: https://drive.google.com/file/d/1HGHz4e7pV6GJ1kICdbvVt8racCiMeZoN/view?usp=sharing
Video: https://drive.google.com/file/d/1YM18ibCuuB1XYH8A8XkK_S_I7yY_cCNg/view?usp=sharing
Talk 6: Biregular Cages - Prof. Robert Jajcay
Date: Wednesday September 15 2021
Time: 16:00 (CET)
Speaker: Prof. Robert Jajcay
Title: Biregular Cages
Abstract: The Cage Problem - the problem of finding a smallest k-regular graph of girth g, i.e., the (k,g)-cage - is well known to be very hard and the exact orders of cages are known for very few parameter pairs (k,g). One possible approach to understanding structural properties of cages includes considering biregular graphs that contain vertices of two degrees, m and n, and generalizing the Cage Problem by looking for smallest graphs of girth g containing vertices of the two degrees m and n, the (m,n;g)-cages. In the case of odd girths, results of this approach differ quite a bit from the regular Cage Problem as the orders of biregular (m,n;g)-cages are determined for all odd girths g and degree pairs m,n in which m is considerably smaller than n. The even girth case is still wide open, and has been therefore restricted to bipartite biregular graphs in which the two bipartite sets consist exclusively of vertices of one of the degrees (regular cages of even girth are also conjectured to be bipartite). We survey the most resent results on biregular and bipartite biregular cages, present some improved lower bounds, and discuss an interesting connection between bipartite biregular cages and t-designs.
Slides: https://drive.google.com/file/d/1GKlTVWu63BaPMhbEvPOibC8_CeQki3iK/view?usp=sharing
Video: https://drive.google.com/file/d/1cFV_jLyoge-NvFLGakkyxU-jhzWOq5s0/view?usp=sharing
Talk 7: Open problema in Distance-based Graph Labelings - Prof. Rinovia Simanjuntak
Date: Wednesday October 13 2021
Time: 13:00 (CET)
Speaker: Prof. Rinovia Simanjuntak
Title: Open problema in Distance-based Graph Labelings
Abstract: https://drive.google.com/file/d/1zLaEyrimiZphyQ-wWDMvi_SW8JS-uu59/view?usp=drivesdk
Slides: https://drive.google.com/file/d/1RW19I1fUWR0d7lHd13xQb1oHQbVVCYy6/view?usp=sharing
Video: https://drive.google.com/file/d/1FrUpH3vgGCOwzvTGuRnZ9uqH4CPSfbxF/view?usp=sharing
Talk 8: On the existence of almost Moore digraphs - Prof. Edy Tri Baskoro
Date: Wednesday November 10 2021
Time: 15:00 (CET)
Speaker: Prof. Edy Tri Baskoro
Title: On the existence of almost Moore digraphs
Abstract: https://drive.google.com/file/d/1L6t25SxIUEJAyt2z1F5jdLSFjgVbUfBv/view?usp=sharing
Video https://drive.google.com/file/d/1uDJtL9Anut5n2XT5fQA6PsXC1wOod-kH/view?usp=sharing
Talk 9: Strong cliques in diamond-free graphs - Prof. Berenice Martinez Barahona
Date: Wednesday December 15 2021
Time: 17:00 (CET)
Speaker: Prof. Berenice Martínez-Barona
Title: Strong cliques in diamond-free graphs
Abstract: A strong clique in a graph is a clique intersecting all inclusion-maximal stable sets. Strong cliques play an important role in the study of perfect graphs. In this talk, we study strong cliques in the class of diamond-free graphs, from both structural and algorithmic points of view. We show that the following five NP-hard or co-NP-hard problems all remain NP-hard or co-NP-hard when restricted to the class of diamond-free graphs: Is a given clique strong? Does the graph have a strong clique? Is every vertex contained in a strong clique? Given a partition of the vertex set into cliques, is every clique in the partition strong? Can the vertex set be partitioned into strong cliques?
On the positive side, we show that the following two problems whose computational complexity is open in general can be solved in linear time in the class of diamond-free graphs: Does every induced subgraph have a strong clique? Is every maximal clique strong? Is every edge contained in a strong clique? The last two results are derived from a characterization of diamond-free graphs in which every maximal clique is strong, which also implies an improved Erdös-Hajnal property for such graphs.
(Joint work with Nina Chiarelli, Martin Milanič, Jerome Monnot and Peter Muršič.)
Video https://drive.google.com/file/d/10rZ2fGwCdjR_uZvIqDuLIG5CXcTRdt1m/view?usp=sharing
Talk 10: Perfect Matchings in Regular Graph with Given Connectivity - Prof. Yuqing Lin
Date: Wednesday January 19 2022
Time: 9:30 Sydney time [23:30 (CET) of January 18th 2022]
Speaker: Prof. Yuqing Lin
Title: Perfect Matchings in Regular Graph with Given Connectivity
Abstract: The problem of how many edge disjoint perfect matchings are there in a graph is a classical topic in graph theory. Most of the work focus on the case where the degree is large, roughly speaking, equal to half of the total number of the vertices in the graph. For example, it has been conjectured that these graphs can be factorized. When working with this conjecture, we realize that the connectivity plays an important role in guarantee the graph has required number of perfect matchings and/or other factors. In this talk, I will present a few results we have obtained along this direction.
Video https://drive.google.com/file/d/1XIHFQKK8cPCccgEuNU8LEchtovKZfH7p/view?usp=sharing
Talk 11: Colorings of Moore graphs - Prof. Mika Olsen
Date: Wednesday February 16 2022
Time: 18:00 (CET)
Speaker: Prof. Mika Olsen - Universidad Autónoma Metropolitana- Cuajimalpa (UAM-Cuajimalpa), México
Title: Colorings of Moore graphs
Abstract: Coloring graphs is a popular topic in graph theory. In this talk I consider two different colorings of Moore graphs, namely rainbow colorings of edges and packing colorings of vertices.
A path P in an edge-colored graph is a rainbow path if there are no arcs of P with the same color. The rainbow connectivity rc(G) is the smallest integer k such that there is an edge coloring of a graph satisfying that the graph is connected by rainbow paths.
A vertex coloring of a graph is a packing coloring if any pair of vertices of color i satisfies that the distance between them is at least i+1. The packing chromatic number is the is the smallest integer k such that there is a packing coloring with k colors.
I will present results for the rainbow t-connectivity of (k,6)-Moore graphs and results for packing chromatic number of Moore graphs with girth 6,8 and 12. In both cases the results where obtained using structures of Moore graphs.
Video https://drive.google.com/file/d/13kyGioVoVGcKliUAt_0afyEJmgdtBiZK/view?usp=sharing
Talk 12: Four families of polynomials in spectral graph theory - Prof. Miquel Àngel Fiol
Date: Wednesday March 16 2022
Time: 17:00 (CET)
Speaker: Prof. Miquel Àngel Fiol
Title: Four families of polynomials in spectral graph theory
Abstract: In this talk, we describe four families of polynomials related to the spectrum of a graph. First, some known main results involving such polynomials, such as the spectral excess theorem characterizing distance-regularity, are discussed. Second, some new results giving bounds for the k-independence number αk of a graph are presented. In this context, we comment on some relationships between the inertia (Cvetkovic) and ratio (Hoffman) bounds of αk.
Slides: [https://drive.google.com/file/d/1EbfdMPDFXfs1E8CtUbCBtrSw7mT-gE2f/view?usp=sharing https://drive.google.com/file/d/1EbfdMPDFXfs1E8CtUbCBtrSw7mT-gE2f/view?usp=sharing]
Video: [https://drive.google.com/file/d/1MyQ-SsQ5bXVc4nUYmyjxGCSwVaH3iNQo/view?usp=sharing https://drive.google.com/file/d/1MyQ-SsQ5bXVc4nUYmyjxGCSwVaH3iNQo/view?usp=sharing]
Talk 13: Berge’s conjecture for cubic graphs with small colouring defect - Prof. Edita Máčajová
Date: Wednesday April 20 2022
Time: TBA
Speaker: Prof. Edita Máčajová
Title: Berge’s conjecture for cubic graphs with small colouring defect
Abstract: https://drive.google.com/file/d/1tAEybLG2Pg1G6DYQSaTW14y1HOqteIFa/view?usp=sharing
Video: https://drive.google.com/file/d/1kgAmb7zQB9Jvsrr4y8Lt0pgK1JB4z-L6/view?usp=sharing
Talk 14: Measuring the closeness to Moore graphs - Prof. Nacho López
Date: Wednesday May 18 2022
Time: 15:00 (CET)
Speaker: Prof. Nacho López
Title: Measuring the closeness to Moore graphs
Abstract: In this talk we will discuss how to measure the closeness to a Moore graph. This `closeness' has been usually measured as the difference between the (unattainable) Moore bound and the order of the considered graphs. Another kind of approach considers relaxing some of the constraints implied by the Moore bound. For instance, we could relax the condition of the degree and admit few vertices with larger degree, as Mirka did for the directed case. Radial Moore graphs are also approximations of Moore graphs, where we allow the existence of vertices with eccentricity just on more than the value they have in a Moore graph. Once we have many different graphs close to Moore graph, an interesting question is how to rank them according to their proximity to being a Moore graph.
Slides: https://drive.google.com/file/d/1FeqbpnXDWpS7xd37Zknyh3ZQ15H0JR38/view?usp=sharing
Video: https://drive.google.com/file/d/1C7zLSb3b_anh3oXE2MZz0BpoPXVOZN_6/view?usp=sharing
Talk 15: On mixed cages - Prof. Diego González
Date: Wednesday June 15 2022
Time: 17:00 (CET)
Speaker: Prof. Diego González
Title: On mixed cages
Abstract: A mixed graph is a graph with edges and arcs. A [z, r; g]-mixed cage is a mixed graph, z-regular by arcs, r-regular by edges with girth g and minimum order. In this talk I’m going to give an overview of the results in mixed cages, and I will talk about the monotonicity and the connectivity of mixed cages. This is a joint work with Gabriela Araujo and Claudia De la Cruz.
Slides: TBA
Video: TBA
Talk 16: On weight-equitable partitions of graphs - Prof. Aida Abiad
Date: Wednesday July 20 2022
Time: 14:00 (CET)
Speaker: Prof. Aida Abiad
Title: On weight-equitable partitions of graphs
Abstract: Weight-equitable partitions of graphs, which are a natural extension of the well-known equitable partitions, have been shown to be a powerful tool to weaken the regularity assumption in several classic eigenvalue bounds. Weight-equitable partitions assign to each vertex a weight that equals the corresponding entry of the Perron eigenvector. In this talk we will present several algebraic characterizations and some computational results of weight-equitable partitions. In addition, we will show that such partitions provide a condition under which Hoffman's ratio bound can be improved.
Slides: TBA
Video: https://drive.google.com/file/d/1Desep_26gt_gg7W7-M8VrGg_uTdrB-x_/view?usp=sharing
Talk 17: Spectral Moore theorems for graphs and hypergraphs - Prof. Sebastian Cioaba
Date: Wednesday October 19 2022
Time: 16:00 (CET)
Speaker: Prof. Sebastian Cioaba (University of Delaware)
Title: Spectral Moore theorems for graphs and hypergraphs
Abstract: The spectrum of a graph is closely related to many graph parameters. In particular, the spectral gap of a regular graph which is the difference between its valency and second eigenvalue, is widely seen an algebraic measure of connectivity and plays a key role in the theory of expander and Ramanujan graphs. In this paper, I will give an overview of recent work studying the maximum order of a regular graph (bipartite graph or hypergraph) of given valency whose second largest eigenvalue is at most a given value. This problem can be seen as a spectral Moore problem and has close connections to Alon-Boppana theorems for graphs and hypergraphs and with the usual Moore or degree-diameter problem
Slides: TBA
Video: https://drive.google.com/file/d/1O1o916Iu_XbVqIAR5dTAth3LOrLJFv9y/view?usp=sharing
Talk 18: On hamiltonian paths of the complete graph with prescribed edge-lengths - Prof. Anita Pasotti
Date: Wednesday November 16 2022
Time: 14:30 (CET)
Speaker: Prof. Anita Pasotti (University of Brescia, Italy)
Title: On hamiltonian paths of the complete graph with prescribed edge-lengths
Abstract: https://drive.google.com/file/d/1H07eEmsU9RsUwlVTb1uZTEajCA4F3lqu/view?usp=share_link
Slides: https://drive.google.com/file/d/1lltYz-fkvBxAV1XcN8uYENPXbX4L5QEc/view?usp=share_link
Video: https://drive.google.com/file/d/1GW1a0DjBuzI6wp3pceagI9KyY7kCZdSN/view?usp=share_link
Talk 19: Mixed graphs with small excess - Prof. Grahame Erskine
Date: Wednesday December 21 2022
Time: 16:00 CET (15:00 UK time)
Speaker: Prof. Grahame Erskine (The Open University, UK)
Title: Mixed graphs with small excess
Abstract: The degree-diameter problem for undirected graphs extends in a natural way to the cases of directed or mixed graphs; we insist that every vertex should be reachable from any other vertex by a path of speficied maximum length. However, the undirected degree-girth problem can be generalised in a number of ways. One natural extension to digraphs and mixed graphs is to insist that any pair of vertices be joined by no more than one path of some specified maximum length; this is called the geodecity problem.
The degree-geodecity problem is in a sense dual to the degree-diameter problem. They share the same Moore bound; in the case of the geodecity problem the Moore bound is a lower bound on the order of a graph with given degree and geodecity, and we are interested in minimising the excess of a graph above this bound. The problem has some features in common with the degree-girth problem for undirected graphs; chief among these is that it seems to be very hard to get good bounds on how small the excess of a directed or mixed graph can be for given degree and geodecity.
We will discuss some of what is known about this problem, with a particular emphasis on mixed graphs.
Slides: https://drive.google.com/file/d/1RkDrLfG3TfYqRY_kMesv9WPrEy4bcTOz/view?usp=share_link
Video: https://drive.google.com/file/d/1xumoar4OhI7l2oEZlDf4aFQB0rcnEn9g/view?usp=share_link
Talk 20: Approaching the Moore bound in the degree-diameter problem by Cayley graphs - Prof. Jana Šiagiová
Date: Wednesday January 18 2023
Time: 15:00 (CET)
Speaker: Prof. Jana Šiagiová (Slovak University of Technology in Bratislava)
Title: Approaching the Moore bound in the degree-diameter problem by Cayley graphs
Abstract: The well known degree-diameter problem for graphs is to determine the largest number n(d,k) of vertices in a graph of given maximum degree d and given diameter k. A trivial upper bound M(d,k) on n(d,k) is provided by the number of vertices of a rooted tree of the same maximum degree and of depth equal to the given diameter, and it is also well known that this upper bound is attained in a non-trivial way only for diameter 2 and degrees 3, 7, and possibly 57, and for no degree and diameter both greater than 2. Some years ago a natural question arose if examples of `large' graphs for given d and k can be constructed by means of Cayley graphs. We have answered this question in the affirmative for diameters k=2 and k=3 by proving that in each case there is an infinite set D(k) of degrees, and for each such degree d a Cayley graph with c(d,k) vertices, such that lim sup c(d,k)/M(d,k) is equal to 1 as d ranges over the set D(k). Thus, at least in this sense, for diameters 2 and 3 the Moore bound can be approached asymptotically. The aim of the talk is to present background on the methods and more details used in the proof of this asymptotic result, hoping to revive interest in trying to push it further.
Slides: []
Video: https://drive.google.com/file/d/1tQVeyG8oRfMfeJNCORLLvZaxlYB40r_x/view?usp=share_link
Talk 21: L(h,k)-colorings of some Moore graphs via some special structures - Prof. Julián Fresán
Date: Wednesday Frebruary 15, 2023
Time: 17:00 (CET)
Speaker: Prof. Julián Fresán (Universidad Autónoma Metropolitana-Cuajimalpa, México)
Title: L(h,k)-colorings of some Moore graphs via some special structures
Abstract: In this talk, I will present a particular structure of the non-adjacencies of the projective planes and two special structures of classical generalized quadrangles. We will use these structures to obtain bounds of a coloring problem, the L(h,k)-coloring problem, of their incidence graphs. This coloring is a vertex coloring with numbers in which the difference between any pair of vertices at distance one is at least h and any pair of vertices at distance two have coloring numbers that differ by at least k. If we start the coloring with zero, the goal of this problem is to find the L(h, k)-coloring with the smallest maximum number.
Slides: https://drive.google.com/file/d/10odT6l8zRF3DGaA899ljikoxEblQPW2d/view?usp=share_link
Video: https://drive.google.com/file/d/10lKFgZ3Nuvt1hqBRZisOMXmEeRO--Xni/view?usp=share_link
Talk 22: A variant of the algebraic connectivity and grid drawings of complete multipartite graphs - Prof. Clemens Huemer
Date: Wednesday March 15, 2023
Time: 15:00 (CET)
Speaker: Prof. Clemens Huemer (UPC)
Title: A variant of the algebraic connectivity and grid drawings of complete multipartite graphs
Abstract: Abstract: We use spectral graph theory to show how to draw the vertices of a complete multipartite graph G on different points of a bounded d-dimensional integer grid, such that the sum of squared distances between vertices of G is (i) minimized or (ii) maximized. For both problems, we provide a characterization of the solutions. For the particular case d = 1, our solution for (i) also settles the minimum-2-sum problem for complete bipartite graphs; the minimum-2-sum problem was defined by Juvan and Mohar in 1992. Weighted centroidal Voronoi tessellations are the solution for (ii). Such drawings are related to Laplacian eigenvalues of graphs. This motivates us to study which properties of the algebraic connectivity of graphs carry over to the restricted setting of drawings of graphs with integer coordinates.
This is joint work with Ruy Fabila-Monroy, Carlos Hidalgo-Toscano, Dolores Lara, and Dieter Mitsche.
Slides:
Video: https://drive.google.com/file/d/1Pyw4Nw7iZ3W1oLydrkuisV2ohqBbyEGO/view?usp=share_link
Talk 23: Results on Problems I Learned About on the Mirka Miller Webinar - Prof. Geoffrey Exoo
Date: Wednesday April 19, 2023
Time: 16:00 (CET)
Speaker: Prof. Geoffrey Exoo (Indiana State University)
Title: Results on Problems I Learned About on the Mirka Miller Webinar
Abstract: Several problems pertaining to the interplay among degree, girth, diameter, geodecity, and algebraic connectivity for undirected, directed, and mixed graphs are considered.
The author gratefully acknowledges learning about several of these concepts, and most of the problems discussed while attending earlier meetings of the Mirka Miller Webinar.
Slides: https://drive.google.com/file/d/19wKzvGBuRHN_z5_vH3qkMg-GQSO1DKNq/view?usp=drivesdk
Video:
Talk 24: On the spectra of token graphs of a cycle - Mónica Reyes, Prfo. Cristina Dalfó and Prof. Miquel Àngel Fiol
Date: Wednesday May 17, 2023 - special edition from BIRS-BANFF within the Extremal Graphs arising from Designs and Configurations Workshop
Time: 9:00 Calgary time (17:00 CEST)
Speaker: Mónica Reyes, Prof. Cristina Dalfó, Prof. Miquel Àngel Fiol (UPC and University of Lleida)
Title: On the spectra of token graphs of a cycle
Abstract: 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.
Slides: Part I https://drive.google.com/file/d/1KALgxuK5GlyfuBRCib5odvKj3_0krpYT/view?usp=drivesdk
Part II https://drive.google.com/file/d/1t9MUTwM3Bj03FweZilDzmqQ7jnUNmZ_W/view?usp=drivesdk
Part III https://drive.google.com/file/d/1-elNL9yfvm2i45Y9n_z-bdRstDdaepoF/view?usp=drivesdk
Video: Part I https://www.birs.ca/events/2023/5-day-workshops/23w5125/videos/watch/202305170900-Dalfo.html
Part II https://www.birs.ca/events/2023/5-day-workshops/23w5125/videos/watch/202305170930-Fiol.html
Part IIIhttps://www.birs.ca/events/2023/5-day-workshops/23w5125/videos/watch/202305171000-Reyes.html
Talk 25: Biregular (and regular) planar cages - Natalia García-Colín
Date: Wednesday June 21, 2023
Time: 16:00 (CEST)
Speaker: Christian Rubio
Title: Biregular (and regular) planar cages
Abstract: In this talk I will present our no-so-recent results on the Cage Problem for biregular planar graphs. This problem has been widely studied for biregular graphs (without the planarity hypothesis).
An ({r, m}; g)-graph is a biregular graph whose vertices have degrees r and m, for 2 ≤ r < m, and girth g. An ({r,m};g)-cage is an ({r,m};g)- graph of minimum order. In this work we have determined the triplets of values ({r, m}; g) for which there exist planar ({r, m}; g)-graphs and for all values we construct examples. Furthermore, we bound the order of the ({r, m}; g)- cages and in many instances our constructions reach the bounds.
This is joint work with Gabriela Araujo-Pardo and Fidel Barrera-Cruz.
Slides: https://drive.google.com/file/d/1EmXKi6fe6szrBfNlDwrepPbotM0weoXy/view?usp=sharing
Video: https://drive.google.com/file/d/1TuB-783xMS2MSIv1upffo4Y61zm-LR2O/view?usp=drive_link
Talk 26: Regular graphs of given chromatic number of minimum order - Christian Rubio
Date: Wednesday September 20, 2023
Time: 17:00 CET
Speaker: Christian Rubio
Title: Regular graphs of given chromatic number of minimum order
Abstract: We define an extremal (r|χ)-graph as an r-regular graph with chromatic number χ of minimum order. In this work, we study the Turán graphs, the antihole graphs, and the graphs Kn x K2 which are extremal in this sense. We also exhibit several extremal Cayley (r|χ)-graphs and some constructions arising from Turán graphs.
Slides: https://drive.google.com/file/d/1dsMXXFnkdthHXn_s4imGUcDj6ZrxiCXn/view?usp=sharing
Date: Wednesday October 18th, 2023
Time: 17:00 (CEST)
Speaker: Klara Stokes (from Umeå University)
Title: New incidence geometries related to the classical generalized hexagons and triality
Abstract: In the 1960s, Tits studied a phenomenon called triality in a hyperbolic quadric in a 7-dimensional projective space. He noted that the incidence geometry of points and lines that are fixed by the triality had interesting properties that generalized the hexagon, thereby inventing the generalized polygons. The incidence graph of the generalized polygons are Moore graphs of even girth; they have the property that the girth is twice the diameter. In this talk, I will introduce new geometries related to the classical generalized hexagons. This is joint work with Dimitri Leemans and Philippe Tranchida.
Slides:
Video: https://drive.google.com/file/d/1PXeHtzhp7rr-MDzMxZ49GSX1ZeEV1iAl/view?usp=sharing
Talk 28: Heffter arrays: from the applications to a generalization - Tommaso Traetta
Date: Wednesday November 15th, 2023
Time: 17:00 (CEST)
Speaker: Tommaso Traetta (from University of Brescia)
Title: Heffter arrays: from the applications to a generalization
Abstract: In 2015, Archdeacon introduced Heffter arrays as a tool to construct current graphs, orthogonal cycle systems and (if endowed with a pair of special orderings) biembeddings of complete graphs on surfaces. In this talk, after describing these connections, we introduce a generalized class of Heffter-type arrays which extend these applications and we show how near alternating sign matrices can be effectively used to build them, thus providing new existence results even in the classic case. This is joint work with Lorenzo Mella.
Slides: https://drive.google.com/file/d/1icYoT4Dw3mreCaSE1_Jzidjv9pncEh67/view?usp=drive_link
Video: https://drive.google.com/file/d/1nrSzFu6h4qhqoA5VoQHW8JWjjHwotXpB/view?usp=drive_link
Talk 29: Properties of Villarceau Torus - Paul Manuel
Date: Wednesday December 20th, 2023
Time: 14 CET
Speaker: Paul Manuel
Title: Properties of Villarceau Torus
Abstract: Villarceau torus is a discrete graph theory model of the spiral torus, which is called the Helical Toroidal Electron Model in Physics. It also represents the double-stranded helix model of DNA. The spiral torus or toroidal helix in Physics and Molecular Biology is continuous, whereas the Villarceau torus is discrete. The main contribution of the paper is the identification of cycles that are equivalent to the toroidal helix in the spiral torus. In addition, the poloidal revolution and the toroidal revolutions of Villarceau torus are computed. The paper identifies some striking differences between the ring torus and Villarceau torus. It is proved that Villarceau torus does not admit any convex edge-cuts and convex cycles other than 4-cycles. The convex-cut method is extended to graphs that do not admit convex edge-cuts. Using this technique, the network distance (Wiener Index) is computed. Also, an optimal congestion-balanced routing for Villarceau torus is designed.
Link: https://eu.bbcollab.com/guest/1f76fcb050da4e7cae40d3b8c33d5d7d
Slides: https://drive.google.com/drive/folders/1h-72Zzto5PCmo1ThgZdzYUJlMseS_6XS
Video: https://drive.google.com/drive/folders/1hFfJqLIR4NEMd-4Wr8WOOkv4-jcjgJ5H
Talk 30: Constructing small totally regular mixed graphs of given degrees and girth - Tatiana Jajcayová
Date: Wednesday January 17th, 2024
Time: 15:00 CET
Speaker: Tatiana Jajcayová
Title: Constructing small totally regular mixed graphs of given degrees and girth.
Abstract: In our talk, we will discuss a generalization of the original Cage Problem in the setting of mixed graphs, which we will call Mixed Cage Problem. Among mixed graphs, we concentrate on extremal totally regular mixed graphs - graphs in which the number of adjacent non-oriented edges is equal to r, and the number of out-going and in-going edges is equal to z, for all vertices of the graph. In order to obtain good upper bounds for the orders of totally regular mixed graphs of given girth and smallest possible order, it is reasonable to consider some related (non-mixed) (k,g)-cages or record (k,g)-graphs and modify them into mixed graphs by adding directions to certain edges. We propose to use in this manner the CD(n,q) graphs of Lazebnik, Ustimenko and Woldar which constitute the best universal family of regular graphs of prime power degree with regard to the original Cage Problem. In our presentation, we will define the CD(n,q) graphs, and will explain their relevance in the context of the Cage and the Mixed Cage Problems.
Link: https://eu.bbcollab.com/guest/f55b21be67dc443fb2ab44c1b0b43da0
Slides: https://drive.google.com/drive/folders/1h-72Zzto5PCmo1ThgZdzYUJlMseS_6XS
Video: https://drive.google.com/drive/folders/1hFfJqLIR4NEMd-4Wr8WOOkv4-jcjgJ5H
Talk 31: Revisiting the Degree-Diameter Problem: A Six-Decade Perspective - Francesc Comellas
Date: Wednesday February 21st, 2024
Time: 15:00 CET
Speaker: Francesc Comellas
Title: Revisiting the Degree-Diameter Problem: A Six-Decade Perspective.
Abstract: The degree-diameter problem for undirected graphs is the problem of finding a graph with the largest possible number of vertices given a maximum degree and maximum diameter. Sixty years ago, the problem gained significant attention with seminal papers by Hoffman-Singleton and Elspas. Since then, there has been periods of intense activity: In the 80s and 90s, they were centered around LRI in Paris (Delorme, Bermond, Farhi, ...) with connections to Belgium (Quisquater, Buset, ...), UPC in Barcelona (Gómez, Fiol, Yebra, FC, ..) as well as research efforts in New Zealand (Hafner, Dinneen) and Germany (Sampels). All this work has fostered enduring collaborations and yielded lasting results. In January 1995, at UPC, we established the first online table for the degree-diameter problem, which became a valuable reference within the field. At the turn of the century, fresh approaches to the problem emerged from the US (Exoo) and Oceania (Loz, Sirán, Miller, Pineda-Villavicencio, Pérez-Rosés, ...), leading to substantial enhancements in the table of large degree-diameter undirected graphs and other related tables. A crucial landmark was the comprehensive review paper by Mirka Miller and Jozef Sirán (2005) complemented by web tables hosted at combinatoricswiki.org. Over the past fifteen years, progress has been limited basically to a few hard-to-find values for small orders. Despite this current slowdown, the evolution of the degree-diameter table has been remarkable and new advances seem possible. In this presentation, my focus will be on tracing the journey of this table from the initial publications to its current state, highlighting the contributions of various researchers and the advances made along the way.
Link: https://eu.bbcollab.com/guest/a50cc5e1e9754ec2a7e2ffe3b41912ed
Slides: https://drive.google.com/file/d/1KT5WknjbJNWYduFdPx_bztyJRgFZofeV/view?usp=drive_link
Video: https://drive.google.com/drive/folders/1hFfJqLIR4NEMd-4Wr8WOOkv4-jcjgJ5H
Talk 32: On the existence of (r, g, χ)-cages - Linda Lesniak
Date: Wednesday 20 March 2024
Time: 16:00 (CET)
Speaker: Linda Lesniak
Title: On the existence of (r, g, χ)-cages
Abstract: In 1961, Erdős showed the following: Given integers χ ≥ 3 and g ≥ 3, there exists a graph with chromatic number χ and girth g. In 1947, Tutte asked the following question: Given integers r ≥ 2 and g ≥ 3, does there exist an r-regular graph with girth g and minimum order? Erd ̋os and Sachs established existence for all pairs r,g in 1960. Finally, Rubio-Montiel considered the problem of the existence of graphs with a given regularity r, chromatic number χ, and also minimum order. In this talk, we’ll look at the question of the existence of (r, g, χ)-cages, that is, r-regular graphs of girth g with chromatic number χ and minimum order. These graphs were introduced by Gabriela Araujo-Pardo, Zhanar Berikkyzy, and Linda Lesniak, where the emphasis was on the case χ = 3. But we now know, for example, according to the work of Gabriela Araujo-Pardo, Julio Diaz-Calderon, Julian Fresan, Diego González-Moreno, and Mika Olsen, that if g and χ are integers both at least 3, then for r sufficiently large there exist (r, g, χ)-graphs.
Finally, we’ll consider the question of the existence of ”equitable” (r, g, χ)- cages, that is, (r, g, χ)-cages with a χ-coloring in which the color classes differ in size by at most 1.
Slides: https://drive.google.com/file/d/1bJD7Ud0iVZacKvAwgK9U3tA7JsTnru-X/view?usp=drivesdk
Video: Video part 1 https://drive.google.com/file/d/1MeQ2MDPQv42sT476rGkeiVkbBi8YlQRT/view?usp=drivesdk
Video part 2 https://drive.google.com/file/d/1E2c3tFGc0-BvdcQJT6SR03O5eb9W-aix/view?usp=drivesdk
Talk 33: James Tuite (Open University, UK)
Date: 17 April 2024
Time: 16:00 CEST (15:00 GMT)
Speaker: James Tuite
Title: Visibility in Graphs
Abstract: A collection of points in space is in general position if no three of the points lie on a straight line. We consider the following discrete version of this no-three-in-line concept: for a graph G what is the largest number of vertices in a set S ⊆ V (G) if we require that no three vertices of S lie on a common shortest path? I will show firstly how this seemingly simple problem is connected to some of the deepest themes of combinatorics. Then we will explore some of the directions in which this problem has evolved in the last five years, including robotic navigation problems, a fractional version of general position and no-three-in-line games.
Meeting link: https://eu.bbcollab.com/guest/5dd6af40782341b8a4b56dd7d505a8f5
Slides: https://drive.google.com/drive/folders/1h-72Zzto5PCmo1ThgZdzYUJlMseS_6XS
Video: https://drive.google.com/drive/folders/1hFfJqLIR4NEMd-4Wr8WOOkv4-jcjgJ5H
Obituaries: Mirka Miller (nee Koutova) https://drive.google.com/file/d/1su6y1qhUkR3PosqRDfFSGhFbKz1oseP1/view?usp=sharing
Special Issue in Honour of Mirka Miller https://drive.google.com/file/d/1wWRIXelvnGhkOM7IlhZhH0G0xxT6rd0s/view?usp=sharing
In memoriam Emeritus Professor Mirka Miller https://drive.google.com/file/d/1WQVHk41Yi5fJuGhWYscN9CwwirdU8uOu/view?usp=sharing
Eulogy for Professor Mirka Miller (1949–2016) [v https://drive.google.com/file/d/1hTS8HxU9omjlF2Q-_jOQIREcguR1Y1FU/view?usp=sharing]
A family of mixed graphs with large order and diameter 2 https://drive.google.com/file/d/1zbwb56QKY1iSeOm6c4ko178Y0UXNIzfL/view?usp=sharing
Photos
Organisers
• Marién Abreu - Dipartimento di Matematica, Informatica ed Economia - Università degli Studi della Basilicata - Potenza, Italia
• Gabriela Araujo-Pardo - Mathematics Institute-Juriquilla - Universidad Nacional Autónoma de México, México
• Camino Balbuena - Department of Civil and Enviromental Engineering - Universitat Politècnica de Catalunya, Spain
• Cristina Dalfó - Cryptography and Graphs Research Group - Universitat de Lleida, Igualada (Barcelona), Catalonia
• Tatiana Jajcayova - Faculty of Mathematics, Physics and Informatics - Comenius University, Bratislava, Slovakia
Honorary Organiser
• Joe Ryan - School of Electrical Engineering and Computing - University of Newcastle, Australia
Website Host and Support
• Grahame Erskine - Department of Mathematics of Statistics - The Open University, UK.
(the organisers thank him for kindly including this website in Combinatorics Wiki)