Supersaturation for subgraph counts

DOI10.1007/S00373-021-02454-YzbMATH Open1485.05083arXiv1903.08059OpenAlexW2921339014MaRDI QIDQ2117531FDOQ2117531

Authors: JD Nir, Jonathan Cutler, Andrew John Radcliffe 

Publication date: 21 March 2022

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

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.

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

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

zbMATH Keywords

extremal graph theorysupersaturation[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=generalized+Tur%EF%BF%BD%EF%BF%BDn+problem&go=Go generalized 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)

Cites Work

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

Cited In (14)

• Extremal problems of double stars
• Some exact results for generalized Turán problems
• Title not available (Why is that?)
• Supersaturation problem for the bowtie
• Paths of length three are \(K_{r+1}\)-Turán-good
• Every graph is eventually Turán-good
• On supersaturation and stability for generalized Turán problems
• Counting copies of a fixed subgraph in \(F\)-free graphs
• Unified approach to the generalized Turán problem and supersaturation
• Supersaturated graphs and hypergraphs
• Multiplicities of subgraphs
• Title not available (Why is that?)
• Supersaturated sparse graphs and hypergraphs
• Supersaturation, counting, and randomness in forbidden subposet 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)