See my post on AoPS

Edit: OK, reposting here.

The first step toward the solution, as it often happens, is to generalize the problem. Instead of just one set $A$, we shall consider $3$ sets $A,B,C$ of cardinalities $|A|,|B|,|C|$ and will try to prove that there exist $a\in A,b\in B,c\in C$ such that $[a,b,c]\ge\sigma |A|\cdot|B|\cdot|C|$.

The reason for such generalization is that we are going to employ the usual "minimal counterexample" technique
(a.k.a. "infinite descent", etc.) and we have much more freedom if we are allowed to modify three different sets independently rather than just one of them.

Our first attempt will be to make the reduction modulo $p^k$ where $p$ is a prime and $k\ge 1$ is an integer. Let $A_{p,k}=\{a\in A: v_p(a)=k\}$ where, as usual, $v_p(a)=\max\{v:p^v\mid a\}$. Let us replace $A$ with $A'=\{a'=p^{-k}a: a\in A_{p,k}\}$. For every $b\in B$, define $b'=\frac{b}{p^{\min(k,v_p(b))}}$. The numbers $b'$ form a set $B'$ of cardinality $|B'|\ge\frac{|B|}{(k+1)}$ because each $b'$ can be obtained from at most $k+1$ different $b\in B$. Define $C'$ in a similar way. Note that if $a'\in A', b'\in B', c'\in C'$, and $a,b,c$ are the elements of $A,B,C$ from which $a',b',c'$ were obtained, we have $[a,b,c]=p^k[a',b',c']$. Thus, if we have a minimal counterexample $A,B,C$ to our statement then $A',B',C'$ is not a counterexample, so we can find $a',b',c'$ with $[a',b',c']\ge \sigma |A'|\cdot |B'|\cdot |C'|\ge \sigma (k+1)^{-2}|A_{p,k}|\cdot|B|\cdot|C|$, which will not give us a triple $a,b,c$ with large least common multiple only if $|A_{p,k}|\le (k+1)^2p^{-k}|A|$. Thus, in our minimal counterexample, we must have this inequality for all prime $p$ and all $k\ge 1$. Note that it is trivially true with $k=0$ as well. The same inequality holds for the cardinalities of sets $B_{p,\ell}$ and $C_{p,m}$.

Now we shall try the averaging technique. Since we are dealing with a multiplicative problem, it will be convenient to use geometric means. So, let us consider the identity
```
\[
\prod_{a\in A,b\in B,c\in C}\frac{abc}{[a,b,c]}\prod_{a\in A,b\in B,c\in C}[a,b,c]=\prod_{a\in A,b\in B,c\in C}(abc)
\]
```

The products have $|A|\cdot|B|\cdot|C|$ factors in them and the product on the right is at least
```
\[
(|A|!)^{|B|\cdot|C|}(|B|!)^{|A|\cdot|C|}(|C|!)^{|A|\cdot|B|}\ge e^{-3|A|\cdot|B|\cdot|C|}(|A|\cdot|B|\cdot|C|)^{|A|\cdot|B|\cdot|C|}
\]
```

Our main task will be to estimate the first product on the left by $e^{K|A|\cdot|B|\cdot|C|}$ with some absolute $K>0$. If we manage to do that, we will immediately get the desired result "on average" with $\sigma=e^{-K-3}$. In order to do it, we'll estimate the power at which each prime $p$ can appear in this product. So, fix some $p$ and assume that $a\in A_{p,k},b\in B_{p,\ell},c\in C_{p,m}$. Then $p$ appears in the factor $\frac{abc}{[a,b,c]}$ at all only if $k+\ell+m\ge 2$ and its power in this case does not exceed $k+\ell+m+1$ (I know, this is an idiotic bound, but it holds and will allow me to have all factors of the same form). Thus, the total power in which $p$ appears in the first product is at most
```
\[
\begin{aligned}
&\sum_{k,\ell,m:k+\ell+m\ge 2}(k+\ell+m+1)|A_{p,k}|\cdot|B_{p,\ell}|\cdot|C_{p,m}|
\cr
&\le
|A|\cdot|B|\cdot|C|\cdot\sum_{k,\ell,m:k+\ell+m\ge 2}(k+\ell+m+1)^7p^{-(k+\ell+m)}
\end{aligned}
\]
```

Since there are at most $(M+1)^2$ ways to represent a positive integer $M$ as a sum of three non-negative integers, the last sum is at most $\sum_{M\ge 2}(M+1)^9p^{-M}$.

Now it is time to put all $p$ together. We get $e^{K|A|\cdot|B|\cdot|C|}$ with
```
\[
K=\sum_{M\ge 2,p\text{ prime}}(M+1)^9p^{-M}\log p
\]
```

and our only task is to show that this double series converges. We can forget that $p$ is prime, just remember that $p\ge 2$. Also for any $\delta>0$, we can estimate $(M+1)^9\le C_\delta p^{\delta M}$, $\log p\le C_\delta p^{\delta}$ with some finite $C_\delta>0$. Thus, our series is dominated by
```
\[
\sum_{M,p\ge 2}p^{\delta-(1-\delta)M}=\sum_{p\ge 2} \frac{p^{3\delta-2}}{1-p^{\delta-1}}\ge \frac 1{1-2^{\delta-1}}\sum_{p\ge 2}p^{3\delta-2}<+\infty
\]
```

if $\delta<\frac 13$.

This proof can be easily generalized to any number of sets but the constant it gives is rather terrible. It would be nice to get some better bound even for the case of 2 sets. As usual, questions and comments are welcome.

`$\{a_1,\ldots,a_n\}$`

and`$\{b_1,\ldots,b_n\}$`

there exist indices`$i,j\in[n]$`

such that`$[a_i,b_j]\ge c n^2$`

with a positive absolute constant`$c$`

? – Seva Oct 29 '10 at 8:12