Bounding extremal functions of forbidden $0-1$ matrices using $(r,s)$-formations

Abstract

First, we prove tight bounds of $n{2}^{\frac{1}{(t-2)!}\alpha (n{)}^{t-2}\pm O(\alpha (n{)}^{t-3})}$ on the extremal function of the forbidden pair of ordered sequences $(123\dots k{)}^t$ and $(k\dots 321{)}^t$ using bounds on a class of sequences called $(r,s)$-formations. Then, we show how an analogous method can be used to derive similar bounds on the extremal functions of forbidden pairs of $0-1$ matrices consisting of horizontal concatenations of identical identity matrices and their horizontal reflections.

10 pages