Skip to Main content Skip to Navigation
Conference papers

Color critical hypergraphs and forbidden configurations

Abstract : The present paper connects sharpenings of Sauer's bound on forbidden configurations with color critical hypergraphs. We define a matrix to be \emphsimple 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(m^k)$ for any $F$, and Sauer's bond states that $forb(m,F)=O(m^k-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.
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam <>
Submitted on : Friday, August 14, 2015 - 11:39:09 AM
Last modification on : Friday, December 18, 2020 - 5:30:06 PM
Long-term archiving on: : Sunday, November 15, 2015 - 11:05:59 AM


Publisher files allowed on an open archive


  • HAL Id : hal-01184389, version 1



Richard Anstee, Balin Fleming, Zoltán Füredi, Attila Sali. Color critical hypergraphs and forbidden configurations. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.117-122. ⟨hal-01184389⟩



Record views


Files downloads