Main.2020-2021 History

April 20, 2021, at 12:39 PM by 83.49.69.147 -

!!!!!! 3 juin 2021 [[#J030621]]

* 10h00 - 11h00 : '''Charlotte Hardouin (Institut de Mathématiques de Toulouse)''',  [[<<]] ''Marches dans le quart plan et familles de courbes elliptiques'' [[<<]] (:toggle id=hardouin init=hide button=0:).
>>id=hardouin resume<<
La nature algébrique des séries génératrices des marches dans le quart-plan  a connu de nombreuses approches: méthode du noyau, analyse des singularités, méthodes analytiques transcendantes, méthodes de guessing, invariants de Tutte et enfin  théorie de Galois différentielle. Dans cet exposé,  après avoir  donné un bref historique  sur les propriétés algébriques et différentielles de telles séries,  je  montrerai comment la  théorie de Galois différentielle et la méthode des invariants de Tutte développée par Olivier Bernardi,  Mireille Bousquet-Mélou et  Kilian Raschel peuvent s'articuler afin d'aboutir à un algorithme qui  associe à chaque modèle de marche à poids  dans le quart-plan un ensemble de relations algébriques entre les poids garantissant  l'existence d'une équation algébrique différentielle pour la série génératrice. [[<<]]
Ceci est une collaboration avec Michael Singer (NCSU).
>><<

* 11h00 - 12h00 : '''Kolja Knauer (Universitat Barcelona)''' [[<<]] ''On sensitivity in Cayley graphs'' [[<<]] (:toggle id=knauer init=hide button=0:).
>>id=knauer resume<<
Recently, Huang proved the Sensitivity Conjecture, by showing that every set of more than half the vertices of the $d$-dimensional hypercube $Q_d$ induces a subgraph of maximum degree at least $\sqrt{d}$. This is tight by a result of Chung, F\"uredi, Graham, and Seymour. Huang asked whether similar results can be obtained for other highly symmetric graphs. In this lecture we study Huang's question on Cayley graphs of groups.
[[<<]]
We show that high symmetry alone does not guarantee similar behavior and present three infinite families of Cayley graphs of unbounded degree that contain induced subgraphs of maximum degree $1$ on more than half the vertices. In particular, this refutes a conjecture of Potechin and Tsang, for which first counterexamples were shown recently by Lehner and Verret. The first family consists of dihedrants. The second family are star graphs, these are edge-transitive Cayley graphs of the symmetric group. All members of the third family are $d$-regular containing an induced matching on a $\frac{d}{2d-1}$-fraction of the vertices. This is largest possible and answers a question of Lehner and Verret.
[[<<]]
On the positive side, we consider Cayley graphs of Coxeter groups, where a lower bound similar to Huang's can be shown. A generalization of the construction of Chung, Füredi, Graham, and Seymour shows that this bound is tight for products of Coxeter groups of type $\mathbf{A_n}$, $\mathbf{I_n}(2k+1)$, most exceptional cases and not far from optimal in general.
Then, we show that also induced subgraphs on more than half the vertices of Levi graphs of projective planes and of the Ramanujan graphs of Lubotzky, Phillips, and Sarnak have unbounded degree. This yields more classes of Cayley graphs with properties similar to the ones provided by Huang's results. However, in contrast to Coxeter groups these graphs have no large subcubes.
[[<<]]
Joint with Ignacio Garcia-Marco.
>><<
April 06, 2021, at 04:25 PM by 83.49.69.147 -
Changed lines 8-9 from:
!!!!!! 1 octobre 2020 [[#J011020]] ([[https://www.tinyurl.com/bpnjcvce/ | videos de la séance]])
to:
!!!!!! 1 octobre 2020 [[#J011020]] ([[https://www.tinyurl.com/2zauaevr/ | videos de la séance]])
Changed line 24 from:
!!!!!! 3 décembre  2020 [[#J031220]] ([[https://www.tinyurl.com/2zauaevr/ | videos de la séance]])
to:
!!!!!! 3 décembre  2020 [[#J031220]] ([[https://www.tinyurl.com/bpnjcvce/ | videos de la séance]])
April 06, 2021, at 04:14 PM by 83.49.69.147 -
Changed lines 8-9 from:
!!!!!! 1 octobre 2020 [[#J011020]]
to:
!!!!!! 1 octobre 2020 [[#J011020]] ([[https://www.tinyurl.com/bpnjcvce/ | videos de la séance]])
Changed line 24 from:
!!!!!! 3 décembre  2020 [[#J031220]]
to:
!!!!!! 3 décembre  2020 [[#J031220]] ([[https://www.tinyurl.com/2zauaevr/ | videos de la séance]])
April 06, 2021, at 09:34 AM by 83.49.69.147 -
Changed line 53 from:
!!!!!! 1 avril 2021 [[#J010421]]
to:
!!!!!! 1 avril 2021 [[#J010421]] ([[http://www.tinyurl.com/3w542kxb/ | videos de la séance]])
April 01, 2021, at 11:12 AM by 83.49.69.147 -
Changed line 64 from:
* 11h00 - 12h00 : '''Stephen Melczer (University of Waterloo)''', [[<<]] ''An Invitation to Analytic Combinatorics in Several Variables'', [[<<]] (:toggle id=Melczer init=hide button=0:).
to:
* 11h00 - 12h00 : '''Stephen Melczer (University of Waterloo)''', [[<<]] ''An Invitation to Analytic Combinatorics in Several Variables'', [[<<]] (:toggle id=Melczer init=hide button=0:), [[Attach:Melczer-slides-IHP.pdf|Transparents]].
April 01, 2021, at 10:46 AM by 83.49.69.147 -
Changed line 64 from:
* 11h00 - 12h00 : '''Stephen Melczer (University of Waterloo)''' [[<<]] ''An Invitation to Analytic Combinatorics in Several Variables'', [[<<]] (:toggle id=Melczer init=hide button=0:).
to:
* 11h00 - 12h00 : '''Stephen Melczer (University of Waterloo)''', [[<<]] ''An Invitation to Analytic Combinatorics in Several Variables'', [[<<]] (:toggle id=Melczer init=hide button=0:).
April 01, 2021, at 10:42 AM by 83.49.69.147 -
Changed line 55 from:
* 10h00 - 11h00 : '''Mathilde Bouvel (CNRS, LORIA)''',  [[<<]] ''Limite en graphon des cographes aléatoires'' [[<<]] (:toggle id=Bouvel2 init=hide button=0:), [[Attach:Bouvel-slides-IHP-2.pdf|Transparents]].
to:
* 10h00 - 11h00 : '''Mathilde Bouvel (CNRS, LORIA)''',  [[<<]] ''Limite en graphon des cographes aléatoires'', [[<<]] (:toggle id=Bouvel2 init=hide button=0:), [[Attach:Bouvel-slides-IHP-2.pdf|Transparents]].
Changed line 64 from:
* 11h00 - 12h00 : '''Stephen Melczer (University of Waterloo)''' [[<<]] ''An Invitation to Analytic Combinatorics in Several Variables'' [[<<]] (:toggle id=Melczer init=hide button=0:).
to:
* 11h00 - 12h00 : '''Stephen Melczer (University of Waterloo)''' [[<<]] ''An Invitation to Analytic Combinatorics in Several Variables'', [[<<]] (:toggle id=Melczer init=hide button=0:).
April 01, 2021, at 10:40 AM by 83.49.69.147 -
Changed lines 18-19 from:

* 11h00 - 12h00 : '''Andrew Elvey-Price (CNRS, Université de Tours)''' [[<<]] ''Counting lattice walks by winding angle,'' [[<<]] (:toggle id=ElveyPrice init=hide button=0:), [[Attach:ElveyPrice-slides-IHP.pdf|Transparents]].
to:
* 11h00 - 12h00 : '''Andrew Elvey-Price (CNRS, Université de Tours)''', [[<<]] ''Counting lattice walks by winding angle,'' [[<<]] (:toggle id=ElveyPrice init=hide button=0:), [[Attach:ElveyPrice-slides-IHP.pdf|Transparents]].
Changed lines 22-23 from:
to:
\\
Changed line 31 from:
* 11h00 - 12h00 : '''Laurent Viennot (INRIA & IRIF)''' [[<<]] ''A trip through hub labeling in graphs,'' [[<<]] (:toggle id=LViennot init=hide button=0:).
to:
* 11h00 - 12h00 : '''Laurent Viennot (INRIA & IRIF)''', [[<<]] ''A trip through hub labeling in graphs,'' [[<<]] (:toggle id=LViennot init=hide button=0:).
Changed lines 35-36 from:
to:
\\
Changed lines 51-52 from:
to:
\\
Deleted line 63:
Changed lines 67-68 from:
>><<
to:
>><<
\\
April 01, 2021, at 10:11 AM by 83.49.69.147 -
Deleted lines 51-52:

Les exposés ont eu lieu en visioconférence. Le lien de connexion est [[https://bbb.lipn.univ-paris13.fr/b/bas-wsn-pcg-dri]] et le code d'accès 07084X où X est le premier chiffre après 2.
April 01, 2021, at 10:09 AM by 83.49.69.147 -
Changed lines 24-25 from:
!!!!!! Jeudi 3 décembre  2020 [[#J031220]]
to:
!!!!!! 3 décembre  2020 [[#J031220]]
Changed lines 36-37 from:
!!!!!! Jeudi 4 février 2021 [[#J040221]]
to:
!!!!!! 4 février 2021 [[#J040221]]
>><<

!!!!!! 1 avril 2021 [[#J010421]]

Les exposés ont eu lieu en visioconférence. Le lien de connexion est [[https://bbb.lipn.univ-paris13.fr/b/bas-wsn-pcg-dri]] et le code d'accès 07084X où X est le premier chiffre après 2.

* 10h00 - 11h00 : '''Mathilde Bouvel (CNRS, LORIA)''',  [[<<]] ''Limite en graphon des cographes aléatoires'' [[<<]] (:toggle id=Bouvel2 init=hide button=0:), [[Attach:Bouvel-slides-IHP-2.pdf|Transparents]].
>>id=Bouvel2 resume<<
Étant donnée une famille de graphes, une question naturelle (qui constitue un pan de la littérature en graphes aléatoires) est de décrire la forme limite d'un graphe pris uniformément au hasard dans cette famille. On étudiera cette question pour la famille des cographes, et on décrira leur limite (appelée le "cographon Brownien") dans le formalisme des graphons.
Dans l'exposé, je ne supposerai aucune connaissance préalable des cographes ni des graphons. J'en présenterai d'abord les définitions et quelques propriétés clés, notamment le codage des cographes par des "cotrees". Je décrirai les étapes principales de la preuve de la limite en graphon dans le cas des cographes étiquetés. Cette preuve utilise surtout de la combinatoire analytique sur les "cotrees".
Si le temps le permet, je mentionnerai plusieurs résultats associés, notamment la limite en graphon des cographes non-étiquetés, et des résultats parallèles dans le monde des permutations qui suggèrent une universalité du cographon Brownien.
[[<<]]
Travail en commun avec F. Bassino, V. Feray, L. Gerin, M. Maazoun, A. Pierrot.
>><<

* 11h00 - 12h00 : '''Stephen Melczer (University of Waterloo)''' [[<<]] ''An Invitation to Analytic Combinatorics in Several Variables'' [[<<]] (:toggle id=Melczer init=hide button=0:).
>>id=Melczer resume<<
The field of analytic combinatorics in several variables (ACSV) examines the asymptotic behaviour of multidimensional sequences using analytic properties of their (multivariate) generating functions. In addition to the tools used in the more classical univariate setting, the methods of ACSV rely on advanced results from complex analysis in several variables, topology, and algebraic and differential geometry -- giving the field a reputation for powerful methods which can be difficult for new researchers to get a firm grasp on. This talk aims to "demystify" ACSV by surveying some of its main results, software implementations, and recent applications of the theory. In addition, we show how these multivariate techniques can solve previously open problems on the asymptotic behaviour of univariate sequences and provide a significant new approach to attacking the "connection problem" for the asymptotics of D-finite functions.
March 07, 2021, at 10:30 PM by 83.49.69.147 -
Changed lines 12-15 from:
->Un méandre est la configuration topologique d'une droite et d'une courbe fermée simple dans le plan (la route et la rivière) qui s'intersectent transversalement, qu'on peut voir de façon (quasi) équivalente comme la configuration de deux courbes fermées simples transversales sur la sphère.  Ce point de vue permet de définir les méandres de genre g comme les configurations topologiques de deux courbes fermées simples s'intersectant transversalement sur des surfaces compactes de genre g (ces méandres de genre supérieur ont été introduits par Di Francesco-Golinelli-Guitter). On définit également les méandres orientés qui correspondent au cas où les courbes sont orientées et elles s'intersectent toujours dans le même sens (ils n'existent qu'en genre supérieur).
->Les développements récents sur l'énumération des surfaces à petits carreaux en grand genre, et la correspondance entre surfaces à petits carreaux à un cylindre horizontal et un cylindre vertical avec les méandres, permettent d'énumérer les méandres dans deux cas
-->- à combinatoire fixée (nombre d'arcs minimaux fixé), énumération des méandres de genre g quand le nombre d'intersections tend vers l'infini, et comportement asymptotique quand g tend vers l'infini
-->- énumération des méandres orientés de genre g quand le nombre d'intersections tend vers l'infini, et comportement asymptotique quand g tend vers l'infini.
to:
Un méandre est la configuration topologique d'une droite et d'une courbe fermée simple dans le plan (la route et la rivière) qui s'intersectent transversalement, qu'on peut voir de façon (quasi) équivalente comme la configuration de deux courbes fermées simples transversales sur la sphère.  Ce point de vue permet de définir les méandres de genre g comme les configurations topologiques de deux courbes fermées simples s'intersectant transversalement sur des surfaces compactes de genre g (ces méandres de genre supérieur ont été introduits par Di Francesco-Golinelli-Guitter). On définit également les méandres orientés qui correspondent au cas où les courbes sont orientées et elles s'intersectent toujours dans le même sens (ils n'existent qu'en genre supérieur).[[<<]]
Les développements récents sur l'énumération des surfaces à petits carreaux en grand genre, et la correspondance entre surfaces à petits carreaux à un cylindre horizontal et un cylindre vertical avec les méandres, permettent d'énumérer les méandres dans deux cas
->- à combinatoire fixée (nombre d'arcs minimaux fixé), énumération des méandres de genre g quand le nombre d'intersections tend vers l'infini, et comportement asymptotique quand g tend vers l'infini
->- énumération des méandres orientés de genre g quand le nombre d'intersections tend vers l'infini, et comportement asymptotique quand g tend vers l'infini.
Changed line 21 from:
->We count walks by winding angle around the origin on four different lattices. Our method uses a decomposition of each lattice, which allows us to write functional equations characterising generating functions for these walks. We then exactly solve these equations in terms of Jacobi theta functions, allowing us to extract asymptotic information about the associated counting sequences using methods popularised by Flajolet and Sedgewick. For each of the four lattices, we then use the reflection principle to count walks confined to cones such as the quarter plane and three quarter plane. On the square lattice, most of our results were derived by Timothy Budd in 2017 using a very different method, based on an explicit eigenvalue decomposition of certain matrices counting paths in the lattice.
to:
We count walks by winding angle around the origin on four different lattices. Our method uses a decomposition of each lattice, which allows us to write functional equations characterising generating functions for these walks. We then exactly solve these equations in terms of Jacobi theta functions, allowing us to extract asymptotic information about the associated counting sequences using methods popularised by Flajolet and Sedgewick. For each of the four lattices, we then use the reflection principle to count walks confined to cones such as the quarter plane and three quarter plane. On the square lattice, most of our results were derived by Timothy Budd in 2017 using a very different method, based on an explicit eigenvalue decomposition of certain matrices counting paths in the lattice.
Changed line 28 from:
->This talk will examine the rich topic of lattice path enumeration. A very classic object of combinatorics, lattice walks withstand study from a variety of perspectives. Even the simple task of classifying the two dimensional walks restricted to the first quadrant has brought into play a surprising diversity of techniques from algebra to analysis to geometry. We will consider walks under a few different lenses. We will see how lattice walks arise in algebraic combinatorics and group theory, and the impact of classification. We will show that a geometric perspective can offer a visual intuition of the role of weighted steps in enumeration formulas. We will also consider some of the existing recent developments using elliptic curves to unravel where the future may lie.
to:
This talk will examine the rich topic of lattice path enumeration. A very classic object of combinatorics, lattice walks withstand study from a variety of perspectives. Even the simple task of classifying the two dimensional walks restricted to the first quadrant has brought into play a surprising diversity of techniques from algebra to analysis to geometry. We will consider walks under a few different lenses. We will see how lattice walks arise in algebraic combinatorics and group theory, and the impact of classification. We will show that a geometric perspective can offer a visual intuition of the role of weighted steps in enumeration formulas. We will also consider some of the existing recent developments using elliptic curves to unravel where the future may lie.
Changed line 33 from:
->Hub labeling is a simple method for coding distances in a graph. It work surprisingly well in road networks where it offers a very compact representation of travel times between any two points and thus allows very fast computation of shortest paths. We will see a graph property called skeleton dimension  that explains such efficiency and that seems to fit with road networks. This method has been shown to work well also on various practical graphs. An intriguing problem in distributed computing resides in building such compact representation for sparse graphs in general. We will see that a family of sparse graphs requires almost quadratic space for any hub labeling. These graphs are connected to the Rusza-Szemerédi function counting induced matchings in dense graphs. We also relate the problem of finding more general distance labels for these graphs to the sum index problem in communication complexity, a second hint that representing distances with sub-quadratic space seems hard even in sparse graphs.
to:
Hub labeling is a simple method for coding distances in a graph. It work surprisingly well in road networks where it offers a very compact representation of travel times between any two points and thus allows very fast computation of shortest paths. We will see a graph property called skeleton dimension  that explains such efficiency and that seems to fit with road networks. This method has been shown to work well also on various practical graphs. An intriguing problem in distributed computing resides in building such compact representation for sparse graphs in general. We will see that a family of sparse graphs requires almost quadratic space for any hub labeling. These graphs are connected to the Rusza-Szemerédi function counting induced matchings in dense graphs. We also relate the problem of finding more general distance labels for these graphs to the sum index problem in communication complexity, a second hint that representing distances with sub-quadratic space seems hard even in sparse graphs.
March 06, 2021, at 10:06 PM by 83.49.69.147 -
Changed line 26 from:
* 10h00 - 11h00 : '''Marni Mishna (Simon Fraser University)''',  [[<<]] ''The Kaleidoscopic Splendor of Lattice Walk Enumeration , '' [[<<]] (:toggle id=Mishna2 init=hide button=0:),
to:
* 10h00 - 11h00 : '''Marni Mishna (Simon Fraser University)''',  [[<<]] ''The Kaleidoscopic Splendor of Lattice Walk Enumeration, '' [[<<]] (:toggle id=Mishna2 init=hide button=0:).
Changed line 31 from:
* 11h00 - 12h00 : '''Laurent Viennot (INRIA & IRIF)''' [[<<]] ''A trip through hub labeling in graphs ,'' [[<<]] (:toggle id=LViennot init=hide button=0:),
to:
* 11h00 - 12h00 : '''Laurent Viennot (INRIA & IRIF)''' [[<<]] ''A trip through hub labeling in graphs,'' [[<<]] (:toggle id=LViennot init=hide button=0:).
March 06, 2021, at 09:55 PM by 83.49.69.147 -
Changed line 5 from:
Le séminaire aura lieu les jeudis [[#J011020|1 octobre 2020]], [[#J031220|3 décembre 2020]], [[#J040221|4 février 2021]], [[#J010421|1 avril 2021]] et [[#J030621|3 juin 2021]].
to:
Le séminaire a eu lieu les jeudis [[#J011020|1 octobre 2020]], [[#J031220|3 décembre 2020]], [[#J040221|4 février 2021]], [[#J010421|1 avril 2021]] et [[#J030621|3 juin 2021]].
March 06, 2021, at 09:54 PM by 83.49.69.147 -
Deleted lines 25-26:
Les exposés auront lieu en visioconférence.

!!!!!! Jeudi 4 février 2021 [[#J040221]]

* 10h00 - 11h00 : '''Valentin Ovsienko (Laboratoire de Mathématiques de Reims)''',  [[<<]] ''Combinatorial and analytic properties of $q$-deformed real numbers'', [[<<]] (:toggle id=Ovsienko init=hide button=0:).
>>id=Ovsienko resume<<
I will explain a recent notion of $q$-deformed real numbers, and discuss its various combinatorial and analytic properties. A "$q$-deformed real" is a Laurent series in one variable, $q$, with integer coefficients. The subject is connected to different theories, such as knot invariants, continued fractions, and cluster algebras. I will formulate a challenging conjecture about the convergence of the series arising as $q$-deformed real numbers. (Here we understand $q$ as a complex variable.) The conjecture is proved in particular cases and concrete examples. In the most simple examples of $q$-Fibonacci and $q$-Pell numbers, the explicit formulas for the radius of convergence are very similar to certain formulas of Ramanujan. [[<<]]
The talk is based on a joint work with Ludivine Leclere, Sophie Morier-Genoud and Alexander Veselov.
>><<

* 11h00 - 12h00 : '''Ilse Fischer (Universität Wien)''', [[<<]] ''Bijective proofs of alternating sign matrix theorems'', [[<<]] (:toggle id=Fischer init=hide button=0:).
>>id=Fischer resume<<
Alternating sign matrices are known to be equinumerous with descending plane partitions, totally symmetric self-complementary plane partitions and alternating sign triangles, and their numbers are given by a simple product formula. For about 40 years now, combinatorialists have been trying to construct bijective proofs of these relations. [[<<]]
We present the first bijective proof of the enumeration formula for alternating sign matrices and of the fact that alternating sign matrices are equinumerous with descending plane partitions. Our constructions rely on signed sets, sijections and related notions such as a generalization of the Garsia-Milne involution principle. The starting point for these constructions are known “computational” proofs, but the combinatorial point of view led to several drastic modifications. We also provide computer code where all of our constructions have been implemented. [[<<]]
This is joint work with Matjaz Konvalinka.
>><<
%define=resume border="3px solid #c0c0c0" round padding=5px bgcolor=#dcdcdc %
!! 2020 - 2021
\\

Le séminaire aura lieu les jeudis [[#J011020|1 octobre 2020]], [[#J031220|3 décembre 2020]], [[#J040221|4 février 2021]], [[#J010421|1 avril 2021]] et [[#J030621|3 juin 2021]].
\\\

!!!!!! 1 octobre 2020 [[#J011020]]

* 10h00 - 11h00 : '''Élise Goujard (Institut de Mathématiques de Bordeaux)''',  [[<<]] ''Méandres en genre supérieur, '' [[<<]] (:toggle id=Goujard init=hide button=0:), [[Attach:Goujard-slides-IHP.pdf|Transparents]].
>>id=Goujard resume<<
->Un méandre est la configuration topologique d'une droite et d'une courbe fermée simple dans le plan (la route et la rivière) qui s'intersectent transversalement, qu'on peut voir de façon (quasi) équivalente comme la configuration de deux courbes fermées simples transversales sur la sphère.  Ce point de vue permet de définir les méandres de genre g comme les configurations topologiques de deux courbes fermées simples s'intersectant transversalement sur des surfaces compactes de genre g (ces méandres de genre supérieur ont été introduits par Di Francesco-Golinelli-Guitter). On définit également les méandres orientés qui correspondent au cas où les courbes sont orientées et elles s'intersectent toujours dans le même sens (ils n'existent qu'en genre supérieur).
->Les développements récents sur l'énumération des surfaces à petits carreaux en grand genre, et la correspondance entre surfaces à petits carreaux à un cylindre horizontal et un cylindre vertical avec les méandres, permettent d'énumérer les méandres dans deux cas
-->- à combinatoire fixée (nombre d'arcs minimaux fixé), énumération des méandres de genre g quand le nombre d'intersections tend vers l'infini, et comportement asymptotique quand g tend vers l'infini
-->- énumération des méandres orientés de genre g quand le nombre d'intersections tend vers l'infini, et comportement asymptotique quand g tend vers l'infini.
>><<

* 11h00 - 12h00 : '''Andrew Elvey-Price (CNRS, Université de Tours)''' [[<<]] ''Counting lattice walks by winding angle,'' [[<<]] (:toggle id=ElveyPrice init=hide button=0:), [[Attach:ElveyPrice-slides-IHP.pdf|Transparents]].
>>id=ElveyPrice resume<<
->We count walks by winding angle around the origin on four different lattices. Our method uses a decomposition of each lattice, which allows us to write functional equations characterising generating functions for these walks. We then exactly solve these equations in terms of Jacobi theta functions, allowing us to extract asymptotic information about the associated counting sequences using methods popularised by Flajolet and Sedgewick. For each of the four lattices, we then use the reflection principle to count walks confined to cones such as the quarter plane and three quarter plane. On the square lattice, most of our results were derived by Timothy Budd in 2017 using a very different method, based on an explicit eigenvalue decomposition of certain matrices counting paths in the lattice.
>><<

!!!!!! Jeudi 3 décembre  2020 [[#J031220]]

Les exposés auront lieu en visioconférence.

* 10h00 - 11h00 : '''Marni Mishna (Simon Fraser University)''',  [[<<]] ''The Kaleidoscopic Splendor of Lattice Walk Enumeration , '' [[<<]] (:toggle id=Mishna2 init=hide button=0:),
>>id=Mishna2 resume<<
->This talk will examine the rich topic of lattice path enumeration. A very classic object of combinatorics, lattice walks withstand study from a variety of perspectives. Even the simple task of classifying the two dimensional walks restricted to the first quadrant has brought into play a surprising diversity of techniques from algebra to analysis to geometry. We will consider walks under a few different lenses. We will see how lattice walks arise in algebraic combinatorics and group theory, and the impact of classification. We will show that a geometric perspective can offer a visual intuition of the role of weighted steps in enumeration formulas. We will also consider some of the existing recent developments using elliptic curves to unravel where the future may lie.
>><<

* 11h00 - 12h00 : '''Laurent Viennot (INRIA & IRIF)''' [[<<]] ''A trip through hub labeling in graphs ,'' [[<<]] (:toggle id=LViennot init=hide button=0:),
>>id=LViennot resume<<
->Hub labeling is a simple method for coding distances in a graph. It work surprisingly well in road networks where it offers a very compact representation of travel times between any two points and thus allows very fast computation of shortest paths. We will see a graph property called skeleton dimension  that explains such efficiency and that seems to fit with road networks. This method has been shown to work well also on various practical graphs. An intriguing problem in distributed computing resides in building such compact representation for sparse graphs in general. We will see that a family of sparse graphs requires almost quadratic space for any hub labeling. These graphs are connected to the Rusza-Szemerédi function counting induced matchings in dense graphs. We also relate the problem of finding more general distance labels for these graphs to the sum index problem in communication complexity, a second hint that representing distances with sub-quadratic space seems hard even in sparse graphs.
>><<