On the minimum number of triangles in balanced tripartite graphs with large minimum degree
Let $f(n,t)$ be the minimum number of triangles in a tripartite graph with $n$ vertices in each part and minimum degree at least $n+t$. In 1975, Bollobás, Erdős and Szemerédi proved that $f(n,1)=\min\{4,n\}$. They further remarked that it is ``very likely'' that $f(n,t)\ge4t^3$ for $n\ge5t$. They also proved that $f(n,t) \ge t^3$ for all integers $n \ge t \ge 1$. We construct graphs showing that, for all integers $t\ge1$ and $n\ge3t+2\lceil(1+\sqrt5)t/2\rceil$, \[ f(n,t)\le(1+\sqrt5)t^3+\left(1+\frac1{\sqrt5}\right)t^2. \] Here $1+\sqrt5\approx3.236<4$, and the displayed upper bound is…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.20590
curl -X POST /api/v1/records/arxiv/2609.20590/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.20590/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'