Back to Search
Start Over
Hereditary properties of hypergraphs
- 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.
- Subjects :
- Discrete mathematics
Hypergraph
Mathematics::Combinatorics
010102 general mathematics
0102 computer and information sciences
01 natural sciences
Graph
Theoretical Computer Science
Combinatorics
Monotone polygon
Computational Theory and Mathematics
Computer Science::Discrete Mathematics
010201 computation theory & mathematics
Discrete Mathematics and Combinatorics
Asymptotic formula
0101 mathematics
Hereditary property
Mathematics
Subjects
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