Plenary speakers

Avoiding and Forcing: (0,1)-Matrices/Bipartite Graphs

Richard A. Brualdi
University of Wisconsin, Madison, USA

Plenary Talk 1: 25 Oct – 9:00am

Permutations/Permutation Matrices are ubiquitous in mathematics. For instance, a graph isomorphism is a permutation of the vertices, and thus a simultaneous permutation $PAP^T$ of the rows and columns of its $(0,1)$ -adjacency matrix $A$ . If $A$ is the bipartite adjacency matrix of a bipartite graph, then an isomorphism leaving its bipartition invariant is equivalent to an independent permutation $PAQ$ of its rows and columns. We shall explore some properties of $(0,1)$ -matrices $A$ that avoid or force certain patterns in the permutation matrices $P\le A$ it contains, thus properties of perfect matchings in its corresponding bipartite graph.

Chair: Vilmar Trevisan

Algebraic graph theory and quantum walks

Krystal Guo
Korteweg-De Vries Institute for Mathematics, University of Amsterdam and QuSoft

Plenary Talk 2: 25 Oct – 2:00pm

The interplay between the properties of graphs and the eigenvalues of their adjacency matrices is well-studied. Important graph invariants, such as diameter and chromatic number, can be understood using these eigenvalue techniques. In this talk, we bring these classical techniques in algebraic graph theory to the study of quantum walks. A system of interacting quantum qubits can be modelled by a quantum process on an underlying graph and is, in some sense, a quantum analogue of random walk. This gives rise to a rich connection between graph theory, linear algebra and quantum computing. In this talk, I will give an overview of applications of algebraic graph theory in quantum walks, as well as various recent results. In a recent paper with V. Schmeits, we show that the evolution of a general discrete-time quantum walk that consists of two reflections satisfies a Chebyshev recurrence, under a projection. We apply this to a model of discrete-time quantum walk proposed by H. Zhan [J. Algebraic Combin. 53(4):1187-1213, 2020], whose transition matrix is given by two reflections, using the face and vertex incidence relations of a graph embedded in an orientable surface. For the vertex-face walk, we prove theorems about perfect state transfer and periodicity and give infinite families of examples where these occur.

Chair: Gabriel Coutinho

Controllable Graphs

Chris Godsil
University of Waterloo, Canada

Plenary Talk 3: 26 Oct – 9:00am

Let $X$ be a graph on $n$ vertices with adjacency matrix $A$ . We say $X$ is controllable if $A$ and the all-ones matrix $J$ generate the algebra of all $n\times n$ real matrices. It is easy to see that regular graphs are not controllable. However O’Rourke Tourin proved a conjecture of mine, showing that the proportion of graphs on $n$ vertices that are controllable goes to one as $n\to\infty.$ Controllable graphs share many properties with random graphs, except that we can decide on polynomial time if a graph is controllable. I will outline some of the theory of controllable graphs, and sketch a proof that controllable graphs are vertex-reconstructible.

Chair: Krystal Guo

On eigenvalue bounds for the independence and chromatic
number of graph powers and their applications

Aida Abiad
Department of Mathematics and Computer Science,
Eindhoven University of Technology, The Netherlands

Plenary Talk 4: 26 Oct – 2:00pm

In this talk I will present several eigenvalue bounds on the independence number and the distance chromatic number of graph powers. We will see how to use polynomials and mixed-integer linear programming in order to optimize such bounds. Infinite families of graphs for which the new bounds are tight will be shown, and also some recent applications to coding theory will be discussed.

Chair: Carlos Hoppen

Structural and Spectral Properties of some Subclasses
of Chordal Graphs

Lilian Markenzon
Universidade Federal do Rio de Janeiro, Brasil

Plenary Talk 5: 26 Oct – 4:00pm

Structural properties of chordal graphs allow the development of efficient solutions for many theoretical and algorithmic problems. In this context, the clique-based structure and the minimal vertex separators play a decisive role. Considering these structures, we establish the relationship among some well-known subclasses of chordal graphs with important spectral properties, including threshold graphs, block graphs, indifference graphs, trivially chordal graphs, strictly chordal graphs and k-trees.

Chair: Claudia Justel

Rigidity and eigenvalues of graphs

Sebastian Cioaba
University of Delaware, USA

Plenary Talk 6: 27 Oct – 9:00am

Rigidity is the property of a structure that does not flex. It is well studied in discrete geometry and mechanics, and has applications in material sciences, engineering and biological sciences. In 1982, Lovasz and Yemini proved that every 6-connected graph is rigid. Consequently, if Fiedler’s algebraic connectivity is greater than 5, then $G$ is rigid. In recent work with Sean Dewar and Xiaofeng Gu, we showed that for a graph G with minimum degree $d>5$ , if its algebraic connectivity is greater than $2+1/(d-1)$ , then $G$ is rigid and if its algebraic connectivity is greater than $2+2/(d-1)$ , then $G$ is globally rigid. Our results imply that every connected regular Ramanujan graph with degree at least $8$ is globally rigid. Time permitting, I will report on another recent work with Sean Dewar, Georg Grasegger and Xiaofeng Gu extending these results to valencies smaller than $8.$

Chair: Jack Koolen.

Completion Problems for Kemeny’s Constant

Steve Kirkland
Department of Mathematics, University of Manitoba, Canada

Plenary Talk 7: 27 Oct – 2:00pm

Given an irreducible stochastic matrix, Kemeny’s constant measures the expected duration of a trip between randomly chosen states in the associated Markov chain. For this reason there is interest in identifying stochastic matrices for which the corresponding value of Kemeny’s constant is low. In this talk we consider the problem of completing a partially specified stochastic matrix so as to minimize Kemeny’s constant. We show that for any partially specified stochastic matrix for which the problem is well-defined, there is a minimizing completion that is as sparse as possible. We also discuss the completion problem in two special cases: all specified entries lie on the diagonal; and all specified entries lie in a common row.

Chair: Renata Del-Vecchio