pith. sign in

arxiv: 2606.28727 · v1 · pith:SPFBOIJRnew · submitted 2026-06-27 · 🧮 math.CO

Degree-restricted semi-saturation numbers of cliques and its applications

Zhen He , Mei Lu , Yanzhe Qiu , Yiduo Xu This is my paper

Pith reviewed 2026-06-30 09:41 UTC · model grok-4.3

classification 🧮 math.CO
keywords semi-saturation numbercliquedegree restrictionsaturation numberjoin graphextremal graph theoryasymptoticslimits
0
0 comments X

The pith

The normalized semi-saturation number of K_r with linear degree bound cn converges for all but a sparse sequence of c values.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies the smallest number of edges in an n-vertex graph that is semi-saturated for the clique K_r, meaning every added edge creates a new K_r copy, while no vertex exceeds a maximum degree Δ. When Δ is set to cn for fixed c in (0,1], the authors prove that this minimum edge count divided by n approaches a limit as n tends to infinity, except at a countable set of rational c values that decrease to zero. They determine the asymptotic form of the limit when c exceeds r/(r+2) but stays below 1, compute exact values for certain specific Δ, and apply the results to relate the saturation number of the join K_r ∨ F to the saturation number of F for many pairs (r,F).

Core claim

For arbitrary r ≥ 4, the limit lim_{n→∞} ssat^{cn}(n,K_r)/n exists for all 0 < c ≤ 1, except for some sparse values of c contained in a countable and rational sequence c_i → 0. Moreover, the asymptotic behaviour of this limit is established for r/(r+2) < c <1 and the exact value of ssat^Δ(n,K_r) is determined for some specific Δ. As an application, the relation between the saturation number of the join graph K_r ∨ F and that of F is determined for a large class of pairs (r,F).

What carries the argument

The degree-restricted semi-saturation number ssat^Δ(n,K_r), the minimum edges in an n-vertex K_r-semi-saturated graph whose maximum degree is at most Δ.

If this is right

  • The normalized minimum edge count converges for every linear degree bound except those sparse rationals.
  • The limit admits an explicit asymptotic expression whenever the bound fraction exceeds r/(r+2).
  • Exact values of ssat^Δ(n,K_r) are known for certain concrete choices of Δ.
  • Saturation numbers of K_r ∨ F are determined by those of F for a broad family of graphs F.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The exceptional rational values of c likely mark points where the optimal construction family changes.
  • The same convergence technique may apply to semi-saturation problems for other forbidden subgraphs under degree constraints.
  • The join-graph relation provides a template for transferring saturation results across other graph products or operations.

Load-bearing premise

Graph constructions exist that remain K_r-semi-saturated while respecting the degree cap cn and attaining the claimed minimum edge count.

What would settle it

For some c outside the exceptional sequence, the sequence ssat^{cn}(n,K_r)/n fails to converge to any single number as n increases through integers.

Figures

Figures reproduced from arXiv: 2606.28727 by Mei Lu, Yanzhe Qiu, Yiduo Xu, Zhen He.

Figure 1
Figure 1. Figure 1: A schematic plot of Ar−2(c) from Theorem 1.5. Recall that ssatn−1 ∗ (n, Kr) = ssatn−1 (n, Kr) = ssat(n, Kr) = sat(n, Kr) = (r − 2)n − (r−2)(r−3) 2 ([5]). Combining with Theorem 1.7, we immediately have that c0 = 1 is a discontin￾uous point in Theorem 1.3. A natural question is whether one can determine sat(n, Kr ∨F) from the saturation number of F. An easy observation is that sat(n, Kr ∨ F) ≤ r(n − r) + sa… view at source ↗
read the original abstract

