×

Hereditary properties of hypergraphs. (English) Zbl 1219.05104

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

MSC:

05C65 Hypergraphs
05C75 Structural characterization of families of graphs
PDF BibTeX XML Cite
Full Text: DOI Link

References:

[1] Alekseev, V.E., On the entropy values of hereditary classes of graphs, Discrete math. appl., 3, 191-199, (1993) · Zbl 0797.05077
[2] Bollobás, B.; Thomason, A., Projections of bodies and hereditary properties of hypergraphs, Bull. London math. soc., 27, 417-424, (1995) · Zbl 0836.05072
[3] Bollobás, B.; Thomason, A., Hereditary and monotone properties of graphs, (), 70-78 · Zbl 0866.05030
[4] R. Dotson, An application of the hypergraph regularity method, Master’s thesis, University of Nevada, Reno, Department of Mathematics and Statistics, 2005
[5] G. Elek, B. Szegedy, Limits of hypergraphs, removal and regularity lemmas. A non-standard approach, submitted for publication
[6] Erdős, P.; Frankl, P.; Rödl, V., Asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent, Graphs combin., 2, 113-121, (1986) · Zbl 0593.05038
[7] Erdős, P.; Kleitman, D.J.; Rothschild, B.L., Asymptotic enumeration of \(K_n\)-free graphs, (), 19-27
[8] Erdős, P.; Stone, A.H., On the structure of linear graphs, J. bull. amer. math. soc., 52, 1087-1091, (1946) · Zbl 0063.01277
[9] Frankl, P.; Rödl, V., Extremal problems on set systems, Random structures algorithms, 20, 2, 131-164, (2002) · Zbl 0995.05141
[10] Gowers, W.T., Quasirandomness, counting and regularity for 3-uniform hypergraphs, Combin. probab. comput., 15, 1-2, 143-184, (2006) · Zbl 1082.05081
[11] Gowers, W.T., Hypergraph regularity and the multidimensional Szemerédi theorem, Ann. of math. (2), 166, 3, 897-946, (2007) · Zbl 1159.05052
[12] Haxell, P.; Nagle, B.; Rödl, V., An algorithmic version of the hypergraph regularity method, (), 439-448 · Zbl 1152.05048
[13] Haxell, P.; Nagle, B.; Rödl, V., An algorithmic version of the hypergraph regularity method, SIAM J. comput., 37, 6, 1728-1776, (2008) · Zbl 1152.05048
[14] Ishigami, Y., The number of hypergraphs and colored hypergraphs with hereditary properties, (2007)
[15] Kohayakawa, Y.; Nagle, B.; Rödl, V., Hereditary properties of triple systems, Combin. probab. comput., 12, 155-189, (2003) · Zbl 1027.05072
[16] Nagle, B.; Rödl, V., The asymptotic number of triple systems not containing a fixed one, Discrete math., 235, 271-290, (2001) · Zbl 0977.05018
[17] Nagle, B.; Rödl, V.; Schacht, M., The counting lemma for regular k-uniform hypergraphs, Random structures algorithms, 28, 2, 113-179, (2006) · Zbl 1093.05045
[18] Nagle, B.; Rödl, V.; Schacht, M., Extremal hypergraph problems and the regularity method, (), 247-278 · Zbl 1116.05041
[19] Prömel, H.J.; Steger, A., Excluding induced subgraphs: quadrilaterals, Random structures algorithms, 2, 55-71, (1991) · Zbl 0763.05046
[20] Prömel, H.J.; Steger, A., The asymptotic number of graphs not containing a fixed color-critical subgraph, Combinatorica, 12, 463-473, (1992) · Zbl 0770.05063
[21] Prömel, H.J.; Steger, A., Excluding induced subgraphs III. A general asymptotic, Random structures algorithms, 3, 1, 19-31, (1992) · Zbl 0751.05041
[22] Prömel, H.J.; Steger, A., The asymptotic structure of H-free graphs, (), 167-178 · Zbl 0838.05070
[23] Rödl, V.; Nagle, B.; Skokan, J.; Schacht, M.; Kohayakawa, Y., The hypergraph regularity method and its applications, Proc. natl. acad. sci. USA, 102, 23, 8109-8113, (2005) · Zbl 1135.05307
[24] Rödl, V.; Schacht, M., Regular partitions of hypergraphs: regularity lemmas, Combin. probab. comput., 16, 6, 833-885, (2007) · Zbl 1206.05071
[25] Rödl, V.; Schacht, M., Regular partitions of hypergraphs: counting lemmas, Combin. probab. comput., 16, 6, 887-901, (2007) · Zbl 1206.05072
[26] Rödl, V.; Skokan, J., Regularity lemma for k-uniform hypergraphs, Random structures algorithms, 25, 1, 1-42, (2004) · Zbl 1046.05042
[27] Scheinerman, E.; Zito, J., On the size of hereditary classes of graphs, J. combin. theory ser. B, 61, 16-39, (1994) · Zbl 0811.05048
[28] Szemerédi, E., On sets of integers containing no k elements in arithmetic progression, Acta arith., 27, 199-245, (1975), collection of articles in memory of Juriĭ Vladimirovič Linnik · Zbl 0303.10056
[29] Szemerédi, E., Regular partitions of graphs, (), 399-401
[30] Tao, T., A variant of the hypergraph removal lemma, J. combin. theory ser. A, 113, 7, 1257-1280, (2006) · Zbl 1105.05052
[31] Turán, P., An extremal problem in graph theory, Mat. fiz. lapok, 48, 436-452, (1941), (in Hungarian)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.