Complexity of computations and proofs

0021599 - MÚ 2006 RIV IT eng M - Monography Chapter
Pudlák, Pavel - Rödl, V.
Pseudorandom sets and explicit constructions of Ramsey graphs.
[Pseudonáhodné množiny a ramseyovské grafy.]
Complexity of computations and proofs. Napoli: Dipartimento di Matematica della Seconda Universita di Napoli, 2004 - (Krajíček, J.), s. 327-346. Quaderni di matematica, 13. ISBN 88-7999-413-1
R&D Projects: GA AV ČR(CZ) IAA1019401
Institutional research plan: CEZ:AV0Z1019905
Keywords : ramsey graphs * explicit constructions
Subject RIV: BA - General Mathematics

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$.

Ukazujeme casově polynomiální konstrukci grafu $G$ na $N$ vrcholech takovou, že $G$ neobsahuje $K_{r,r}$ ani $/overline {K}_{r,r}$, pro $r=/sqrt{N}/{2^{/epsilon/sqrt{/log N}}}=o(/sqrt{N})$. K tomuto účelu sestrojíme podmnožinu $X/subseteq F^m$, která má malé průniky se všemi podprostory dimenze $m/2$.
Permanent Link: http://hdl.handle.net/11104/0110538