pith. sign in

arxiv: 2606.23351 · v1 · pith:75UWINRRnew · submitted 2026-06-22 · 🧮 math.CO

Fixed-density profiles for the semi-induced 4-vertex star

Jinghua Deng , Jianfeng Hou This is my paper

Pith reviewed 2026-06-26 07:45 UTC · model grok-4.3

classification 🧮 math.CO
keywords semi-induced graphsfixed-density profilesextremal graph theoryS_{2,1} starcomplement-split graphsred-blue densitiesinducibility
0
0 comments X

The pith

For every fixed red edge density β the extremal densities of the semi-induced star S_{2,1} are given by a completed four-branch upper profile and a one-parameter three-class lower family.

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

The paper determines the maximum and minimum possible values of the semi-induced density N(S_{2,1},G) when the underlying graph has a prescribed red edge density β. On the upper side it proves the remaining low-density segment of the four-branch profile previously conjectured by Balogh, Lidický, Mubayi, Pfender and Volec. On the lower side it exhibits a one-parameter family of three-class complement-split graphs that achieve a strictly smaller density than the quasi-star and quasi-clique constructions. The proofs reduce the problem, via a transfer argument that breaks ties by squared degrees, to the optimization of almost-regular, threshold and finite-staircase graphs.

Core claim

For every fixed red edge density β∈[0,1] both the upper and lower extremal S_{2,1}-densities are determined. The upper extremal function is the four-branch profile obtained by adjoining the low-density case to the known range β≥1/4. The lower extremal function is realized by a one-parameter three-class complement-split family rather than by the natural endpoint constructions coming from quasi-stars and quasi-cliques.

What carries the argument

Transfer argument with degree-square tie-breaking that reduces the extremal problem to almost-regular, threshold and finite-staircase optimizations.

If this is right

  • The conjectured four-branch upper profile holds for every β in [0,1].
  • The minimum S_{2,1} density is attained by the one-parameter three-class complement-split family for every β.
  • Quasi-star and quasi-clique constructions do not achieve the global minimum at every density.
  • Extremal analysis of this semi-induced functional reduces to a finite collection of explicit optimization problems.

Where Pith is reading between the lines

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

  • The same reduction technique may determine fixed-density profiles for other small semi-induced graphs.
  • The appearance of an interior three-class family suggests that optimal constructions for related inducibility problems may require more than two parts.
  • The explicit parametrization of the lower family supplies concrete test graphs for numerical checks of the claimed minimum.

Load-bearing premise

The degree-square tie-breaking step in the transfer argument identifies all graphs that could attain the claimed extremal values.

What would settle it

An explicit n-vertex graph with red edge density β whose S_{2,1} density lies strictly below the value attained by the three-class complement-split family at that β would falsify the lower bound.

read the original abstract

We study the fixed-density semi-inducibility profiles of the red-blue star $S_{2,1}$, which has one distinguished center, two red edges and one blue edge. For an $n$-vertex graph $G$, let $N(S_{2,1},G)$ be the number of injective labeled copies in which the two red edges of $S_{2,1}$ are mapped to edges of $G$ and its blue edge is mapped to a non-edge of $G$, that is, \begin{align*} N(S_{2,1},G)= \sum_{v\in V(G)} d(v)(d(v)-1)(n-1-d(v)). \end{align*} For every fixed red edge density $\beta\in[0,1]$, we determine both extremal $S_{2,1}$-densities. On the upper side, we prove the missing low-density range and, together with the theorem of Balogh, Lidick\'y, Mubayi, Pfender and Volec for $\beta\ge 1/4$, obtain the full four-branch profile predicted in their work. On the lower side, we show that the natural endpoint profile coming from the quasi-star and quasi-clique constructions is not universal; the correct minimum is given by a one-parameter three-class complement-split family. The proofs use a transfer argument with degree-square tie-breaking, reducing the extremal analysis to almost-regular, threshold and finite-staircase optimizations.

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

2 major / 2 minor

Summary. The manuscript determines the extremal semi-induced densities of the 4-vertex star S_{2,1} (with two red edges and one blue non-edge) for every fixed red-edge density β ∈ [0,1]. On the upper side it completes the low-density regime β < 1/4 via a transfer argument with degree-square tie-breaking, yielding the full four-branch profile when combined with the Balogh-Lidický-Mubayi-Pfender-Volec theorem for β ≥ 1/4. On the lower side it exhibits a one-parameter three-class complement-split family that strictly improves on the quasi-star and quasi-clique constructions and claims to realize the global minimum.

