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!

Jan 9, 10am CT

Speaker: Karen Meagher

Affiliation: University of Regina, Canada

Title: A Gentle Introduction to Erdos-Ko-Rado Combinatorics

Abstract: My research is centred around the famous Erdos-Ko-Rado (EKR) Theorem. I was first introduced to this theorem through an application in computer science, and later learned about its roots in pure mathematics. This is a research area that has grown so much recently that researchers have coined the term "Erdos-Ko-Rado Combinatorics" to describe the field. My talk will be a general introduction to this field, highlighting the different types of problems considered and their connections to different areas of math.

The original EKR Theorem is a problem in extremal set theory; it determines the largest collections of k-subsets from an n-set, with the property that any two of the subsets have non-empty intersection. The collection of all k-subsets that contain a fixed point is clearly an example of such a family (it is called a canonical intersecting family) and the EKR theorem states that it is the largest possible. One reason that the this theorem is so important is that it is a very natural and satisfying result! Further, there are many vastly different proofs of the result, and in recent year many extensions and generalizations have been considered.

One active direction is to show that a theorem analogous to the EKR holds for different objects. So consider any type of object with some notion of intersection, and ask what is the largest collection of objects so that any two from the collection have non-trivial intersection. A natural version of the EKR theorem is known to hold for set partitions, permutations, integer sequences, trees in a graph and many different geometries, just to name a few examples. A common proof method is to define a graph with the property that intersecting sets are exactly the cocliques (also called independent sets) in the graph. Then the problem becomes how to determine the largest cocliques in this graph. With this perspective, tools from linear algebra and algebraic graph theory can be applied and are surprisingly effective. Further, the adjacency matrices of these graphs often belong to a very structured matrix algebra and there can be patterns in the eigenvalues of these association scheme that can be used to find good, and often tight, bounds on the size of the cocliques.

Another direction in EKR combinatorics is to characterize all the largest intersecting sets. Typically, this is a much harder problem, but new and effective methods based on algebraic graph theory have been recently developed. This method considers a collection of Boolean functions defined on a subspace and leads to the study of related sets called Cameron-Liebler sets.

The focus of research has been on objects for which a version of the EKR theorem holds, but some recent work had looked for natural examples where the theorem does not hold. This work has focused on permutation groups, and trying to measure how far the group is to having the EKR theorem hold. There are also some examples where the EKR theorem is conjectured to hold, but the current methods are not effective.

No preprint  |  This talk will be recorded  |  Slides will be shared

Jan 23, 10am CT

Speaker: Lorenzo Ciardo

Affiliation: TU Graz, Austria

Title: TBA

Abstract: 

Feb 6, 10am CT

Speaker: Carlos Hoppen

Affiliation: Universidade Federal do Rio Grande do Sul (UFRGS), Brazil

Title: Recent progress on the inverse eigenvalue problem

Abstract: The inverse eigenvalue problem has played a central role in spectral graph theory in the last decade. In this talk, I shall be interested in a particular parameter, namely the minimum number of distinct eigenvalues of a graph G, i.e., in the minimum number of distinct eigenvalues of a real symmetric matrix whose underlying graph is G. To be precise, let M be a symmetric matrix of order n. A graph G is said to be the underlying graph of M if its vertex set has n elements and if any pair of distinct vertices i and j are adjacent if and only if the entry ij of M is nonzero. There is no constraint about diagonal entries.

It is well known that, if G is a tree, the value of this parameter is at least d(G)+1, where d(G) is the diameter of G. I will discuss instances where this bound is tight. In a different direction,  I will show that the number of eigenvalues of G is at most 4 whenever G is a cograph, that is, whenever G does not contain an induced path on four vertices.  

This includes joint work with L. Emilio Allem, Martin Fürer, Lucas Siviero Sibemberg, and Vilmar Trevisan.

Preprint 1, 2 and 3  |  This talk will be recorded  |  You may email the speaker for their slides

Feb 20, 10am CT

Speaker: John Urschel

Affiliation: TBA

Title: TBA

Abstract: 

Mar 6, 10am CT

Speaker: Veronika Furst

Affiliation: Fort Lewis College (Colorado)

Title: The number of edges of graphs that admit two distinct eigenvalues

Abstract: The Inverse Eigenvalue Problem for Graphs (IEP-G) concerns determining all possible spectra of matrices in S(G), the set of real symmetric matrices described by a graph.  Specific subproblems involve studying the maximum nullity or minimum rank, the ordered multiplicity list of distinct eigenvalues, or the minimum number of distinct eigenvalues of a graph.  In this talk, we will share recent results on the last of these, known as the parameter q(G).  In particular, we will investigate bounds on the number of edges of a graph through the “allows problem,” which asks what sparsity allows q(G) = 2, and the complementary “requires problem,” which asks what density requires q(G) = 2.  We will answer the first question, present a characterization of certain regular graphs, and give some evidence in support of a conjectured answer to the second question.

Joint work with W. Barrett, E. Egolf, S. Fallat, F. Kenter, S. Nasserasr, B. Rooney, M. Tait, and H. van der Holst, and partially supported by NSF grant DMS-2331072.

Preprint 1, 2, 3 and 4  |  This talk will NOT be recorded  |  You may email the speaker for their slides

Mar 20, 10am CT

Speaker: 

Affiliation: 

Title: TBA

Abstract: 

Apr 3, 10am CT

Speaker: Mark Kempton

Affiliation: Brigham Young University (USA)

Title: Non-backtracking Matrices of Graphs

Abstract: Famously, the adjacency matrix of a graph can be used to enumerate walks in graphs.  This makes the adjacency spectrum important to understanding graph structure.  I will talk about the non-backtracking matrix, which is used to enumerate walks that are not allowed to backtrack.  This matrix also have interesting spectral properties, which I will discuss.  We will also look at constructions of matrices that are cospectral with respect to the non-backtracking matrix.

No preprint  |  This talk will be recorded  |  Slides will be shared

Apr 17, 10am CT

Speaker: Lord Kavi

Affiliation: Concordia University of Edmonton (Canada)

Title: TBA

Abstract: 

May 1, 10am CT

Speaker: Sarojini Mohapatra

Affiliation: NIT Rourkela (India)

Title: TBA

Abstract: 

May 15, 10am CT

Speaker: Domingos Cardoso

Affiliation: University of Aveiro (Portugal)

Title: TBA

Abstract: 

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.