Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ Advances in Combinat...arrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
Advances in Combinatorics
Article . 2020 . Peer-reviewed
Data sources: Crossref
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
Advances in Combinatorics
Article
License: CC BY
Data sources: UnpayWall
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
https://dx.doi.org/10.48550/ar...
Article . 2019
License: arXiv Non-Exclusive Distribution
Data sources: Datacite
versions View all 3 versions
addClaim

The maximum number of triangles in a graph of given maximum degree

Authors: Chase, Zachary;

The maximum number of triangles in a graph of given maximum degree

Abstract

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$.

Related Organizations
Keywords

FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO)

  • BIP!
    Impact byBIP!
    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
Powered by OpenAIRE graph
Found an issue? Give us feedback
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).
BIP!Citations provided by BIP!
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.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
4
Top 10%
Average
Average
Green
gold