# Constructions better than a random one.

I am interested in examples of constructions in the complexity theory which are better than a random constructions.

The only one example of such construction which I know is in the field of error-correcting codes. Algebraic-geometry codes are better in some range of parameters than a random codes.

One can easily to construct such artificial examples. I am interested in the examples like algebraic geometry codes, where it is easy make a random construction and it is not obvious how to do better.

• This question is horribly vague. Please at the very least state what field you are talking about. Mar 14 '11 at 17:14
• I added the [big-list] tag and flagged it for moderator attention asking them to make this question a community wiki. Mar 15 '11 at 14:40
• I like the question, but we might want to limit the scope somehow. It's clear that things like finite groups, projective planes, etc., if you parameterize them in the right way (number of triplets violating associativity, for example), will have much better parameters than random constructions. Mar 17 '11 at 15:36
• I agree that the question is vague. I do not how to limit the scope. Any suggestions are welcome. My interest is of the interesting examples. For example when for a long time the random construction was the best one and one need non-trivial ideas to beat it.
– Klim
Mar 19 '11 at 20:50
• @Dave, not sure if this needed to be a CW or [big-list] tag, if a question is vague we should ask the OP to clarify it, note that CW is irreversible. IMHO, a question like this can be modified in a way that it does need to be a big-list question. Mar 20 '11 at 9:00

Ramanujan graphs have second eigenvalue $\lambda_2\leq \frac{2\sqrt{D-1}}{D}$ (with $D$ the degree of the graph), while random graphs only achieve $\lambda_2\leq \frac{2\sqrt{D-1}}{D} + o(1)$ w.h.p. In fact, in general we have that $\lambda_2\geq \frac{2\sqrt{D-1}}{D} - o(1)$, with the $o(1)$ term going to $0$ with $D$ held constant (as the number of vertices $N\rightarrow \infty$), so in some sense these are optimal.
There is Behrend's construction of a large subset of $\{ 1,\ldots,N \}$ that contains no three elements in arithmetic progression (abbreviated 3AP-free). A random subset of $\{ 1,\ldots,N\}$ of size, say $N^{0.9}$ will contain lots of length-3 arithmetic progressions, but Behrend constructs a 3AP-free set of size $N^{1-o(1)}$.
This may not be quite what you're looking for, but Jeff Lagarias and I (later improved by Mackey) came up with cube tilings of high dimensional spaces that are counterexamples to Keller's conjecture, i.e. tilings of $n$ dimensions with unit cubes where no two cubes meet in a full ($n-1$)-dimensional face. It seems unlikely that random tilings will give counterexamples.