Supersaturation Beyond Color-Critical Graphs

Jie Ma, Long-Tu YuanComb 2025 · DOI

TL;DR

This paper delves into the "supersaturation problem" in graph theory, which asks how many copies of a specific subgraph must appear in a larger graph that has just a few more edges than the maximum possible without that subgraph. The authors present novel constructions that refute a conjecture about this problem for general graphs and establish new theoretical bounds for various graph families, including Kneser graphs and color-k-critical graphs.

What Problem Does This Paper Address?

The core problem is understanding the "supersaturation" phenomenon in graph theory. Given a graph $F$, the supersaturation problem asks for the minimum number of copies of $F$ that must exist in an $n$-vertex graph with $ex(n, F) + q$ edges, where $ex(n, F)$ is the maximum number of edges in an $n$-vertex graph that doesn't contain $F$ as a subgraph. A related concept is $t_F(n, q)$, the number of copies of $F$ in a graph obtained by adding $q$ edges to a maximum $F$-free graph. A key question is when $h_F(n, q) = t_F(n, q)$ holds.

Previous work focused heavily on cliques and color-critical graphs, establishing equality $h_F(n, q) = t_F(n, q)$ for certain ranges of $q$. This paper aims to extend these results beyond color-critical graphs and explore more complex relationships between $h_F(n, q)$, $q \cdot t_F(n, 1)$, and $t_F(n, q)$. Specifically, it addresses:

  1. Refuting a conjecture by Mubayi regarding the supersaturation of general graphs.
  2. Extending the equality $h_F(n, q) = t_F(n, q)$ to a broader family of graphs.
  3. Identifying precise thresholds for when this equality holds as $q$ varies with $n$.

Methods

The paper employs a combination of established and novel techniques from extremal graph theory:

  • Graph Removal Lemma and Erdős-Simonovits Stability Theorem: These are foundational tools used to analyze the structure of graphs with many edges that are close to being $F$-free. They help in understanding how graphs can be "made $F$-free" by removing a small number of edges or how $F$-free graphs with slightly fewer edges can be constructed from extremal graphs.
  • Explicit Graph Constructions: The authors construct specific graphs to demonstrate their theoretical results, particularly to refute conjectures. These constructions are carefully designed to have a controlled number of copies of $F$.
  • Quantitative and Structural Analysis: The paper meticulously analyzes the number of copies of $F$ in various graph structures, often by breaking down the problem into cases based on how copies of $F$ are embedded within different parts of the graph. This involves detailed counting arguments and the use of combinatorial parameters.
  • Specialized Lemmas: Several technical lemmas are developed or utilized to bound the number of substructures (like matchings or stars) within graphs, which are crucial for the main proofs.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Refutation of a Conjecture: The paper provides a counterexample to a conjecture by Mubayi, showing that for certain graphs and a fixed number of added edges $q \ge 4$, the number of copies of $F$ can be significantly less than what the conjecture predicted. This highlights that supersaturation behavior can be more complex than initially thought for general graphs.
  • Threshold for Equality: The research identifies a critical threshold for $q$ (specifically, $q = \Theta(n^{1-1/s})$ for some parameter $s$) that determines whether $h_F(n, q) = t_F(n, q)$ holds. This suggests a phase transition in the supersaturation behavior.
  • Admissible Color-k-Critical Graphs: The introduction and study of "admissible" color-k-critical graphs provide a framework for extending results like $h_F(n, q) = t_F(n, q)$ to a rich family of graphs, including Kneser graphs and disjoint unions of cliques.
  • Complexity of Supersaturation: The paper demonstrates that the relationship between $h_F(n, q)$ and $t_F(n, q)$ is not always straightforward, especially for non-bipartite graphs and when $q$ is not small relative to $n$.

Key Results

  • Theorem 1.4: Proves that a conjecture by Mubayi (Conjecture 1.3) is false for general graphs. It constructs non-bipartite stable graphs $F$ for which $h_F(n, q) < (1-\delta)q \cdot c(n, F)$ for $4 \le q \le \delta_F n$ and large $n$, where $c(n, F) = t_F(n, 1)$.
  • Theorem 1.5: Shows that for any Kneser graph $K = K(t, 2)$ with $t > 5$, the equality $h_K(n, q) = t_K(n, q)$ holds for $1 < q \le \delta n$ and sufficiently large $n$.
  • Theorem 1.6: Establishes that for any positive integer $s$, there exists a non-bipartite stable graph $F$ such that $h_F(n, q) = t_F(n, q)$ for $1 \le q \le \epsilon n^{1-1/s}$ and $h_F(n, q) < t_F(n, q)$ for $n^{1-1/s}/\epsilon \le q \le \epsilon n$. This pinpoints $q = \Theta(n^{1-1/s})$ as a threshold.

Limitations and Future Work

  • Conjecture 1.3 for Small $q$: While the paper refutes Conjecture 1.3 for $q \ge 4$, it speculates that the conjecture might hold for $q=1$. The authors pose this as an open question.
  • General Graphs and Odd Cycles: The paper suggests that investigating the supersaturation problem for odd cycles, especially for larger values of $q$, is a promising direction.
  • Hypergraphs: The authors mention that extending these problems to hypergraphs is an interesting avenue for future research.
  • Case $t=3$ for Theorem 1.6: The proof of Theorem 1.6 for the case $t=3$ is noted as requiring more effort and is deferred to future work.
  • Case $t=\infty$ for Theorem 1.6: The case $t=\infty$ for Theorem 1.6 is also left for a forthcoming paper.

Summary updated

BibTeX
@article{ma2025supersaturation,
  author = {Jie Ma and Long-Tu Yuan},
  title = {{Supersaturation Beyond Color-Critical Graphs}},
  journal = {Comb.},
  year = {2025},
  doi = {10.1007/s00493-025-00143-5},
}
Figure