A Simple Explicit Construction of an $n^{\Tilde{O}(\log n)}$-Ramsey Graph

Details A Simple Explicit Construction of an $n^{\Tilde{O}(\log n)}$-Ramsey Graph A Simple Explicit Construction of an $n^{\Tilde{O}(\log n)}$-Ramsey Graph

2006-01-26

arxiv.org/abs/math/0601651v1

Mathematics

Combinatorics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

A Simple Explicit Construction of an $n^{\Tilde{O}(\log n)}$-Ramsey Graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Simple Explicit Construction of an $n^{\Tilde{O}(\log n)}$-Ramsey Graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Simple Explicit Construction of an $n^{\Tilde{O}(\log n)}$-Ramsey Graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-171286