
arXiv: 1912.01600
Maximizing or minimizing the number of copies of a fixed graph in a large host graph is one of the most classical topics in extremal graph theory. Indeed, one of the most famous problems in extremal graph theory, the Erdős-Rademacher problem, which can be traced back to the 1940s, asks to determine the minimum number of triangles in a graph with a given number of vertices and edges. It was conjectured that the mnimum is attained by complete multipartite graphs with all parts but one of the same size whilst the remaining part may be smaller. The problem was widely open in the regime of four or more parts until Razborov resolved the problem asymptotically in 2008 as one of the first applications of his newly developed flag algebra method. This catalyzed a line of research on the structure of extremal graphs and extensions. In particular, Reiher asymptotically solved in 2016 the conjecture of Lovász and Simonovits from the 1970s that the same graphs are also minimizers for cliques of arbitrary size. This paper deals with a problem concerning the opposite direction: _What is the maximum number of triangles in a graph with a given number $n$ of vertices and a given maximum degree $D$?_ Gan, Loh and Sudakov in 2015 conjectured that the graph maximizing the number of triangles is always a union of disjoint cliques of size $D+1$ and another clique that may be smaller, and showed that if such a graph maximizes the number of triangles, it also maximizes the number of cliques of any size $r\ge 4$. The author presents a remarkably simple and elegant argument that proves the conjecture exactly for all $n$ and $D$.
FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO)
FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 4 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
