2
$\begingroup$

I don't understand how the bound on the minimum number of trivial triangles is established in the proof for Roth's Theorem.

An explanation can be found for example on this page.

We identify arithmetic progressions as triangles in a tripartite graph. I don't get why there are more than $\epsilon n^2$ trivial triangles.

$\endgroup$

1 Answer 1

1
$\begingroup$

Chose $i \in V_1$. We have $n$ possibilities to do this. Later, chose $j \in V_2$ such that $j - i \in A$. We have at least $\varepsilon n$ possibilities. Finally, we have just one possibility to choose $k \in V_3$ such that $k - j = j - i$.

$\endgroup$

You must log in to answer this question.

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