The number of hypergraphs and colored Hypergraphs with hereditary properties

2007/12/04 by Yoshiyasu Ishigami, Ishigami, Yoshiyasu
Mathematics · #05C65 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C65

paper · pdf · doi:10.48550/arxiv.0712.0425

9 pages

arxiv created 2007/12/04 · arxiv updated 2009/12/01

Abstract

As an application of Szemeredi's regularity lemma, Erdos-Frankl-Rodl (1986) showed that the number of graphs on vertex set 1,2,...n with a monotone class P is 2^{(1+o(1))ex(n,P)n2/2} where ex(n,P) is the maximum number of edges of an n-vertex graph which has no subgraph in P. Kohayakawa et al. (2003) extended it from monotone to hereditary and from graphs to 3-uniform hypergraphs. We extend it to general hypergraphs. This may be a simple example illustrating how to apply a recent hypergraph regularity lemma by the author.

Related

• Removal lemma for infinitely-many forbidden hypergraphs and property testing
• A Tight Bound for Hypergraph Regularity I
• Hypergraph regularity and the multidimensional Szemerédi theorem
• Some extremal problems for hereditary properties of graphs
• A Tight Bound for Hypergraph Regularity II