A graph $G$ is said to be $F$-semi-saturated if the addition of any nonedge $e \not \in E(G)$ would create a new copy of $F$ in $G+e$. The semi-saturation number $ssat(n,F)$ is the minimum number of edges in an $F$-semi-saturated graph of order $n$. In this paper we investigate the semi-saturation number of $K_r$ on $n$ vertices with maximal degree at most $\Delta$, denoted by $ssat^{\Delta}(n,K_r)$. This investigation was suggested by Erd\H os, R\'enyi and S\'os, who in 1966 considered the graph of diameter 2 with degree restrictions, equivalently $ssat^{\Delta}(n,K_3)$. The following are some of our results. For arbitrary $r \geq 4$, we show that the limit $ \lim_{n \rightarrow \infty} ssat^{cn}(n,K_r)/n$ exists for all $0 < c \leq 1$, except for some sparse values of $c$ contained in a countable and rational sequence $c_i \rightarrow 0$. Moreover, we establish the asymptotic behaviour of this limit for $\frac{r}{r+2} < c <1$ and determine the exact value of $ssat^{\Delta}(n,K_r)$ for some specific $\Delta$. As an application, we determine the relation between the saturation number of the join graph $K_r \vee F$ and that of $F$ for a large class of pairs $(r,F)$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper defines the degree-restricted semi-saturation number ssat^Δ(n, K_r) and proves, for r ≥ 4, that lim_{n→∞} ssat^{cn}(n, K_r)/n exists for every 0 < c ≤ 1 except a countable sequence of rational values c_i → 0. It determines the asymptotic value of the limit on the interval r/(r+2) < c < 1, obtains exact values of ssat^Δ(n, K_r) for certain specific Δ, and derives a relation between sat(n, K_r ∨ F) and sat(n, F) for a large class of pairs (r, F). The proofs rely on explicit blow-up constructions that respect the linear degree bound cn together with a counting argument that produces a matching lower bound.

Significance. If the stated constructions and counting arguments are correct, the work supplies the first systematic treatment of linear degree restrictions on semi-saturation numbers for cliques larger than K_3, confirming the existence of the normalized limit outside an explicitly described exceptional set and giving matching asymptotics on a positive-density interval of c. The application to saturation numbers of joins extends the reach of the method to a broader family of forbidden graphs. The combination of explicit, degree-controlled constructions with a direct counting lower bound constitutes a concrete technical contribution to extremal graph theory.

minor comments (3)
  1. [§2] §2, Definition 1.1: the phrase “the addition of any nonedge e ∉ E(G) would create a new copy of F” should be accompanied by an explicit statement that the new copy must contain the added edge, to avoid any ambiguity with the classical saturation definition.
  2. [Theorem 1.3] Theorem 1.3 (the asymptotic statement for r/(r+2) < c < 1): the leading coefficient is stated only up to o(1) terms; if the authors possess a more precise second-order expansion, it would strengthen the result and could be recorded as a remark.
  3. [Introduction] The sequence c_i is described as “countable and rational” but its explicit recursive definition or generating function is not displayed in the introduction; a short displayed formula would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, recognition of its technical contributions, and recommendation to accept.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper derives existence of the limit lim ssat^{cn}(n,K_r)/n, its asymptotics for r/(r+2)<c<1, and exact values for specific Δ via explicit blow-up constructions of semi-saturated graphs respecting the degree cap cn together with a counting lower bound on K_r copies. These steps rely on independent graph-theoretic constructions and counting arguments rather than any self-definition, fitted parameter renamed as prediction, or load-bearing self-citation chain. No equations or reductions in the provided text equate a claimed result to its own inputs by construction. The derivation is self-contained against external graph constructions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on the standard definitions and axioms of graph theory (simple undirected graphs, cliques, edge addition) with no free parameters, no invented entities, and no ad-hoc axioms visible in the abstract.

axioms (1)
  • standard math Standard axioms of finite undirected simple graphs and the definition of F-semi-saturation
    The entire investigation is built on these background definitions from extremal graph theory.

pith-pipeline@v0.9.1-grok · 5834 in / 1380 out tokens · 45396 ms · 2026-06-30T09:41:40.146026+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

