A következő kombinatorika szeminárium
<P><CENTER>
          november 10, 10:00, Riesz terem
</CENTER>
előadása:

<P><CENTER>
Nagy V. Gábor: 
<B>$\Gamma$-mentes 0-1 mátrixok bijektív leszámlálása</B>
</CENTER>

<P>
Bényi Beáta és Hajnal Péter 2015-ben igazolták, hogy azon nxk-as
0-1 mátrixok száma, amelyek nem tartalmaznak sem $1 0 \\ 0 1$, sem
$0 1 \\ 1 0$ 2x2-es részmátrixot, megegyezik azon nxk-as 0-1
mátrixok számával, amelyek nem tartalmaznak sem $1 1 \\ 1 0$, sem
$1 1 \\ 1 1$ 2x2-es részmátrixot. (Mindkét mátrixosztályt a B_n^(-k)
poly-Bernoulli-szám számolja meg.) Erre az eredményre adunk új bijektív
bizonyítást. A második osztály mátrixait nevezzük $Gamma$-mentes
mátrixoknak; ezek összeszámlálása a nehezebb, főleg erről lesz szó.

<P>
Végül, amennyire az idő engedi, a kidolgozott bijekció egy alkalmazását
szeretném bemutatni.
Nevezzünk egy nxn-es 0-1 mátrixot szépnek, ha
<UL>
<LI>
$Gamma$-mentes,
<LI>
nincs csupa-0 sora és oszlopa, továbbá
<LI>
a mátrix minden 1-esére teljesül, hogy vagy (a sorában) tőle balra is
és (az oszlopában) felette is van 1-es valahol, vagy se tőle balra, se
felette nincs 1-es.
</UL>
Az \alpha,\beta \in S_n permutációkból álló (\alpha,\beta) pár
közösemelkedés-mentes, ha nincs olyan 1 <= i <= n-1 index, amelyre
\alpha(i) < \alpha(i+1) és \beta(i) < \beta(i+1) egyszerre teljesül.
Aval et al. 2014-es észrevétele szerint az nxn-es szép 0-1 mátrixok
száma megegyezik az {1,...,n} alaphalmaz közösemelkedés-mentes
permutációpárjai számával. Ezen eredmény új bijektív bizonyítását
ismertetem.

<P>
A fentiek közös eredmények Bényi Beátával.

<P>
Mindenkit szeretettel várunk, Péter