### Counting pattern-free set partitions. II: Noncrossing and other hypergraphs.

Skip to main content (access key 's'),
Skip to navigation (access key 'n'),
Accessibility information (access key '0')

Back to Simple Search
# Advanced Search

We investigate the extremal function $f(u,n)$ which, for a given finite sequence $u$ over $k$ symbols, is defined as the maximum length $m$ of a sequence $v={a}_{1}{a}_{2}...{a}_{m}$ of integers such that 1) $1\le {a}_{i}\le n$, 2) ${a}_{i}={a}_{j},i\ne j$ implies $|i-j|\ge k$ and 3) $v$ contains no subsequence of the type $u$. We prove that $f(u,n)$ is very near to be linear in $n$ for any fixed $u$ of length greater than 4, namely that $$f(u,n)=O\left(n{2}^{O\left(\alpha {\left(n\right)}^{\left|u\right|-4}\right)}\right).$$ Here $\left|u\right|$ is the length of $u$ and $\alpha \left(n\right)$ is the inverse to the Ackermann function and goes to infinity very slowly. This result extends the estimates in [S] and [ASS] which...

In the first part of the paper we are concerned about finite sequences (over arbitrary symbols) $u$ for which $Ex(u,n)=O\left(n\right)$. The function $Ex(u,n)$ measures the maximum length of finite sequences over $n$ symbols which contain no subsequence of the type $u$. It follows from the result of Hart and Sharir that the containment $ababa\prec u$ is a (minimal) obstacle to $Ex(u,n)=O\left(n\right)$. We show by means of a construction due to Sharir and Wiernik that there is another obstacle to the linear growth. In the second part of the paper we investigate whether...

**Page 1**