10
$\begingroup$

For $n\in N_+$, define $f(n)$ to be the maximum number of triangles in a graph $G$ with $n$ vertices, taken over all $n$-vertex graphs having the property where no two triangles have a common edge.

Do we have some good estimates for $f(n)$?

By triangle removal lemma, we can prove for any $\varepsilon>0$, while $n$ is large, we have $f(n)<\varepsilon n^2$.

(Intuitively, for a regular partition of $G$, if any triangle contributes an edge to a "low density part" (or some ignored part), then the "low density part" can not suffer so much edge. So there's some triangle which every edge contained in a "high density part", and then we'll get $cn^3$ triangles, which can't independent in edge.)

If we can prove that $f(n)<\frac{\varepsilon n^2}{ln\ n}$ for large $n$, then we can prove that there exists infinitely many triples of primes which forms an arithmetic sequence, in a combinatorial way.

Improve this question
$\endgroup$
8
  • $\begingroup$ There is of course the trivial lower bound $f(n)\gt cn^{3/2}$ from the fact that $f\left(\binom n2\right)\ge\binom n3$ but that's neither here nor there. $\endgroup$
    – bof
    Commented Sep 4, 2018 at 6:26
  • 2
    $\begingroup$ I think this is a somewhat simpler triangle removal argument: Since every edge is in at most one triangle, there are $O(n^2)$ triangles, so by the triangle removal lemma we can destroy them all by removing $o(n^2)$ edges. So actually there were $o(n^2)$ triangles. $\endgroup$
    – Sean Eberhard
    Commented Sep 4, 2018 at 7:59
  • 2
    $\begingroup$ The best known constructions with respect to the triangle removal lemma (so called Behrend graphs) show that $f(n)\ge \frac{n^2}{\exp(\sqrt{\log n})}$. $\endgroup$
    – Louis Esperet
    Commented Sep 4, 2018 at 11:19
  • 1
    $\begingroup$ The connection between the triangle removal lemma and Roth's theorem was noticed long time ago, see this survey math.mit.edu/~fox/paper-removalsurvey.pdf for the history and some recent results. $\endgroup$
    – Louis Esperet
    Commented Sep 4, 2018 at 11:26
  • $\begingroup$ If I understand the question then it is the same as the maximum number of monotone, linear X3SAT clauses for $n$ variables. $\endgroup$
    – Russell Easterly
    Commented Oct 20, 2018 at 4:13

1 Answer 1

Reset to default
2
$\begingroup$

I think the answer to your question "do we have some good estimates for $f(n)$?" is no. Or at least, the situation is the same as that for triangle removal itself. The assertion that $f(n) = o(n^2)$ is normally called the Ruzsa--Szemeredi theorem: see for instance footnote 1 here: https://arxiv.org/abs/1211.3487. I think that people who think about this stuff generally think of Ruzsa--Szemeredi and triangle removal as morally (but not quite exactly) equivalent.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .