05C50 Online

05C50 Online is a biweekly virtual seminar about graphs and matrices held on a Friday, 10AM Central Time via Zoom. This is organized by Stephen Kirkland (University of Manitoba) and Hermie Monterde (University of Regina). Kindly fill out this FORM to subscribe to our mailing list (and receive zoom links for upcoming talks for FALL 2025).

Sep 12, 10am CT

Speaker: William J. Martin

Affiliation: Worcester Polytechnic Institute (WPI), USA

Title: The nearest neighbour graph of a Q-polynomial association scheme

Abstract: 

In his seminal 1973 thesis, Philippe Delsarte identified two important families of association schemes  deserving of in-depth study: the P-polynomial association schemes and the Q-polynomial  association schemes. P-polynomial association schemes are essentially the same as  distance-regular graphs and these have been extensively studies in the intervening years leading to a rich theory with deep results and a variety of applications. By contrast, Q-polynomial association schemes has received very little attention in the literature with the notable exception being when the scheme is also P-polynomial. Indeed, Hamming graphs, Johnson graphs, and many fundamental families of distance-regular graphs are both P- and Q-polynomial. 

The class of Q-polynomial association schemes also includes the schemes determined by the shortest vectors of some important lattices, schemes coming from extremal error-correcting codes and combinatorial designs, and real mutually unbiased bases, whose study is motivated by questions about measurements in quantum information theory. While it may be more natural to view a Q-polynomial association scheme as a certain type of spherical code (e.g., every platonic solid except the dodecahdron determines a Q-polynomial association scheme with one graph corresponding to each nonzero angle that occurs), our toolkit as combinatorialists leads us to frame our questions in graph-theoretic terms. In this talk, we study the graph determined by the smallest non-zero angle appearing among pairs of unit vectors in this spherical code. As we build the basic theory of this nearest neighbour graph, similarities and differences between the P-polynomial case and the Q-polynomial case will be highlighted.

This talk is based on joint work with Jason Williford (U Wyoming).

No preprint  |  Recording passcode:  3S=W*Rn!  |  Slides

Sep 26, 10am CT

Speaker: Milica Anđelić

Affiliation: Kuwait University, Kuwait

Title: Moore–Penrose Inverses of Signed Graph Laplacians: Formulas, Simplifications, and Extensions

Abstract: 

The Laplacian matrix L of a signed graph G  may or may not be invertible. We present an entrywise combinatorial formula for the Moore-Penrose inverse of L, obtained by deriving a combinatorial expression for the Moore-Penrose inverse of an incidence matrix of G. Our results extend known formulas for incidence and (signless) Laplacian matrices of unsigned graphs. We also highlight several particular cases in which the computation of the Moore-Penrose inverse can be considerably simplified by applying alternative, non-combinatorial methods. Finally, we indicate directions for further generalizations and applications, including the resistance matrix and the development of suitable partition-based approaches.

Preprint  |  Will be recorded  |  Slides will be available

Oct 10, 10am CT

Speaker: Sarobidy Razafimahatratra

Affiliation: Carleton University and the Fields Institute, Canada

Title: Erdős-Ko-Rado type theorems for transitive groups of degree a product of two odd primes

Abstract: Please click here.

Preprint 1, 2, 3  |  Not recorded |  You may email the speaker for their slides

Oct 24, 10am CT

Speaker: Susana Furtado

Affiliation: Faculdade de Economia do Porto and CEMS.UL, Portugal

Title: Efficient ranking vectors for pairwise comparison matrices

Abstract: 

An n-by-n matrix A=[a_{ij}] is said to be a pairwise comparison matrix (PC matrix) or a reciprocal matrix if it is positive and a_ij=1/a_ji, for all i,j=1,...,n. If, in addition, a_ika_kj=a_ij for all i,j,k, the matrix is said to be consistent. There is a natural consistent matrix associated to any positive vector.

