As was mentioned in the previous answers, the answer is no. Or more accurately I'd say that the answer is currently no, but possibly yes.
Also, consider the related question of constructing a bipartite graph with parts of size $2^n$, which contains no $K_{k,k}$ and whose complement contains no $K_{k,k}$ where $k = O(n)$. Such an explicit construction will have as far as I can tell huge impact on derandomization of randomized algorithms, among other topics in theoretical computer science. See e.g. this paper, where such an explicit construction is given for $k = 2^{n^{o(1)}}$.
You might also be interested in the following accompanying paper (seems like I cannot post it, being a new user; you can google it though, its title is "Pseudorandomness and Combinatorial Constructions") to Luca Trvisan's talk at ICM '06. This may contain more connections between explicit constructions of combinatorial objects and applications in theoretical computer science.
No comments:
Post a Comment