Back to Search Start Over

Hereditary properties of hypergraphs

Authors :
Brendan Nagle
Ryan Dotson
Source :
Journal of Combinatorial Theory, Series B. 99(2):460-473
Publication Year :
2009
Publisher :
Elsevier BV, 2009.

Abstract

A hereditary property P^(^k^) is a class of k-graphs closed under isomorphism and taking induced sub-hypergraphs. Let P"n^(^k^) denote those k-graphs of P^(^k^) on vertex set {1,...,n}. We prove an asymptotic formula for log"2|P"n^(^k^)| in terms of a Turan-type function concerning forbidden induced sub-hypergraphs. This result complements several existing theorems for hereditary and monotone graph and hypergraph properties.

Details

ISSN :
00958956
Volume :
99
Issue :
2
Database :
OpenAIRE
Journal :
Journal of Combinatorial Theory, Series B
Accession number :
edsair.doi.dedup.....3e8832bdff056c218dddd85e2a87e0e6
Full Text :
https://doi.org/10.1016/j.jctb.2008.09.004