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), Hermie Monterde (University of Regina) and Homer de Vera (University of Manitoba). Kindly fill out THIS FORM to subscribe to our mailing list!

Sep 25, 10am CT

Speaker: Luiz Emilio Allem

Affiliation: Universidade Federal do Rio Grande do Sul, Brazil

Title: q(G) for Threshold Graphs

Abstract: We study the minimum number of distinct eigenvalues q(G) of threshold graphs. It is known that every threshold graph satisfies q(G) at most 4, which suggests that a complete combinatorial characterization according to the values q(G) = 2, 3, 4 is possible.

In this talk, we present ongoing results toward such a characterization.

Preprint  |  Recording passcode:  e%F..v*2  |  Slides

Oct 9, 10am CT

Speaker: Roghayeh Maleki

Affiliation: University of Regina, Canada

Title: The complete classification of triply-transitive strongly-regular graphs

Abstract: An association scheme X on a finite set V is a highly-regular partition of the edge set of the complete graph on V. The Terwilliger algebra T_v of X with respect to a vertex v∈V is an algebra defined using the neighbours of v in each graph in the partition X. 

The algebra T_v satisfies the inclusions T_0 ⊆ T_v ⊆ \widetilde{T}, where T_0 is a certain subspace, and \widetilde{T} is the centralizer algebra of the stabilizer of v in the automorphism group of X.

We study the association schemes arising from strongly-regular graphs whose Terwilliger algebras are as small as possible in the sense that T_0 = T_v = \widetilde{T}. A strongly-regular graph Γ is called triply transitive if  (1) its automorphism group Aut(Γ) is transitive, and (2) its Terwilliger algebra coincides with both its subspace T_0 and \widetilde{T}. In this talk, I will present a complete classification of triply-transitive strongly-regular graphs.

No preprint  |  No recording  |  Slides will NOT be shared

Oct 23, 10am CT

Speaker: David Roberson

Affiliation: Technical University of Denmark (DTU), Denmark

Title: Applications of Coherent Configurations to Quantum Symmetry

Abstract: The quantum automorphism group of a graph is defined via a noncommutative relaxation of its classical automorphism group. Since its introduction, several authors have worked on classifying which “small” graphs have so-called quantum symmetry, meaning that their quantum automorphism group is strictly larger than its classical counterpart. Previously this had been completed for all 208 graphs on up to six vertices, and recent work by Schanz completed the classification for all 165 vertex transitive graphs on up to thirteen vertices. Considering the smallest coherent configuration that contains a given graph preserves the quantum automorphism group but maps many distinct graphs to the same configuration. This greatly reduces the number of objects that must be checked for quantum symmetry. Combining this with other tools from the theory of coherent configurations and from quantum groups allows us to classify all graphs on up to fifteen vertices (approximately 31 quintillion) that have quantum symmetry.

No preprint  |  Recording  |  Slides will be shared

Nov 6, 10am CT

Speaker: Prateek Kumar Vishwakarma

Affiliation: Indian Statistical Institute, New Delhi, India

Title: Hyperbolic distance matrix completion

Abstract: I will present a completion theory for hyperbolic distance data at the interface of matrix analysis, graph theory, and hyperbolic geometry, drawing particularly on representations of chordal graphs. In analogy with the positive semidefinite completion theorem of Grone, Johnson, Sá, and Wolkowicz and the Euclidean distance completion theorem of Bakonyi and Johnson, our existence theorem establishes chordality as a necessary and sufficient condition for locally consistent Lorentz-Gram data to always admit a global completion. We then give explicit constructions. For trees, these yield geodesic-rectification completions and recover the product-distance matrices of Bapat and Sivasubramanian. The latter construction extends to chordal graphs through matrix-valued transfers along clique trees. The resulting canonical completion is characterized by inverse sparsity via a formula of Johnson and Lundquist, and by a maximum-absolute-determinant principle. Finally, its metric distortion exhibits a dichotomy governed by clique separator size: distortion is uniformly bounded, by the square root of the graph’s diameter, precisely when the chordal graph is diamond-free. This talk is based on recent joint work with Mihai Putinar [arXiv:2609.10403].

Preprint  |  Recording  |  Slides will be shared

Nov 20, 10am CT

Speaker: Shivaramakrishna Pragada

Affiliation: Simon Fraser University, Canada

Title: A finiteness theorem for eigenvalue extremization problems

Abstract: Extremization of graph eigenvalues and their sums is a well-studied problem in spectral graph theory. A useful approach is to reduce optimization over graphs of arbitrary order to optimization over weighted graphs of bounded order. In this talk, we discuss a finiteness theorem for an eigenvalue maximization problem involving weighted Seidel adjacency matrices. The extremal value is attained on a weighted graph whose order admits an explicit bound depending only on the number of leading eigenvalues in consideration.

The main focus will be the finite reduction, which combines the Ky Fan maximum principle, an orthogonality-preserving cloning argument, and Carathéodory’s theorem from convex geometry. As a consequence, for each fixed subspace dimension, the maximal relative projection constants stabilize at the maximal absolute projection constant once the ambient dimension is sufficiently large, answering a question of Basso.

We will also briefly outline the solution of the maximum spectral sum problem. The spectral sum of a graph, defined as the sum of its two largest adjacency eigenvalues, is at most 8/7 of its order, proving a conjecture of Ebrahimi, Mohar, Nikiforov and Ahmady. The proof combines graph limits and a related reduction to weighted graphs on at most six vertices with exterior algebra and matrix sum-of-squares techniques.

Preprint  1   2  |  Recording  |  Slides will be shared

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.