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

Equipe(s) : lm,
Responsables :S. Anscombe, O. Finkel, A. Khélif, S. Rideau, T. Tsankov, A. Vignati
Email des responsables :
Salle : Contacter Silvain Rideau ou Alessandro Vignati
Adresse :

ArchivesRetour ligne automatique
Abonnement à la liste de diffusion

Orateur(s) Caroline Terry - University of Chicago,
Titre Speeds of hereditary properties and mutual algebricity
Horaire16:00 à 17:15

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.

SalleContacter Silvain Rideau ou Alessandro Vignati