The maximum number of triangles in a graph and its relation to the size of the Schur multiplier of special p-groups

Abstract

We give a sharp bound on the number of triangles in a graph with fixed number of edges. We also characterize graphs that achieve the maximum number of triangles. Using the upper bound on number of triangles, we give a sharp bound for the size of the Schur multiplier of special p-group of all ranks. We also improve existing bounds for the size of Schur multiplier of p-groups $(p\ne 2,3)$ of class $c\ge 3$, and for p-groups of coclass r.

Keywords:

• Coclass
• cycles
• graphs
• Schur multiplier
• special p-groups

2020 Mathematics Subject Classification:

• 20D15
• 20F18
• 20J05
• 20J06
• 05C38
• 05D99

Acknowledgments

The authors asked Marcin Mazur whether he knows a bound for the set $Y_X:=\{(a,b,c)\mid (a,b),(a,c),(b,c)\in X,1\le a<b<c\le d\}$ where X is a subset of $\{(a,b)\mid 1\le a<b\le d\}$. Mazur informed us that there is a bijection between $Y_X$ and the triangles in a graph with vertices $\{1,\dots ,d\}$ and edges X and pointed us to Rivin’s paper [15]. We are grateful to him for this input as it simplified the exposition in Section 3. We also thank Robert F. Morse for providing us with the GAP code and computing the examples mentioned in Remark 2. We thank Komma Patali for helpful discussions. We thank the referee for their suggestions.

Additional information

Funding

V. Z. Thomas acknowledges research support from SERB, DST, Government of India grant MTR/2020/000483.