### Color critical hypergraphs and forbidden configurations

*Richard Anstee, Balin Fleming, Zoltán Füredi, Attila Sali*

#### Abstract

The present paper connects sharpenings of Sauer's bound on forbidden configurations with color critical hypergraphs. We define a matrix to be

*simple*if it is a (0,1)-matrix with no repeated columns. Let F be a k× l (0,1)-matrix (the forbidden configuration). Assume A is an m× n simple matrix which has no submatrix which is a row and column permutation of F. We define forb(m,F) as the best possible upper bound on n, for such a matrix A, which depends on m and F. It is known that forb(m,F)=O(mk) for any F, and Sauer's bond states that forb(m,F)=O(mk-1) fore*simple*F. We give sufficient condition for non-simple F to have the same bound using linear algebra methods to prove a generalization of a result of Lovász on color critical hypergraphs.Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page