Many triangles with few edges

zbMath1414.05161arXiv1709.06163MaRDI QIDQ2420564

Rachel Kirsch, Andrew John Radcliffe

Publication date: 6 June 2019

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: Extremal problems concerning the number of independent sets or complete subgraphs in a graph have been well studied in recent years. Cutler and Radcliffe proved that among graphs with $n$ vertices and maximum degree at most $r$, where $n=a(r+1)+b$ and $0lebler$, $a{K}_{r+1}cup{K}_b$ has the maximum number of complete subgraphs, answering a question of Galvin. Gan, Loh, and Sudakov conjectured that $a{K}_{r+1}cup{K}_b$ also maximizes the number of complete subgraphs $K_t$ for each fixed size $tge3$, and proved this for $a=1$. Cutler and Radcliffe proved this conjecture for $rle6$. We investigate a variant of this problem where we fix the number of edges instead of the number of vertices. We prove that $a{K}_{r+1}cupmathcalC(b)$, where $mathcalC(b)$ is the colex graph on $b$ edges, maximizes the number of triangles among graphs with $m$ edges and any fixed maximum degree $rle8$, where $$ and $$.

Full work available at URL: https://arxiv.org/abs/1709.06163

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

complete subgraphsnumber of independent sets

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Two problems on independent sets in graphs
• Face vectors of flag complexes
• On the maximum number of cliques in a graph
• Bounds on the number of complete subgraphs
• The maximum number of q-cliques in a graph with no p-clique
• The maximum number of triangles in a \(K_4\)-free graph
• A new Turán-type theorem for cliques in graphs
• The maximum number of complete subgraphs in a graph with given maximum degree
• A generalization of a theorem of Turán
• The Maximum Number of Complete Subgraphs of Fixed Size in a Graph with Given Maximum Degree
• Shadows of colored complexes.
• Maximizing the Number of Independent Sets of a Fixed Size
• Counting Independent Sets of a Fixed Size in Graphs with a Given Minimum Degree
• Difference graphs

Related Items (8)

Tree densities in sparse graph classes ⋮ Maximizing the density of \(K_t\)'s in graphs of bounded degree and clique number ⋮ The maximum number of triangles in a graph and its relation to the size of the Schur multiplier of special p-groups ⋮ Regular Turán numbers and some Gan–Loh–Sudakov‐type problems ⋮ Many Cliques in Bounded-Degree Hypergraphs ⋮ Many cliques with few edges ⋮ Many cliques with few edges and bounded maximum degree ⋮ Exact results on generalized Erdős-Gallai problems

This page was built for publication: Many triangles with few edges