Forbidden Families of Configurations

Abstract

A simple matrix is a (0,1)-matrix with no repeated columns. For a (0,1)-matrix $F$, we say that a (0,1)-matrix $A$ has $F$ as a configuration if there is a submatrix of $A$ which is a row and column permutation of $F$ (trace is the set system version of a configuration). Let $\ncols{A}$ denote the number of columns of $A$. Let $\mathcal{F}$ be a family of matrices. We define the extremal function $forb(m,{\cal F})=\max{\ncols{A} : A is m-rowed simple matrix and has no configuration F\in{\cal F}}$. We consider some families $\mathcal{F}=\{F_1,F_2,\dots ,F_t\}$ such that individually each $\forb(m,F_i)$ has greater asymptotic growth than $\forb(m,{\cal F})$.

18 pages

Cited by in corpus (2)

• Unavoidable Multicoloured Families of Configurations
• Multi-Symbol Forbidden Configurations