Séminaires : Séminaire de Logique Lyon-Paris

Equipe(s) : lm,
Responsables :O. Finkel, T. Ibarlucía, A. Khélif, S. Rideau, A. Vignati
Email des responsables :
Salle : https://bigbluebutton.imj-prg.fr/b/sil-gwg-gge
Adresse :Sophie Germain
Description

ArchivesRetour ligne automatique
Abonnement à la liste de diffusion


Orateur(s) Caroline Terry - University of Chicago,
Titre Speeds of hereditary properties and mutual algebricity
Date13/05/2020
Horaire16:00 à 17:15
Diffusion
Résume

A hereditary graph property is a class of finite graphs closed under isomorphism and induced subgraphs.  Given a hereditary graph property H, the speed of H is the function which sends an integer n to the number of distinct elements in H with underlying set {1,...,n}.  Not just any function can occur as the speed of hereditary graph property.  Specifically, there are discrete ``jumps" in the possible speeds.  Study of these jumps began with work of Scheinerman and Zito in the 90's, and culminated in a series of papers from the 2000's by Balogh, Bollob\'{a}s, and Weinreich, in which essentially all possible speeds of a hereditary graph property were characterized.  In contrast to this, many aspects of this problem in the hypergraph setting remained unknown.  In this talk we present new hypergraph analogues of many of the jumps from the graph setting, specifically those involving the polynomial, exponential, and factorial speeds.  The jumps in the factorial range turned out to have surprising connections to the model theoretic notion of mutual algebricity, which we also discuss. 

This is joint work with Chris Laskowski.

Sallehttps://bigbluebutton.imj-prg.fr/b/sil-gwg-gge
AdresseSophie Germain
© IMJ-PRG