Timeline for Maximum number of triangles no two of which have a common edge
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 26 at 17:29 | comment | added | RobPratt | If I understand correctly, the values of $f(n)$ for $n\in \{1,\dots,15\}$ are $$0,0,1,1,2,2,3,4,6,6,7,9,10,12,15,$$ which does not seem to be in the OEIS. | |
| Feb 26 at 5:58 | comment | converted from answer | Mathematics1998 | What if graph $G$ is a planar graph? Maybe $f(n)<\varepsilon n, \varepsilon<1 $. | |
| S Sep 16, 2020 at 23:12 | history | suggested | JimN | CC BY-SA 4.0 |
Edited the definition of $f(n)$, and applied math font to three f(n), four G, three n.
|
| Sep 16, 2020 at 21:36 | review | Suggested edits | |||
| S Sep 16, 2020 at 23:12 | |||||
| Oct 20, 2018 at 8:43 | comment | added | QiRenrui | @Russell Easterly no, sometimes you can take many triangle which no two of them have a common edge, but their edges may create another bad triangle. | |
| Oct 20, 2018 at 4:13 | comment | added | Russell Easterly | If I understand the question then it is the same as the maximum number of monotone, linear X3SAT clauses for $n$ variables. | |
| Oct 8, 2018 at 0:40 | answer | added | Sean Eberhard | timeline score: 2 | |
| Sep 4, 2018 at 11:26 | comment | added | Louis Esperet | 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. | |
| Sep 4, 2018 at 11:19 | comment | added | Louis Esperet | 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})}$. | |
| Sep 4, 2018 at 7:59 | comment | added | Sean Eberhard | 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. | |
| Sep 4, 2018 at 7:56 | history | edited | Sean Eberhard | CC BY-SA 4.0 |
edited title
|
| Sep 4, 2018 at 6:26 | comment | added | bof | 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. | |
| Sep 4, 2018 at 4:03 | history | asked | QiRenrui | CC BY-SA 4.0 |