Počet záznamů: 1
Complexity of computations and proofs
- 1.
SYSNO ASEP 0021599 Druh ASEP M - Kapitola v monografii Zařazení RIV C - Kapitola v knize Název Pseudorandom sets and explicit constructions of Ramsey graphs Překlad názvu Pseudonáhodné množiny a ramseyovské grafy Tvůrce(i) Pudlák, Pavel (MU-W) RID, SAI
Rödl, V. (US)Zdroj.dok. Complexity of computations and proofs. - Napoli : Dipartimento di Matematica della Seconda Universita di Napoli, 2004 / Krajíček J. - ISBN 88-7999-413-1 Rozsah stran s. 327-346 Poč.str. 20 s. Jazyk dok. eng - angličtina Země vyd. IT - Itálie Klíč. slova ramsey graphs ; explicit constructions Vědní obor RIV BA - Obecná matematika CEP IAA1019401 GA AV ČR - Akademie věd CEZ AV0Z1019905 - MU-W Anotace We shall show a polynomial time construction of a graph $G$ on $N$ vertices such that $G$ does not contain $K_{r,r}$and$/overline{K}_{r,r}$, for $r=/sqrt{N}/{2^{/epsilon/sqrt{/log N}}}=o(/sqrt{N})$. To this end we construct a subset $X/subseteq F^m$ which has small intersections with all subspaces of dimension $m/2$. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2006
Počet záznamů: 1