From Séminaire Philippe Flajolet

Main: HomePage

Le Séminaire de Combinatoire Enumérative et Analytique, rebaptisé Séminaire Philippe Flajolet le 7 avril 2011, a pour objectif de couvrir un large spectre de recherche en combinatoire, et est ouvert à tou·te·s les chercheur·se·s et étudiant·e·s intéressé·e·s.

Il se tient habituellement un jeudi tous les deux mois à l'IHP, plus de détails ici. Il a actuellement lieu en virtuel.

Prochaine séance : Jeudi 3 juin 2021

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.

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).

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.

Liste des séances de l'année

Les séances de l'année 2020-2021 auront lieu :

Retrieved from http://semflajolet.math.cnrs.fr/index.php/Main/HomePage
Page last modified on April 20, 2021, at 12:38 PM