On growth functions of ordered hypergraphs

Authors Jaroslav Hančl Jr., Martin Klazar

Publication date 21 May 2020

Abstract: For

k, l g e 2

we consider ideals of edge

l

-colored complete

k

-uniform hypergraphs

(n, c h i)

with vertex sets

[n] = 1, 2, d o t s n

for

n i n m a t h b b N

. An ideal is a set of such colored hypergraphs that is closed to the relation of induced ordered subhypergraph. We obtain analogues of two results of Klazar [arXiv:0703047] who considered graphs, namely we prove two dichotomies for growth functions of such ideals of colored hypergraphs. The first dichotomy is for any

k, l g e 2

and says that the growth function is either eventually constant or at least

n - k + 2

. The second dichotomy is only for

k = 3, 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 g e 23

at least as

G_{n}

where

G_{n}

is the sequence defined by

G_{1} = G_{2} = 1

,

G_{3} = 2

and

G_{n} = G_{n - 1} + G_{n - 3}

for

n g e 4

. The lower bounds in both dichotomies are tight.

This page was built for publication: On growth functions of ordered hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6341172)