PC matrices play an important role in decision making, namely in models for ranking alternatives, as the Analytic Hierarchy Process, proposed by Saaty (1977). In these models, a PC matrix represents independent, pairwise, ratio comparisons among n alternatives and a cardinal ranking vector should be obtained from it. The consistent matrix constructed from this vector should be a good approximation of the PC matrix. So, it is desirable to choose a ranking vector from the set of efficient vectors for the PC matrix, as, otherwise, there would be a positive vector such that the consistent matrix obtained from it better approximates the PC matrix in at least one entry and is not worse in all other entries.

In this talk we give two descriptions of the set of efficient vectors for a PC matrix and discuss some of its consequences. Saaty proposed the right Perron vector of a PC matrix as the ranking vector. We discuss the efficiency of this vector and, in addition, we provide vectors constructed from the matrix whose efficiency is universal.

This is a joint work with Charles Johnson.

No preprint  |  Not recorded |  You may email the speaker for their slides

Nov 7, 10am CT

Speaker: Sirshendu Pan

Affiliation: Indian Institute of Technology (IIT) Guwahati, India

Title: Dominant eigenvalue and winners in graphs

Abstract: 

Let A ∈ M_n be nonnegative, irreducible and E_ii = e_ie_i^T, where e_i is the ith standard basis vector. For a fixed t_0 > 0, an index p ∈ [n] := {1, 2, \ldots, n} is called a winner for the value t_0 if the spectral radius satisfies

\rho( A + t_0 E_pp ) = \max_{ i ∈ [n] } \rho( A + t_0 E_ii ).

If p remains a winner for each t>0, then it is called a universal winner. The concepts were introduced in 1996 and studied only in a few articles till now. When G is a simple connected graph (or a strongly connected digraph), the nonnegative weighted adjacency matrix A(G) being irreducible, one can talk of a universal winner vertex with respect to A(G). The universal winners seem to capture the graph structures well. It is known that the only strongly connected digraph G in which all vertices are universal winners with respect to all nonnegative weighted A(G), is the directed cycle, thereby characterizing it. Let S\subset [n] be nonempty. We characterize the class of strongly connected digraphs G with vertex set [n] for which only the vertices in S are the universal winners with respect to all nonnegative weighted A(G). Interestingly, in the case of undirected graphs, it turns out that the stars are the only such graphs. Looking at this result, one is naturally be curious about whether the structures will be different if we consider only the 0-1 adjacency matrices of connected undirected graphs? As expected, even for a tree, it is not in general true that there is always a universal winner. In fact, every tree is a subtree of a tree that has a unique universal winner, and also of one without a universal winner.  Trees with exactly k > 1 universal winners are not easy to find. A construction of a class of trees with exactly k universal winners is provided. Interestingly, it turns out that for any undirected connected graph G, the set of winners of G and the corona G \circ K_1 are the same, where the later is obtained by adding a new pendent vertex to each vertex of G. This talk is based on joint work with Steve Kirkland and Sukanta Pati.

Preprint 1, 2  |  Will be recorded  |  Slides will be available

Nov 21, 10am CT

Speaker: Antonina P. Khramova

Affiliation: Eindhoven University of Technology, Netherlands

Title: Algebraic bounds for sum-rank-metric codes

Abstract:

The sum-rank metric is a generalization of the well-known Hamming and rank metrics. In this talk, we introduce two new bounds on the maximal cardinality of the sum-rank-metric code with a given minimum distance. One of the bounds exploits a connection between such a code and a (d-1)-independent set in a graph defined for the sum-rank-metric space. We then use the eigenvalues of the graph to deduce the bound. The second bound is derived from the Delsarte's LP method, which has been previously obtained for Hamming metric, rank metric, Lee metric, and others, but the sum-rank-metric case remained open. To derive the new LP bound, we propose a way to construct an association scheme for the sum-rank metric, since the approach used in the Hamming and the rank-metric cases fails due to the associated graph not being distance-regular in general. Based on computational experiments on relatively small instances, we observe that the obtained bounds often outperform the bounds previously known for sum-rank-metric codes.

The talk is based on joint work with Aida Abiad, Alexander Gavrilyuk, Ilia Ponomarenko, and Alberto Ravagnani.

Preprint 1, 2  |  Will be recorded |  Slides will be available

For titles and abstracts of previous talks, and links to recordings, please visit here .

Please contact Hermie Monterde  if you have inquiries about the seminar.