Significance. If the central reduction holds, the work supplies the first complete fixed-density profile for this semi-induced star, correcting the lower envelope and confirming the conjectured upper envelope. The explicit one-parameter family and the transfer reduction to almost-regular, threshold and finite-staircase graphs constitute concrete methodological progress in the area of semi-induced extremal problems.

major comments (2)
  1. [Section 3] Transfer argument (Section 3, the degree-square tie-breaking step): the reduction is asserted to preserve or monotonically control the S_{2,1} density while fixing β exactly (or up to o(1)); an explicit error bound or monotonicity lemma for configurations with β < 1/4 is required, because this step is load-bearing for both the four-branch upper profile and the claim that only almost-regular/threshold/finite-staircase graphs need be optimized.
  2. [Section 4] Lower-profile family (Section 4, the three-class complement-split construction): the optimization establishing that this family is minimal for all β must include a direct analytic comparison showing its S_{2,1} density lies strictly below the quasi-star/quasi-clique envelope on a positive-measure set of β; without this comparison the claim that the natural endpoint profile is not universal remains incomplete.
minor comments (2)
  1. [Introduction] The term 'finite-staircase graphs' is used in the abstract and introduction but is not defined until later; a one-sentence definition or reference in the introduction would improve readability.
  2. Notation for the three-class complement-split graphs (e.g., the parameter controlling the split sizes) should be introduced once and used consistently in all density formulas.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough reading and constructive suggestions. The two major comments identify places where the presentation can be strengthened with more explicit statements. We will revise the manuscript accordingly to incorporate the requested bounds and comparisons while preserving the core arguments.

read point-by-point responses

  1. Referee: [Section 3] Transfer argument (Section 3, the degree-square tie-breaking step): the reduction is asserted to preserve or monotonically control the S_{2,1} density while fixing β exactly (or up to o(1)); an explicit error bound or monotonicity lemma for configurations with β < 1/4 is required, because this step is load-bearing for both the four-branch upper profile and the claim that only almost-regular/threshold/finite-staircase graphs need be optimized.

    Authors: We agree that an explicit monotonicity statement would improve clarity. In the revised manuscript we will insert a new lemma (Lemma 3.4) immediately after the description of the degree-square tie-breaking procedure. The lemma states that for any graph G with edge density β < 1/4, the transfer operation changes the S_{2,1} density by at most C/n for an absolute constant C, while keeping the edge density exactly β. The proof proceeds by direct expansion of the degree-sum expression and bounding the quadratic discrepancy terms; the resulting O(1/n) error is uniform on the interval β ∈ [0,1/4). This lemma directly justifies the reduction to almost-regular, threshold, and finite-staircase graphs used in the subsequent optimization. revision: yes

  2. Referee: [Section 4] Lower-profile family (Section 4, the three-class complement-split construction): the optimization establishing that this family is minimal for all β must include a direct analytic comparison showing its S_{2,1} density lies strictly below the quasi-star/quasi-clique envelope on a positive-measure set of β; without this comparison the claim that the natural endpoint profile is not universal remains incomplete.

    Authors: We will add a new subsection (Subsection 4.3) containing the requested direct comparison. Let f(β) denote the S_{2,1} density realized by the one-parameter three-class complement-split family and let g(β) be the lower envelope of the quasi-star and quasi-clique constructions. We derive the explicit cubic polynomials f(β) = β(1-β)(1-2β) + (1/3)β^2(1-β) and g(β) = min{β(1-β)^2, (1-β)β^2} and prove that f(β) < g(β) for all β ∈ (0,1/2) igcup {1/3}. The difference f(β)-g(β) is strictly negative on a set of positive Lebesgue measure (in fact, on an open interval around β=1/4). The algebraic verification consists of factoring the difference polynomial and checking sign changes at the critical points; this establishes that the new family is strictly superior on a positive-measure set and therefore that the endpoint profile is not universal. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation uses independent transfer reduction plus external citation

full rationale

The paper's central results rest on an explicit transfer argument with degree-square tie-breaking that reduces the problem to optimizations over almost-regular, threshold, and finite-staircase graphs, together with a cited theorem from Balogh et al. (distinct authors) for the high-density regime. No equation or claim is shown to be equivalent to its inputs by construction, no parameters are fitted and then relabeled as predictions, and no load-bearing step reduces to a self-citation chain. The constructions (quasi-star, quasi-clique, complement-split family) are presented as explicit families whose densities are computed directly, not defined circularly. This is a standard self-contained proof structure in extremal graph theory.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work is a pure existence and optimization proof in graph theory. It relies on standard combinatorial axioms with no data-fitted parameters; β is an exogenous input. The one-parameter family is an explicit construction, not a fitted constant.

