$\parbox{7cm}{ {\Huge\bf SEMINARIUM}}$
Matematyka Dyskretna
(prowadzone przez M.Woźniaka)

UWAGA!!!  UWAGA!!!  UWAGA!!!

Spotkanie nadzwyczajne!  termin wyjątkowy! miejsce niezwykłe!

W czwartek, 7 października 2004 roku, o godzinie 16:00

w Instytucie Matematycznym PAN, ul. 14w. Tomasza 30

Dalibor FRONCEK

(Czechy i USA)

wygłosi referat pod tytułem:

Biclique coverings of $K_{n,n} - M$

and Sperner Theorem

Joint work with Janja Jerebic, Sandi Klavzar, University of Maribor and Petr Kovar, Technical University of Ostrava

The strong product $H=\boxtimes _{\,i=1}^{\,k}H_i$ of graphs $H_1, H_2,\dots ,H_k$ is the graph defined on the Cartesian product of the vertex sets of the factors, two distinct vertices $(u_1,u_2,\dots ,u_k)$ and $(v_1,v_2,\dots ,v_k)$ being adjacent if and only if $u_i$ is equal or adjacent to $v_i$ in $H_i$ for $i=1,2,\dots ,k$. The strong isometric dimension, $\idim (G)$, of a graph $G$ is the least number $k$ such that there is a set of paths $\{ P^{(1)},P^{(2)},\dots ,P^{(k)}\}$ with the property that $G$ isometrically embeds into $\boxtimes _{\, i=1}^{\, k}P^{(i)}$.

Jerebic and Klavzar conjectured that if $k\geq 1$ and ${ { \dbinom{k}{\lfloor{\frac{k}{2}\rfloor}} } <n\leq { \dbinom{k+1}{\lfloor{\frac{k+1}{2}\rfloor}} } }$ then $\idim (K_2\,\square\medspace K_n)=k+1$. They also proved that the conjecture is equivalent to the following

Conjecture (Jerebic, Klavzar 2003)
Let $k\geq 1$ and let $%%\displaystyle { n= { \dbinom{k+1}{\lfloor{\frac{k+1}{2}\rfloor}} } +1 }$. Then the edges of $K_{n,n} - M$, where $M$ is the perfect matching, cannot be covered by $k$ complete bipartite graphs.

We use Sperner Theorem to prove the conjecture. If time permits, we also present some related results.

Serdecznie zapraszamy wszystkich chętnych !