A Simple Explicit Construction of an $n^{\Tilde{O}(\log n)}$-Ramsey Graph
| dc.creator | Barak, Boaz | |
| dc.date | 2006-01-26 | |
| dc.date.accessioned | 2026-07-07T06:59:20Z | |
| dc.date.available | 2026-07-07T06:59:20Z | |
| dc.description | We show a simple explicit construction of an $2^{\Tilde{O}(\sqrt{\log n})}$ Ramsey graph. That is, we provide a $\poly(n)$-time algorithm to output the adjacency matrix of an undirected $n$-vertex graph with no clique or independent set of size $2^{\e \sqrt{\log n}\log\log n}$ for every $\e>0$. Our construction has the very serious disadvantage over the well-known construction of Frankl and Wilson \cite{FranklWi81} that it is only explicit and not very explicit, in the sense that we do \emph{not} provide a poly-logarithmic time algorithm to compute the neighborhood relation. The main advantage of this construction is its extreme simplicity. It is also somewhat surprising that even though we use a completely different approach we get a bound which essentially equals the bound of \cite{FranklWi81}. This construction is quite simple and was obtained independently by others as well\footnote{P.~Pudlak, personal communications, July 2004.} but as far as we know has not been published elsewhere. | |
| dc.identifier | https://arxiv.org/abs/math/0601651 | |
| dc.identifier | http://arxiv.org/abs/math/0601651 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/107711 | |
| dc.subject | Combinatorics | |
| dc.title | A Simple Explicit Construction of an $n^{\Tilde{O}(\log n)}$-Ramsey Graph | |
| dc.type | text |