HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information

# 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.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [9 references]

https://hal.inria.fr/hal-01184389
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
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

### File

dmAE0123.pdf
Publisher files allowed on an open archive

### Citation

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, ⟨10.46298/dmtcs.3432⟩. ⟨hal-01184389⟩

Record views