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 of the rows and columns of its -adjacency matrix . If is the bipartite adjacency matrix of a bipartite graph, then an isomorphism leaving its bipartition invariant is equivalent to an independent permutation of its rows and columns. We shall explore some properties of -matrices that avoid or force certain patterns in the permutation matrices it contains, thus properties of perfect matchings in its corresponding bipartite graph.
Chair: Vilmar Trevisan
Algebraic graph theory and quantum walks
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
University of Waterloo, Canada
Plenary Talk 3: 26 Oct – 9:00am
Let be a graph on vertices with adjacency matrix . We say is controllable if and the all-ones matrix generate the algebra of all 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 vertices that are controllable goes to one as 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
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
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
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 is rigid. In recent work with Sean Dewar and Xiaofeng Gu, we showed that for a graph G with minimum degree , if its algebraic connectivity is greater than , then is rigid and if its algebraic connectivity is greater than , then is globally rigid. Our results imply that every connected regular Ramanujan graph with degree at least 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
Chair: Jack Koolen.
Completion Problems for Kemeny’s Constant
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