Kombinatorika a grafy I, Jelínek 30.5.18

I30T4 at 2018-05-30 15:25:42

4 úlohy:

  1. 5 bodů
    Definujte latinský čtverec, ortogonalní čtverce + příklad o. čtverců řádu 3.

  2. 10 bodů
    Formulujte Singletonuv, Hamminguv a Gilbert-Varshamovuv odhad a jeden z nich dokažte.

  3. 5 bodů
    Formulujte Ramseyovu větu pro nekonečnou spocetnou množinu a definujte netrivialni pojmy z formulace.

  4. 10 bodů
    Formulujte a dokažte větu o nejdelším antiretezci na n-prvkové množině. (system nezávislých množin)

Znamkovani: po 5 bodech stupeň dolů, min 10 na ústní.