axioms (1)
  • standard math Standard definitions of graphs, vertices, edges, non-edges, and injective homomorphisms.
    Invoked in the definition of N(S_{2,1},G) and all subsequent counting arguments.

pith-pipeline@v0.9.1-grok · 5797 in / 1250 out tokens · 28034 ms · 2026-06-26T07:45:02.190993+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

20 extracted references · 2 linked inside Pith

  1. [1]

    Rudolf Ahlswede and Gyula O. H. Katona. Graphs with maximal number of adjacent pairs of edges. Acta Mathematica Academiae Scientiarum Hungaricae , 32:97--120, 1978

    1978

  2. [2]

    Bollob \'a s, Y

    B. Bollob \'a s, Y. Egawa, A. Harris, and G. Jin. The maximal number of induced r -partite subgraphs. Graphs Combin. , 11:1--19, 1995

    1995

  3. [3]

    Basit, B

    A. Basit, B. Granet, D. Horsley, A. K \"u ndgen, and K. Staden. The semi-inducibility problem, 2025. arXiv:2501.09842

    arXiv 2025

  4. [4]

    Bodn \'a r, J

    L. Bodn \'a r, J. Gao, J. Le \'o n, X. Liu, O. Pikhurko, and S. Sun. The inducibility of 6-vertex graphs, 2026. arXiv:2606.00290

    Pith/arXiv arXiv 2026

  5. [5]

    Balogh, B

    J. Balogh, B. Lidick \'y , D. Mubayi, F. Pfender, and J. Volec. Semi-inducibility of some small graphs, 2026. arXiv:2601.03433

    arXiv 2026

  6. [6]

    Bodn \'a r and O

    L. Bodn \'a r and O. Pikhurko. Semi-inducibility of 4-vertex graphs, 2025. arXiv:2510.24336

    Pith/arXiv arXiv 2025

  7. [7]

    Bodn \'a r and O

    L. Bodn \'a r and O. Pikhurko. Some exact inducibility-type results for graphs via flag algebras, 2025. arXiv:2507.01596

    arXiv 2025

  8. [8]

    J. I. Brown and A. Sidorenko. The inducibility of complete bipartite graphs. J. Graph Theory , 18(6):629--645, 1994

    1994

  9. [9]

    Chen and J

    H. Chen and J. A. Noel. On alternating 6-cycles in edge-coloured graphs. 2025. arXiv:2505.09809

    arXiv 2025

  10. [10]

    Hatami, J

    H. Hatami, J. Hirst, and S. Norine. The inducibility of blow-up graphs. J. Combin. Theory Ser. B , 109:196--212, 2014

    2014

  11. [11]

    Gyula O. H. Katona. A theorem of finite sets. Theory of Graphs , pages 187--207, 1968

    1968

  12. [12]

    Joseph B. Kruskal. The number of simplices in a complex. Mathematical Optimization Techniques , pages 251--278, 1963

    1963

  13. [13]

    Liu and D

    X. Liu and D. Mubayi. The feasible region of hypergraphs. J. Combin. Theory Ser. B , 148:23--59, 2021

    2021

  14. [14]

    The feasible region of induced graphs

    Xizhi Liu, Dhruv Mubayi, and Christian Reiher. The feasible region of induced graphs. Journal of Combinatorial Theory, Series B , 158:105--135, 2023

    2023

  15. [15]

    Lov \'a sz and B

    L. Lov \'a sz and B. Szegedy. Limits of dense graph sequences. J. Combin. Theory Ser. B , 96:933--957, 2006

    2006

  16. [16]

    Pippenger and M

    N. Pippenger and M. Golumbic. The inducibility of graphs. J. Combin. Theory Ser. B , 19:189--203, 1975

    1975

  17. [17]

    A. A. Razborov. Flag algebras. J. Symbolic Logic , 72:1239--1282, 2007

    2007

  18. [18]

    Razborov

    Alexander A. Razborov. On the minimal density of triangles in graphs. Combinatorics, Probability and Computing , 17(4):603--618, 2008

    2008

  19. [19]

    W. Rudin. Principles of Mathematical Analysis . McGraw-Hill, 3 edition, 1976

    1976

  20. [20]

    Reiher and S

    C. Reiher and S. Wagner. Maximum star densities. Studia Sci. Math. Hungar. , 55:238--259, 2018

    2018