Many triangles with few edges (Q2420564)

Summary: Extremal problems concerning the number of independent sets or complete subgraphs in a graph have been well studied in recent years. \textit{J. Cutler} and \textit{A. J. Radcliffe} [J. Comb. Theory, Ser. B 104, 60--71 (2014; Zbl 1282.05073); J. Graph Theory 84, No. 2, 134--145 (2017; Zbl 1354.05104)] proved that among graphs with \(n\) vertices and maximum degree at most \(r\), where \(n = a(r+1)+b\) and \(0 \le b \le r\), \(aK_{r+1}\cup K_b\) has the maximum number of complete subgraphs, answering a question of \textit{D. Galvin} [Discrete Math. 311, No. 20, 2105--2112 (2011; Zbl 1228.05228)]. \textit{W. Gan} et al. [Comb. Probab. Comput. 24, No. 3, 521--527 (2015; Zbl 1371.05213)] conjectured that \(aK_{r+1}\cup K_b\) also maximizes the number of complete subgraphs \(K_t\) for each fixed size \(t \ge 3\), and proved this for \(a = 1\). Cutler and Radcliffe [loc. cit.] proved this conjecture for \(r \le 6\). We investigate a variant of this problem where we fix the number of edges instead of the number of vertices. We prove that \(aK_{r+1}\cup \mathcal{C}(b)\), where \(\mathcal{C}(b)\) is the colex graph on \(b\) edges, maximizes the number of triangles among graphs with \(m\) edges and any fixed maximum degree \(r\le 8\), where \(m = a \binom{r+1}{2} + b\) and \(0 \le b < \binom{r+1}{2}\).