Workshop Walks, Algebra, Combinatorics and Applications |
Combinatorics of nonbacktracking walks and non-cycling walks and their applications to network science (Slides)
In this talk we discuss how to count nonbacktracking walks in graphs, i.e., walks that do not present instances of the form
\(i \rightarrow j \rightarrow i\). We will show that one of the possible approaches, which is based on the Hashimoto matrix,
can be generalized to the non-cycling framework, thus allowing us to correctly count walks that not only avoid backtracking, but that also
avoid closed cycles of up to a given length \(k\). If time allows, we will describe some applications to centrality measures in
network science.
A chemist/spectroscopist discovering Path-Sum (Slides)
Solid state NMR (Nuclear Magnetic Resonance) spectroscopy allows to have an unequalled description of the local structure
and dynamics of materials. Spin dynamics is governed by the Liouville-von Neumann equation and the main goal is to extract
the time evolution of the evolution operator, U. In NMR, two theoretical approaches are usually used:
the Floquet theory (when the Hamiltonian of the system is periodic in time) and the Magnus expansion in the general case
(which can present severe convergence problems). In July 2017, I contacted P.-L. Giscard to ask him to explain the potentiality
of Path-Sum applied to the exact computation of the ordered exponential (Giscard, 2015). This resulted in the original treatment
of the Bloch-Siegert effect (Giscard, Bonhomme, 2020) and the most general Bloch equations (Bonhomme, Giscard, ENC, 2020)
using Path-Sum.
In this presentation, I will highlight all the advances obtained with Path-Sum in the treatment of spin dynamics.
I will also present the upcoming research in the framework of the ANR MAGICA 2020 (Bonhomme, Giscard, Pozza).
In particular, I will show that the Lanczos-Path-Sum approach (Giscard, Pozza, 2020) will allow to understand large
coupled spin systems such as those encountered in DNP (Dynamic Nuclear Polarization).
Promenade sur les chemins de Dyck (Slides)
On présentera des objets combinatoires très classiques et quelques unes de leurs nombreuses connexions,
qui vont des probabilités à la physique mathématique. On décrira en particulier plusieurs relations d'ordre partiel sur l'ensemble
de ces objets, classiques ou nouvelles. Parmi les propriétés remarquables de ces ordres partiels, on présentera des relations
surprenantes entre leurs intervalles et plusieurs types de cartes planes.
Parking trees (Slides)
In 1980, Edelman defined a poset on objects called noncrossing \(2\)-partitions, made of a partition and a noncrossing partition,
with a bijection linking parts of the same size in both partitions. Studying this poset, he proved that the number of noncrossing
\(2\)-partitions is given by \((n+1)^{n-1}\). This is also the number of classical combinatorial objects called parking functions.
After introducing noncrossing partitions, noncrossing \(2\)-partitions and parking functions,
we will draw the link between parking functions and noncrossing \(2\)-partitions, describing Edelman's poset in terms of parking
functions. Afterwards, we will (recall and) use the notion of species introduced in the early 1980s by Joyal to describe the
action of the symmetric group on a poset on parking trees. This is a joint work with Matthieu Josuat-Vergès.
New algebraic aspects of Losev-Manin moduli spaces
In early 2000s, Losev and Manin studied compactifications of the spaces of tuples of nonzero complex numbers modulo homotheties,
sometimes called the "sausage" compactifications. These spaces also happen to be the toric varieties associated to the Weyl chambers
of type A, and as such have been studied by Procesi about a decade earlier. I shall discuss some remarkable properties of an
algebraic structure on the collection of these spaces that has not been thoroughly studied before, that of a twisted associative
algebra. This is a by-product of an ongoing joint work with S.Shadrin and P.Tamaroff.
Trace monoids, hike monoids and number theory (Slides)
Trace monoids were originaly introduced by Cartier and Foata as monoids on the edges E of a graph G and with combinatorics described by
Viennot's heaps of pieces theory. They now accept a more general definition as right angled Artin-Tits monoid or partially commutative
monoids. Of particular interest are the submonoids of the original Cartier-Foata monoids composed only of words that have as many incoming
as outgoing edges for each graph vertex. Such a monoid is in bijection with the monoid formed by the oriented simple cycles of the graph G,
where two cycles commute if and only if they are vertex-disjoint on G. Thus, words in these monoids are collections of graph walks,
called hikes. The algebraic and combinatorial properties of hikes monoids are known to naturally extend number theory with all its objects
and relations maintained at a more general level offering new perspectives.
After a quick presentation of hike monoids and some of their properties, we address the open question of whether or not number theory
extends to all trace monoids. That is, whether or not a trace monoid T can always be seen as the monoid formed by the simple cycles
of a graph G ?
Algebraic structures on walks of graphs and algebraic reconstruction of the identity (Slides)
One of the goals of this in progress work made in collaboration with Foissy, Giscard and Ronco is to describe algebraically,
thanks to Hopf algebras, the reconstruction of any walk of a given graph from simple cycles and self-avoiding walks.
In this talk, we will first remind the definition of a combinatorial Hopf algebra. Then, we will present the Lawler's loop
erasing procedure, detail the construction of a co-pre-Lie coproduct on walks and explain how make walks into Hopf algebras.
Finally, we will explain how we can calculate an algebraic reconstruction of the identity by using the dual algebraic structure.
Families of algebraic structures
Algebraic structures may come into families, where each operation at hand is replaced by a family of operations indexed by some
parameter set, which often bears a semigroup structure. I will introduce Rota-Baxter families, then address other family structures
(dendriform, duplicial, pre-Lie,...), and finally give a general account of family algebras over a finitely presented linear operad,
this operad together with its presentation naturally defining an algebraic structure on the set of parameters.
Based on recent joint works with Loïc Foissy, Xing Gao and Yuanyuan Zhang.
Méthodes de Feynman-Kac trajectorielles
L'exposé abordera le problème de la simulation numérique des distributions trajectorielles de processus stochastiques,
et des variantes (distributions conditionnelles, filtrage, sampling de trajectoires satisfaisant des critères géométriques).
On insistera surtout sur les outils combinatoires et algébriques sous-jacents. Basé sur des travaux
avec P. del Moral, R. Kohn et S. Rubenthaler.
S-weak order and s-Permutohedra (Slides)
The weak order on permutations is classical objects of combinatorics. It is related to the permutohedra: a polytope obtained by
taking the convex hull of permutations seen as vertices in an \(n\) dimensional space. In this talk, we present a generalization of
this object: the \(s\)-Permutohedra motivated by some recent exploration of the generalizations of the Tamari lattice.
A Lanczos-like method for the time-ordered exponential (Slides)
The time-ordered exponential (TOE) is defined as the function that solves a system of coupled first-order linear differential
equations with generally non-constant coefficients. Despite being at the heart of many problems, the TOE remains elusively difficult
to evaluate. The path-sums method formulates any desired entry of a TOE as a branched continued fraction of finite depth and breadth,
and it has been successfully used to solve challenging quantum dynamic problems. However, while this approach can provide exact
(even analytical) expressions and is unconditionally convergent, it suffers from a complexity drawback. It requires finding all
the simple cycles and simple paths of a certain graph G, an #P-complete task. The \(^{\star}\)-Lanczos algorithm solves this issue by
effectively mapping G on a structurally simpler graph. On this graph, the path-sum solution takes the form of an ordinary, finite,
continued fraction.
A coupling of the spectral measures at a vertex (Slides)
I will introduce a particular coupling of the spectral measures at the vertices of a graph, whose moments count the rooted closed
paths in the graph. The resulting joint spectral measure verifies numerous interesting properties that allow to recover minors of
analytical functions of the adjacency matrix from its generalized moments. I'll prove an extension of Obata’s Central Limit Theorem
in growing star-graphs to the multivariate case and discuss some combinatorial properties using Viennot’s heaps of pieces point of
view.
Algebraic structures on graph associahedra (Slides)
Her abstract is available thanks to the link Abstract
Dirichlet distribution on decomposable graph (Slides)
We start by introducing the classical Dirichlet distribution and its related Beta Gamma algebra. After an introduction to
decomposable graph, we generalize the Dirichlet distribution to any finite decomposable graph, called Graph Dirichlet distribution.
We will discuss counterparts of some classical Bayesian statistics properties related to the Dirichlet distribution. Finally we
discuss its relation with MacMahon's master theorem.