Given a vector $\vec{x}$ in the null space of the adjacency matrix of a graph $G$, the support of $\vec{x}$ are the vertices which correspond to non-zero coordinates of $\vec{x}$. The support of $G$, $\Supp{G}$, is the union of the supports of all vectors in the null space of its adjacency matrix. The null decomposition of $G$, first introduced by Jaume and Molina in 2018, studies two subgraphs of $G$, $C_S(G)$, induced by the vertices in $\Supp{G}$ and their neighbours, and $C_N(G)$, induced by the remaining vertices.

In this talk, we study the null decomposition of bipartite graphs without cycles of length $0$ modulo $4$. We show that $C_S(G)$ contains a unique maximum independent set and that $C_N(G)$ contains a unique maximum matching. We use the decomposition to show that $\Supp{G}$ is the intersection of all maximum independent sets of $G$, and the union of the unmatched vertices over all maximum matchings. As an application, we present an algorithm that finds a sparse basis for the null space of adjacency matrix of forests in optimal time.

This talk is based on joint work with Daniel Jaume and Gonzalo Molina, from Universidad Nacional de San Luis, and Martin Safe, from Universidad Nacional del Sur.

Deuxième cours de Frédéric Magniez au Collège de France sur les Algorithmes quantiques (à 10h), suivi d'un exposé de Thomas Vidick sur « Certifier la génération de nombres aléatoires avec le quantique » (à 11h30). Informations supplémentaires : https://www.college-de-france.fr/site/frederic-magniez/course-2021-04-14-10h00.htm

The talk is based on joint work with Thomas Colcombet. We initiate a study of the expressive power of tree algebras, and more generally infinitely sorted algebras, based on their asymptotic complexity.

Tree algebras in many of their forms, such as clones, hyperclones, operads, etc, as well as other kind of algebras, are infinitely sorted: the carrier is a multi sorted set indexed by a parameter that can be interpreted as the number of variables or hole types. Finite such algebras - meaning when all sorts are finite - can be classified depending on the asymptotic size of the carrier sets as function of the parameter, that we call the complexity of the algebra. This naturally defines the notions of algebras of bounded, linear, polynomial, exponential or doubly exponential complexity…

Our main result precisely characterizes the tree algebras of bounded complexity based on the languages that they recognize as Boolean closures of simple languages. Along the way, we prove that such algebras that are syntactic are exactly those in which, as soon as there are sufficiently many variables, the elements are invariant under permutation of the variables.

We show that for any quantale Q, a Q-category is skeletal and complete if and only if it is injective with respect to fully faithful Q-functors. This is a special case of known theorems due to Hofmann and Stubbe, but we provide a different proof, using the characterisation of the MacNeille completion of a Q-category as its injective envelope.