Forbidden configurations: exact bounds determined by critical substructures (Q976694)

Summary: 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,\dots ,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 \(\text{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 \(\text{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 \(\text{forb}(m,F)\) is determined by \(\text{forb}(m,F')\) for some configuration \(F'\) contained in \(F\) and in that situation, with \(F'\) being minimal, we call \(F'\) a critical substructure.