<p>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.</p>

CC BY-SA 2.5
2011-03-14T17:15:13.617Z
2011-03-14T17:15:13.617Z
alpoge
<p>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)}$.</p>

CC BY-SA 2.5
2011-03-15T00:27:56.873Z
2011-03-15T00:27:56.873Z
Luca Trevisan
<p>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 <a href="http://mathworld.wolfram.com/KellersConjecture.html" rel="nofollow">Keller's conjecture</a>, 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.</p>

CC BY-SA 2.5
2011-03-17T13:26:38.920Z
2011-03-17T14:09:57.650Z
2011-03-17T14:09:57.650Z
Peter Shor 
<p>In general, random constructions and greedy constructions achieve the same bounds (e.g., error correcting codes). Once I heard a talk by Lovasz where he said that greedy choices and random choices are essentially the same. So, any construction that beat the greedy construction should provide an answer to your question. As a quick example, construction that achieve the Sperner capacity of graphs are of this kind. As Peter Shor said, there are really lots of examples in extremal combinatorics.</p>

CC BY-SA 2.5
2011-03-17T16:39:55.030Z
2011-03-17T19:11:56.617Z
2011-03-17T19:11:56.617Z
Ugo
<p>I am interested in examples of constructions in the complexity theory which are better than a random constructions. </p>

<p>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.</p>

<p>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. </p>

CC BY-SA 2.5
2011-03-15T14:40:34.653Z
I added the [big-list] tag and flagged it for moderator attention asking them to make this question a community wiki.
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-17T15:36:38.887Z
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.
Peter Shor 
CC BY-SA 2.5
2011-03-19T20:50:30.550Z
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
CC BY-SA 2.5
2011-03-20T09:00:33.363Z
@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.
Kaveh
CC BY-SA 2.5
2011-03-14T17:14:33.477Z
This question is horribly vague. Please at the very least state what field you are talking about.
Dave Clarke
<reference-request><big-list><derandomization><pr.probability>
Constructions better than a random one.
Klim
# Constructions better than a random one.

(Asked by: username_0 on 2011-03-14)

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.

**Tags:** reference-request, big-list, derandomization, pr.probability
> **Comments:**
> **username_4**: This question is horribly vague. Please at the very least state what field you are talking about.  
> **username_1**: I added the [big-list] tag and flagged it for moderator attention asking them to make this question a community wiki.  
> **username_2**: 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.  
> **username_0**: 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.  
> **username_3**: @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.  

---

## 4 answers

### Answer by username_5 on 2011-03-14. Score: 11

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.


---

### Answer by username_6 on 2011-03-15. Score: 10

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


---

### Answer by username_2 on 2011-03-17. Score: 6

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](http://mathworld.wolfram.com/KellersConjecture.html), 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.


---

### Answer by username_7 on 2011-03-17. Score: 5

In general, random constructions and greedy constructions achieve the same bounds (e.g., error correcting codes). Once I heard a talk by Lovasz where he said that greedy choices and random choices are essentially the same. So, any construction that beat the greedy construction should provide an answer to your question. As a quick example, construction that achieve the Sperner capacity of graphs are of this kind. As Peter Shor said, there are really lots of examples in extremal combinatorics.


---

