I will give an overview of some recent work on applying categorical methods in finite model theory and descriptive complexity. A key idea of a research program started by Abramsky, Dawar et al. in 2017 is that various forms of model comparison game, central to finite model theory, can be encoded as game comonads', i.e. resource-indexed comonads on the category of relational structures. For example, the following ingredients can be captured in a syntax-free way: Ehrenfeucht-Fraïssé games, fragments of first-order logic with bounded quantifier rank, and the combinatorial parameter of tree-depth. This approach covers also finite variable fragments, modal and guarded fragments, and more. The pattern of game comonads has been axiomatised at a general level in terms ofarboreal adjunctions', i.e. adjunctions between an extensional category (typically, in the examples, a category of relational structures) and a resource-indexed family of arboreal' categories. I will illustrate an application of this axiomatic framework to the study ofequi-resource' homomorphism preservation theorems in (finite) model theory, exemplified by Rossman's equirank homomorphism preservation theorem. If time allows, I will also discuss recent work on identifying the expressive power of arboreal adjunctions.
Artin et Pfister ont démontré que tout polynôme réel en n variables qui ne prend que des valeurs >=0 est somme de 2^n carrés de fonctions rationnelles. Après une introduction générale à cette thématique (le dix-septième problème de Hilbert), je présenterai des extensions de ce théorème à des corps de séries formelles ou de fonctions analytiques.
Dans ce séminaire nous étudions des classes d’arbres étiquetés selon différents modèles d’étiquetages croissants. Ces arbres sont utiles dans la modélisation de nombreux processus. Nous adoptons dans nos recherches différents points de vues complémentaires (combinatoire ou probabiliste) afin d’enrichir les résultats connus sur les arbres croissants classiques et de proposer de nouvelles classes d’arbres moins contraintes que les modèles existants dans la littérature.
A prototypical model for an age-structured diffusive population is considered in which individuals are distinguished by age and spatial position. The evolution equation involves a diffusion term for the space variable and a transport term for the age variable supplemented with a nonlocal boundary condition. The linear version of the model gives rise to a strongly continuous semigroup which exhibits the parabolic regularizing effects in the space variable. We determine its asymptotic behavior based on spectral properties of the associated generator. For a nonlinear version of the model we investigate the existence of nontrivial steady states and establish a principle of linearized stability.
Un pavage est un recouvrement du plan par des tuiles qui ne se chevauchent pas. On appelle sous-shift un ensemble de pavages qui est invariant par translation et fermé (pour la topologie habituelle sur les pavages). Ici on s’intéresse au cas où il y a un nombre fini de tuiles à translation près, les tuiles sont des losanges, et à chaque fois que deux tuiles sont adjacentes elle partagent soit un unique sommet en commun soit une arête entière en commun. Sur ces pavages, on peut imposer des règles locales (à la manière des tuiles de Wang) en ajoutant des couleurs sur les arêtes des tuiles avec la règle que deux tuiles qui partagent une arête doivent avoir la même couleur pour cette arête. Dans ce cas, pour une même tuile géométrique, on peut avoir plusieurs copies avec des couleurs différentes sur les arêtes. Étant donné un sous-shift X de pavages par losanges, le problème du domino sur X prend en entrée un ensemble fini de règles locales F et renvoie Vrai si il existe un pavage de X qui respecte les règles locales F et Faux dans le cas contraire. Ce problème est co-Récursivement-Énumérable-complet et nous allons présenter une réduction many-one depuis le problème du domino classique sur les tuiles de Wang.
Une équation différentielle algébrique est fortement minimale si tout sous-ensemble définissable de son ensemble de solutions (considéré dans un corps différentiel universel dans le langage des corps différentiel) est fini ou cofini. Dans mon exposé, je commencerai par présenter cette notion, son histoire et sa relation avec des énoncés de transcendence pour les solutions d’équations différentielles algébriques non linéaires. Je présenterai ensuite un résultat d’abondance pour les équations différentielles autonomes fortement minimales.
Soit (K, ν) un corps valué, les notions de valuation augmentée, de valuation augmentée limite et de famille admise de valuations permettent de donner une description de toute valuation μ de K[x] prolongeant ν. Dans le cas où le corps K est algébriquement clos cette description est particulièrement simple et nous pouvons la réduire aux notions de paire minimale et de famille pseudo-convergente. Soient (K, ν) un corps valué hensélien et ν' l’unique extension de ν à la clôture algébrique ̄K de K et soit μ une valuation de K[x] prolongeant ν, nous étudions les extensions ̄μ de μ à ̄K[x] et nous donnons une description des valuations ̄μ_i de ̄K[x] qui sont les extensions des valuations μ_i appartenant à la famille admise associée à μ.
Un problème classique dû à Abel est de déterminer si une équation différentielle y′ = ηy admet une solution non triviale y algébrique sur C(x) lorsque η est une fonction algébrique donnée sur C(x). Risch a produit un algorithme qui, étant donné η, détermine s'il existe une solution algébrique ou non. Dans un travail en commun avec Eric Delaygue (Lyon), nous avons donné un point de vue différent lorsque η admet un développement de Puiseux à coefficients rationnels en 0 : il existe une solution algébrique non triviale de y′=ηy si et seulement si les coefficients du développement de Puiseux de η en 0 satisfont les congruences de Gauss pour presque tous les nombres premiers. Nous avons appliqué notre critère afin de déterminer complètement les équations y′=ηy avec une solution algébrique lorsque xη(x) est une série hypergéométrique algébrique à paramètres rationnels, ce qui nous a permis de prouver une prédiction de Golyshev.
This talk has three parts. First, I want to explain how monoid acts can be viewed as models of computation. Second, I will sketch my thesis work on categories of actions of topological monoids. Third, if there is time, I would like to explain how this work would need to be extended in order to capture the monoid acts from the first part, point out some obstacles that need to be overcome, and give some intuition on what building such a topos-theoretic context could provide. Note that while I will give complexity-theoretic motivation, I want to apply this theory to monoid and group acts of all kinds, so feel free to ask questions about your favourite ones.
The notion of hypergraph has been introduced as a generalization of graphs so that each hyperedge is a subset of the set of vertices, without constraints on its cardinality. A widely investigated problem related both to graphs and to hypergraphs concerns the characterization and reconstruction from their degree sequences. Concerning graphs, this problem has been efficiently solved in 1960 by Erdos and Gallai, while no efficient solutions are possible in the case of hypergraphs, even in the simple case of 3-uniform ones, as shown in 2018 by Deza et al. So, to reduce the NP-hard core of the hypergraph reconstruction problem, we consider a class of degree sequences defined by Deza et al. that show interesting geometrical and algebraic properties. We propose some ideas on how use those properties to challenge the related reconstruction problem.
Nous rappellerons quelques tenants et aboutissants de l'étude des familles d'arcs sur une variété algébrique singulière, initiée par John Nash. Puis nous expliquerons des progrès récents, obtenus en collaboration avec Kevin Langlois et Hussein Mourtada, dans le cas où la variété est équipée d'une action de tore dont les orbites génériques sont de codimension 1.
Dans cet exposé j'introduirai les surfaces K3 et leurs groupes d'automorphismes, en particulier je montrerai comme la théorie des réseaux joue un rôle clé dans cette étude. Je montrerai des progrès récents sur les automorphismes qui agissent non-symplectiquement et qui sont d'ordre un multiple de sept. Il s'agit ici d'un des cas qui est encore ouvert en vue d'une classification complète des groupes d'automorphismes finis qui agissent sur les surfaces K3. Si le temps le permet je donnerai des exemples qui utilisent les fibrations elliptiques. Ces résultats sont obtenus en collaboration avec R. Bell, P. Comparin, J. Li, A. Rinc'on-Hidalgo, A. Zanardini.
Je présenterai des travaux récents qui mettent en scène des hypersurfaces cubiques projectives complexes de dimension trois et les revêtements cycliques ramifiés au-dessus, pour étudier la riche et belle géométrie de la variété de Fano des droites qu'ils contiennent et le comportement de l'automorphisme du revêtement lors de la dégénérescence vers une cubique à singularités isolées.
La conjecture 3n+1 est sans doute le problème ouvert actuel le plus élémentaire de toutes les mathématiques. En itérant la très simple fonction arithmétique T(n)= n/2 ou (3n+1)/2 selon que n est pair ou impair, on ne maîtrise plus grand chose sur l’évolution des trajectoires. En effet, on conjecture depuis des décennies que quel que soit l’entier de départ n0, on finira toujours par tomber sur 1. Mais il semble qu’on soit encore très loin de pouvoir le prouver. Le but de l’exposé est de présenter deux ou trois résultats partiels, tant théoriques qu’expérimentaux, sur ce problème.
Dans cet exposé, on montrera que toute variété algébrique réelle de dimension n contient des hypersurfaces algébriques réelles de degré d dont les nombres de Betti croissent en O(d^n), lorsque le degré d tend vers l’infini. Ceci est l'ordre de croissance maximal autorisé par l'inégalité de Smith-Thom. L’existence de telles hypersurfaces est obtenue à l’aide de techniques probabilistes.
I will be talking about simplicial sets, which are combinatorial objects widely used in topology. But this time, I'll explain how some of them can characterize graphs, and by extension categories. After defining what simplicial sets are, I will show how to associate to each graph a simplicial set, called its nerve. I will then give a nerve for partial order and categories as well. Then, we will study which simplicial sets arise as nerves from a category, given by the so- called Segal condition. Finally, I will show how to recover graphs, partial orders and categories from their nerve.