10
$\begingroup$

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.

$\endgroup$
  • 7
    $\begingroup$ This question is horribly vague. Please at the very least state what field you are talking about. $\endgroup$ – Dave Clarke Mar 14 '11 at 17:14
  • $\begingroup$ I added the [big-list] tag and flagged it for moderator attention asking them to make this question a community wiki. $\endgroup$ – Tsuyoshi Ito Mar 15 '11 at 14:40
  • 4
    $\begingroup$ 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. $\endgroup$ – Peter Shor Mar 17 '11 at 15:36
  • $\begingroup$ 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. $\endgroup$ – Klim Mar 19 '11 at 20:50
  • $\begingroup$ @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. $\endgroup$ – Kaveh Mar 20 '11 at 9:00
11
$\begingroup$

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.

$\endgroup$
10
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.