Charles Explorer logo
🇨🇿

A jump to the Narayana number for hereditary properties of ordered 3-uniform hypergraphs

Publikace na Matematicko-fyzikální fakulta |
2023

Tento text není v aktuálním jazyce dostupný. Zobrazuje se verze "en".Abstrakt

For k, l >= 2 we consider ideals of edge l-colored complete k-uniform hypergraphs (n, x) with vertex sets [n] = {1, 2, ... n} for n is an element of N. An ideal is a set of such colored hypergraphs that is closed under the induced ordered sub-hypergraph relation.

We obtain analogues of two results of Klazar (2010) who considered graphs, namely we prove two jumps for growth functions of such ideals of colored hypergraphs. The first jump is for any k, l >= 2 and says that the growth function is either eventually constant or at least n - k + 2.

The second jump is only for k = 3 and l = 2 and says that the growth function of an ideal of edge two-colored complete 3-uniform hypergraphs grows either at most polynomially, or for n >= 23 at least as Gn where Gn is the sequence defined by G1 = G2 = 1, G3 = 2 and Gn = Gn-1 + Gn-3 for n >= 4. The lower bounds in both jumps are tight. (c) 2023 Elsevier Ltd.

All rights reserved.