22 extracted references · 1 canonical work pages

  1. [1]

    N. Alon, P. Erd¨ os, R. Holzman and M. Krivelevich, Onk-saturated graphs with restrictions on the degrees. J. Graph Theory, 23 (1996), pp. 1-20

    1996

  2. [2]

    K. Amin, J. Faudree, R.J. Gould and E. Sidorowicz, On the non-(p−1)-partiteK p-free graphs. Discuss. Math. Graph Theory, 33(1) (2013), pp. 9-23

    2013

  3. [3]

    Currie, J.R

    B.L. Currie, J.R. Faudree, R. J. Faudree and J. R. Schmitt, A survey of minimum saturated graphs, Electron. J. Combin., 18 (2011), DS19

    2011

  4. [4]

    Duffus and D

    D.A. Duffus and D. Hanson, Minimalk-saturated and color critical graphs of prescribed minimum degree, J. Graph Theory, 10 (1986), pp. 55-67

    1986

  5. [5]

    Erd˝ os, A

    P. Erd˝ os, A. Hajnal and J.W. Moon, A problem in graph theory, Amer. Math. Monthly 71 (1964), pp. 1107-1110

    1964

  6. [6]

    Erd˝ os and R

    P. Erd˝ os and R. Holzman, On maximal triangle-free graphs, J. Graph Theory, 18 (1994), pp. 585-594

    1994

  7. [7]

    Erd˝ os, A

    P. Erd˝ os, A. R´ enyi and V. T. S´ os, On a problem of graph theory, Studia Sci. Math. Hungar. 1 (1966), pp. 215-235

    1966

  8. [8]

    Erd˝ os and R

    P. Erd˝ os and R. Rado, Intersection theorems for systems of sets, J. London Math. Soc. 35 (1960), pp. 85–90

    1960

  9. [9]

    F¨ uredi and A

    Z. F¨ uredi and A. Seress, Maximal triangle-free graphs with restrictions on the degrees, J. Graph Theory, 18 (1994), pp. 11-24

    1994

  10. [10]

    F¨ uredi, Intersecting designs from linear programming and graphs of diameter two, Discrete Math

    Z. F¨ uredi, Intersecting designs from linear programming and graphs of diameter two, Discrete Math. 127 (1994), no. 1-3, pp. 187-207

    1994

  11. [11]

    Hajnal, A theorem onk-saturated graphs, Canad

    A. Hajnal, A theorem onk-saturated graphs, Canad. J. Math. 17 (1965), pp. 720-724

    1965

  12. [12]

    Hanson and K

    D. Hanson and K. Seyffarth,k-saturated graphs of prescribed maximum degree, Congres. Numer. 42 (1984), pp. 169-182

    1984

  13. [13]

    J. Hu, S. Ji, and Q. Cui, (K 1 ∨P t)-saturated graphs with minimum number of edges. J. Combin. Optim. 49 (2025), no. 2, Paper No. 23

    2025

  14. [14]

    S. Hu, Z. Luo and Y. Peng, Saturation numbers of joins of graphs, Discrete Appl. Math. 357 (2024), pp. 300–309. 25

    2024

  15. [15]

    Pach and L

    J. Pach and L. Sur´ anyi, Graphs of diameter 2 and linear programming, inAlgebraic methods in graph theory, Vol. I, II (Szeged, 1978), pp. 599–629, Colloq. Math. Soc. J´ anos Bolyai, 25, North-Holland, Amsterdam-New York

    1978

  16. [16]

    Pach and L

    J. Pach and L. Sur´ anyi, On graphs of diameter 2, Ars Combin. 11 (1981), pp. 61-78

    1981

  17. [17]

    Y. Qiu, Z. He, M. Lu and Y. Xu, The saturation number of wheels, Discrete Appl. Math. 379 (2026), pp. 542–550

    2026

  18. [18]

    N. Song, J. Hu, S. Ji and Q. Cui, The saturation number ofW 4, Discrete Math. 349 (8) (2026), 115107

    2026

  19. [19]

    Vˇ rˇto and ˇS

    I. Vˇ rˇto and ˇS. Zn´ am, Minimal graphs of diameter two and given maximal degree, Studia Sci. Math. Hungar. 17 (1982), no. 1-4, pp. 283-290

    1982

  20. [20]

    Zhang, Q

    C. Zhang, Q. Cui, J. Hu, E. Yue and S. Ji, Some results on minimum saturated graphs, Discrete Appl. Math. 384 (2026), pp. 23–33

    2026

  21. [21]

    Zhang, L

    X. Zhang, L. You and X. Zhao, Saturation numbers ofK 2 ∨P k, arXiv:2511.20213

    work page arXiv

  22. [22]

    Zn´ am, Minimal graphs of diameter two, Studia Sci

    ˇS. Zn´ am, Minimal graphs of diameter two, Studia Sci. Math. Hungar. 19 (1984), no. 2-4, pp. 187-191. 26

    1984