MODNET
Research Training Network in Model Theory
Publications > Preprint server > Preprint Number 1071

Preprint Number 1071

Previous Next Preprint server


1071. Caroline Terry
Structure and enumeration theorems for hereditary properties in finite relational languages
E-mail:

Submission date: 17 July 2016

Abstract:

Given a finite relational language L, a hereditary L-property is a class of finite L-structures which is closed under isomorphism and model theoretic substructure. This notion encompasses many objects of study in extremal combinatorics, including (but not limited to) hereditary properties of graphs, hypergraphs, and oriented graphs. In this paper, we generalize certain definitions, tools, and results form the study of hereditary properties in combinatorics to the setting of hereditary L-properties, where L is any finite relational language with maximum arity at least two. In particular, the goal of this paper is to generalize how extremal results and stability theorems can be combined with standard techniques and tools to yield approximate enumeration and structure theorems. We accomplish this by generalizing the notions of extremal graphs, asymptotic density, and graph stability theorems using structures in an auxiliary language associated to a hereditary L-property. Given a hereditary L-property H, we prove an approximate asymptotic enumeration theorem for H in terms of its generalized asymptotic density. Further we prove an approximate structure theorem for H, under the assumption of that H has a stability theorem. The tools we use include a new application of the hypergraph containers theorem (Balogh-Morris-Samotij, Saxton-Thomason) to the setting of L-structures, a general supersaturation theorem for hereditary L-properties (also new), and a general graph removal lemma for L-structures proved by Aroskar and Cummings.

Mathematics Subject Classification: 03C13 (Primary) 05A16, 05D99 (Secondary)

Keywords and phrases:

Full text arXiv 1607.04902: pdf, ps.


Last updated: August 10 2016 11:42 Please send your corrections to: