Number of the records: 1
Complexity of computations and proofs
- 1.
SYSNO ASEP 0021599 Document Type M - Monograph Chapter R&D Document Type Monograph Chapter Title Pseudorandom sets and explicit constructions of Ramsey graphs Title Pseudonáhodné množiny a ramseyovské grafy Author(s) Pudlák, Pavel (MU-W) RID, SAI
Rödl, V. (US)Source Title Complexity of computations and proofs. - Napoli : Dipartimento di Matematica della Seconda Universita di Napoli, 2004 / Krajíček J. - ISBN 88-7999-413-1 Pages s. 327-346 Number of pages 20 s. Language eng - English Country IT - Italy Keywords ramsey graphs ; explicit constructions Subject RIV BA - General Mathematics R&D Projects IAA1019401 GA AV ČR - Academy of Sciences of the Czech Republic (AV ČR) CEZ AV0Z1019905 - MU-W Annotation 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$. Workplace Mathematical Institute Contact Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Year of Publishing 2006
Number of the records: 1