Forbidden configurations: exact bounds determined by critical substructures

R. P. Anstee ; S. N. Karp

The electronic journal of combinatorics, Tome 17 (2010)

Résumé

We consider the following extremal set theory problem. Define a matrix to be simple if it is a (0,1)-matrix with no repeated columns. An $m$-rowed simple matrix corresponds to a family of subsets of $\{1,2,\ldots ,m\}$. Let $m$ be a given integer and $F$ be a given (0,1)-matrix (not necessarily simple). We say a matrix $A$ has $F$ as a configuration if a submatrix of $A$ is a row and column permutation of $F$. We define $\hbox{forb}(m,F)$ as the maximum number of columns that a simple $m$-rowed matrix $A$ can have subject to the condition that $A$ has no configuration $F$. We compute exact values for $\hbox{forb}(m,F)$ for some choices of $F$ and in doing so handle all $3\times 3$ and some $k\times 2$ (0,1)-matrices $F$. Often $\hbox{forb}(m,F)$ is determined by $\hbox{forb}(m,F')$ for some configuration $F'$ contained in $F$ and in that situation, with $F'$ being minimal, we call $F'$ a critical substructure.

Détail

DOI : 10.37236/322

Classification : 05D05
Mots-clés : VC-dimension, (0, 1)-matrices, forbidden configurations, trace