Geodesic
Color critical hypergraphs and forbidden configurations
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) (2005).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2005_special_250_a41,
     author = {Anstee, Richard and Fleming, Balin and F\"uredi, Zolt\'an and Sali, Attila},
     title = {Color critical hypergraphs and forbidden configurations},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
     year = {2005},
     doi = {10.46298/dmtcs.3432},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3432/}
}
TY  - JOUR
AU  - Anstee, Richard
AU  - Fleming, Balin
AU  - Füredi, Zoltán
AU  - Sali, Attila
TI  - Color critical hypergraphs and forbidden configurations
JO  - Discrete mathematics & theoretical computer science
PY  - 2005
VL  - DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3432/
DO  - 10.46298/dmtcs.3432
LA  - en
ID  - DMTCS_2005_special_250_a41
ER  - 
%0 Journal Article
%A Anstee, Richard
%A Fleming, Balin
%A Füredi, Zoltán
%A Sali, Attila
%T Color critical hypergraphs and forbidden configurations
%J Discrete mathematics & theoretical computer science
%D 2005
%V DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3432/
%R 10.46298/dmtcs.3432
%G en
%F DMTCS_2005_special_250_a41
Anstee, Richard; Fleming, Balin; Füredi, Zoltán; Sali, Attila. Color critical hypergraphs and forbidden configurations. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) (2005). doi : 10.46298/dmtcs.3432. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3432/

Cité par Sources :