PreprintCC BY 4.0arXiv
On the minimum number of triangles in balanced tripartite graphs with large minimum degree
Abstract
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)≥4t3 for n≥5t. They also proved that f(n,t) ≥ t3 for all integers n ≥ t ≥ 1. We construct graphs showing that, for all integers t≥1 and n≥3t+2⌈(1+√5)t/2⌉, f(n,t)≤(1+√5)t3+(1+1/√5)t2. Here 1+√5≈3.236<4, and the displayed upper bound is strictly less than 4t3 for every t≥2, disproving their proposed bound. We also improve their lower bound t3 by showing that f(n,t)≥12/5t3 for all integers t≥2 and n≥18t6.
Related
- On the maximum number of triangles in tripartite graphs with no $4$-cycles between any two parts
- The maximum number of triangles in regular graphs
- On the Minimum Number of Hamilton Cycles in Hamiltonian Threshold Graphs: A Simple Proof
- Bounded chromatic number of graphs with small clique number and large minimum degree
- On rainbow saturated graphs with minimum number of edges
BibTeX
@misc{fang2026minimum,
title = {{On the minimum number of triangles in balanced tripartite graphs with large minimum degree}},
author = {Chunqiu Fang and Rongxing Xu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.20590},
eprint = {2609.20590},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.20590},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On the minimum number of triangles in balanced tripartite graphs with large minimum degree
AU - Chunqiu Fang
AU - Rongxing Xu
PY - 2026
DA - 2026/09/17
PB - arXiv
DO - 10.48550/arxiv.2609.20590
UR - https://arxiv.org/abs/2609.20590
AB - 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)≥4t^3 for n≥5t. They also proved that f(n,t) ≥ t^3 for all integers n ≥ t ≥ 1. We construct graphs showing that, for all integers t≥1 and n≥3t+2⌈(1+√5)t/2⌉, f(n,t)≤(1+√5)t^3+(1+1/√5)t^2. Here 1+√5≈3.236<4, and the displayed upper bound is strictly less than 4t^3 for every t≥2, disproving their proposed bound. We also improve their lower bound t^3 by showing that f(n,t)≥12/5t^3 for all integers t≥2 and n≥18t^6.
ER -