Sali Attila:
Pontos eredmények tiltott részkonfigurációkra
Absztrakt:
Az eloadásban Anstee, Ferguson, Griggs, Kamoosi és Sali
által megkezdett munkát folytatjuk. Egy (0,1)-mátrix egyszeru, ha nem
tartalmaz ismételt oszlopokat. Legyen $F$ egy $k\times l$ (0,1)-mátrix, és
tegyük fel, hogy az $A$ $m\times n$ egyszeru mátrixnak nincs olyan
részmátrixa, ami $F$ valamely sor és oszlop permutációja lenne. Ekkor azt
mondjuk, hogy $A$-nak nincs $F$ (tiltott) részkonfigurációja.
Halmazrendszeres
megfogalmazásban nyomnak is szokták nevezni. $\forb(m,F)$ a legngyobb olyan
$n$, amelyre egy ilyen $A$ létezik.
Definiáljuk az $F_{abcd}$ $(a+b+c+d)\times 2$ mátrixot úgy, hogy $a$ darab
$[11]$ sort, $b$ darab $[10]$ sort, $c$ darab $[01]$ sort és $d$ darab
$[00]$ sort tartalmaz. $F_{2110}$ kivételével pontos korlátot adunk az
összes
$4\times 2$ $F_{abcd}$-re. Például $\forb(m,F_{0220})=\binom{m}{2}+2m-1$,
itt a tiltott részkonfiguráció
Kleitman egy tételével áll rokonságban. $F_{2110}$-el kapcsolatos
eredményeink
alapján az látszik, hogy a kérdés design-okkal áll szoros kapcsolatban.
Az eredmények Richard Anstee-val és Farzin Barekat-tal közösek.