Supersaturation for subgraph counts

DOI10.1007/S00373-021-02454-YMaRDI QIDQ2117531zbMATH OpenOpenAlexFDO

Authors JD Nir, Jonathan Cutler, Andrew John Radcliffe

Publication date 21 March 2022

Published in Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

extremal graph theorysupersaturationgeneralized Turán problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Vertex degrees (05C07) Enumeration in graph theory (05C30) Paths and cycles (05C38)

Abstract: The classic extremal problem is that of computing the maximum number of edges in an $F$-free graph. In the case where $F=K_{r+1}$, the extremal number was determined by Tur'an. Later results, known as supersaturation theorems, proved that in a graph containing more edges than the extremal number, there must also be many copies of $K_{r+1}$. Alon and Shikhelman introduced a broader class of problems asking for the maximum number of copies of a graph $T$ in an $F$-free graph. In this paper, we determine some of these generalized extremal numbers and prove supersaturation results for them.

Recommendations

• Supersaturated graphs and hypergraphs
• Supersaturated sparse graphs and hypergraphs
• Subgraph densities in hypergraphs
• A concentration result with application to subgraph count
• Subgraph counts for dense random graphs with specified degrees
• Saturation numbers for families of graph subdivisions
• Multiplicities of subgraphs
• Upper tails for subgraph counts in random graphs
• Counting Subgraphs in Degenerate Graphs

Cites work

• scientific article; zbMATH DE number 3821782 (Why is no real title available?)
• scientific article; zbMATH DE number 3529891 (Why is no real title available?)
• scientific article; zbMATH DE number 5174567 (Why is no real title available?)
• scientific article; zbMATH DE number 3258067 (Why is no real title available?)
• scientific article; zbMATH DE number 3185004 (Why is no real title available?)
• scientific article; zbMATH DE number 3188526 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• scientific article; zbMATH DE number 3050594 (Why is no real title available?)
• A Turán type problem concerning the powers of the degrees of a graph
• Counting independent sets of a fixed size in graphs with a given minimum degree
• Degree powers in graphs with forbidden subgraphs
• Graphs with many r -cliques have large complete r -partite subgraphs
• Many \(T\) copies in \(H\)-free graphs
• Maximizing five-cycles in \(K_r\)-free graphs
• Maximizing the number of independent sets of a fixed size
• New asymptotics for bipartite Turán numbers
• On a theorem of Rademacher-Turán
• On complete subgraphs of different orders
• On supersaturation and stability for generalized Turán problems
• On the Minimal Density of Triangles in Graphs
• On the maximal number of certain subgraphs in \(K_ r\)-free graphs
• On the maximum number of cliques in a graph
• On the structure of linear graphs
• Supersaturation problem for color-critical graphs
• The clique density theorem
• The maximum number of $P_\ell$ copies in $P_k$-free graphs
• The maximum number of cliques in graphs without long cycles
• The maximum number of triangles in a graph of given maximum degree
• The number of cliques in graphs of given order and size

Cited in

(13)

• Paths of length three are \(K_{r+1}\)-Turán-good
• scientific article; zbMATH DE number 3885945 (Why is no real title available?)
• Supersaturated graphs and hypergraphs
• Unified approach to the generalized Turán problem and supersaturation
• scientific article; zbMATH DE number 3900799 (Why is no real title available?)
• Multiplicities of subgraphs
• Extremal problems of double stars
• Counting copies of a fixed subgraph in \(F\)-free graphs
• On supersaturation and stability for generalized Turán problems
• Supersaturated sparse graphs and hypergraphs
• Every graph is eventually Turán-good
• Supersaturation, counting, and randomness in forbidden subposet problems
• Some exact results for generalized Turán problems

This page was built for publication: Supersaturation for subgraph counts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2117531)