Pith. sign in

REVIEW 3 major objections 6 minor 5 references

Star decompositions via orientations

T0 review · 3 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper proves that random $d$-regular graphs almost surely decompose into $k$-stars with balanced star counts whenever $k < d/2 - 1$.

desk verdict The strong-condition half is a real contribution, but the weak-regime proof uses the wrong threshold for condition (2) and skips exactly the profiles where violations are possible. read the letter →

arxiv 2506.05194 v2 pith:Y2HSIRA7 submitted 2025-06-05 math.CO math.PR

Viktor Harangi This is my paper · ORCID
classification math.COmath.PR MSC 05C8005C7005C20
keywords stardecompositionk-starrandomregulargraphorientationwithprescribedout-degreesfirstmomentmethodconfigurationmodelentropyratefunctioninducedsubgraphedgecount
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper proves that, for any degree $d$ and any star size $k$ with $2\le k < d/2-1$, a uniform random $d$-regular graph on $N$ vertices almost surely has a $k$-star decomposition: a partition of all edges into $k$-edge stars, each with a center vertex. The decomposition can be chosen so that every vertex is the center of either $s$ or $s+1$ stars, where $s=\lfloor d/(2k)\rfloor$, so the star counts are as balanced as possible. Under the stronger hypotheses $k

What carries the argument

The load-bearing object is Lemma 2.1, which uses a known orientation theorem, cited as [3, Theorem 1], to prove that a $d$-regular graph has a $k$-star decomposition with prescribed star counts exactly when every induced subgraph $U$ satisfies the edge bound $e[U]\le \sum_j jk|U_j|$, or equivalently the complementary bound (3). The probabilistic engine is the entropy rate function $F(x,t)=\tfrac12 h(tx)+h((1-t)x)+\tfrac12 h(1-(2-t)x)-H(x)$, with $h(x)=-x\log x$ and $H(x)=h(x)+h(1-x)$, which controls the exponential probability that an induced subgraph of density $x$ has average degree $td$. A first-moment comparison of $dF(x,t)+H(x)$ against the number of subsets yields the a.a.s. edge-count conditions. A strong condition $F_d(x_0,t_0)<0$ handles the prescribable-set regime, while a more delicate profile function $\eta(x_1,x_2)$ handles the remaining cases.

What would settle it

For a fixed $d,k$ in the theorem's range and for each $N$ with $Nd/(2k)\in\mathbb N$, compute the expected number of induced subgraphs $U$ violating inequality (2), using Lemma 3.1's bound (6). If the exponential rate $dF(x,t)+H(x)$ is nonnegative for some allowed $(x,t)$, the first-moment argument stops, so the a.a.s. claim would need a different proof or would be false. The paper's own boundary obstruction can be checked directly: for $r=1,2$ with $d=2k+r$, evaluate $\eta(x_1,x_2)$ from (14) over the region (15); a positive maximum would show exactly why the proof requires $k<d/2-1$.

Watch

Extended reading notes

Core claim

Theorem 1.1 is the paper's central claim: a random $d$-regular graph $G_{N,d}$ a.a.s. admits a $k$-star decomposition with $s$ or $s+1$ stars centered at each vertex whenever $2\le k<d/2-1$, provided $Nd/2$ is divisible by $k$ so that a decomposition is numerically possible. The stronger statement says that when $k<d/3$ or $k<d/2-2.6\log d$, the same holds simultaneously for every prescribed set $A$ of size $\beta N=\{d/(2k)\}N$: vertices outside $A$ get exactly $s$ stars and vertices in $A$ get exactly $s+1$. This goes beyond the earlier odd-$k$ existence result and provides a direct, self-contained derivation from an orientation theorem rather than from modulo-$k$ orientation results.

Load-bearing premise

The reduction rests on the quoted orientation theorem [3, Theorem 1] converting the existence of a star decomposition with prescribed star counts into the induced-subgraph edge-count inequalities (2) and (3); if that theorem does not apply as translated, none of the probabilistic verification establishes the decomposition.

Editorial extensions

If this is right

  • For every $d$ and every $k<d/2-1$, the theorem gives a $k$-star decomposition whose center counts differ by at most one, so the edge partition is as balanced as possible.
  • With $k<d/3$ or $k<d/2-2.6\log d$, the decomposition can be aligned with an arbitrary prescribed set of vertices of size $\beta N$, giving a strong form of local control over the star counts.
  • Together with the easy Eulerian case $2k\mid d$, the only unresolved value in the entire range $k\le d/2$ is $k=\lfloor (d-1)/2\rfloor$.
  • The proof supplies explicit, computer-checkable thresholds, tabulated in Section 5.3, for when the strong condition holds at any fixed $d$, so the theorem is effective rather than merely existential.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The orientation reduction of Lemma 2.1 is not tied to randomness: any graph whose induced subgraphs respect the edge bounds (2) and (3) automatically has the corresponding star decomposition, so the method may transfer to quasi-random or deterministic graph families.
  • The thresholds $k<d/3$ and $k<d/2-2.6\log d$ come from first-moment estimates and are probably not optimal; the paper's own tables show the strong condition holding in many pairs beyond those thresholds.
  • The missing boundary case $k=\lfloor(d-1)/2\rfloor$ corresponds to $r=1,2$ in the parametrization $d=2sk+r$, where the profile function in Lemma 4.2 ceases to be negative; closing that gap likely needs sharper entropy estimates rather than a new global idea.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. The paper studies k-star decompositions of random d-regular graphs. The main theorem (Theorem 1.1) asserts that for 2 ≤ k < d/2 - 1, the random d-regular graph G_{N,d} a.a.s. has a k-star decomposition in which each vertex centers either s or s+1 stars, where s = floor(d/(2k)); moreover, under additional conditions (k < d/3 or k < d/2 - 2.6 log d), the set of vertices with s stars can be prescribed arbitrarily among sets of the correct size βN. The proof strategy is to use a deterministic orientation equivalence (Lemma 2.1) reducing star decompositions to edge-count conditions (2)/(3), and then to verify these conditions probabilistically in the configuration model. The verification uses large-deviation estimates for induced subgraph edge densities (Lemma 3.1, Corollary 3.4) and, in the remaining weak regime (s = 1), a first-moment calculation over intersection profiles (Section 5.4). The paper also states threshold tables and claims finite verification for d ≤ 500.

Significance. If correct, the result would be a substantial advance: it covers all k < d/2 - 1 for every d, including even k, and strengthens the earlier existence results for odd k by prescribing the number of stars per vertex up to a specified set. The deterministic reduction and the entropy-based first-moment framework are natural and, apart from the gap described below, are executed with care. The paper contains no fitted parameters and the constants are derived analytically; the configuration-model estimates are standard and appear sound. The claimed thresholds are concrete and falsifiable. However, the central first-moment argument in the weak regime contains a load-bearing error that currently leaves a class of potentially violating subsets unaccounted for; this prevents the proof from establishing the theorem as written.

major comments (3)
  1. [Section 4, Eq. (14)] The quantity t defined in Eq. (14) is not the threshold for condition (2). Condition (2) requires e[U] ≤ k|U_1| + 2k|U_2|, i.e., the average degree of G[U] is at most t_true d with t_true = 2k(x_1 + 2x_2)/(d(x_1 + x_2)). Equation (14) instead defines t = 2r/d + 2k x_1/(d(x_1+x_2)) = [2(k+r)x_1 + 2r x_2]/(d x), which is the threshold for the inequality e[U] ≤ (k+r)|U_1| + r|U_2|, i.e., the complementary coefficient pattern applied to U rather than to U^c. These two thresholds agree only when x_1/x_2 = α_1/α_2. For A_1-rich profiles with x_1/x_2 > α_1/α_2, the paper's t exceeds 1 even though t_true < 1, and condition (2) can fail. The paper then asserts that t ≥ 1 means condition (2) holds automatically and restricts Lemma 4.2 to x_1/x_2 ≤ α_1/α_2. Consequently, the first-moment bound in Section 4 covers only A_2-rich profiles; A_1-rich profiles with density in [x_-, x_+] are not handled by the small-U case (x ≤ x_-) or the large-U case (x ≥ x_+). For instance, with d = 9, k = 3, r = 3, the profile x_1 = 0.15, x_2 = 0.01 gives the paper's t = 1.29 > 1, while t_true = 0.708 < 1; such a U can violate (2), and its expected count is not bounded anywhere in the proof. This is a genuine missing case in the proof of Theorem 1.1.
  2. [Section 5.4, Lemma 4.2] Because the threshold t in Eq. (14) is incorrect for condition (2), the first-moment function η(x_1, x_2) does not bound the expected number of sets U that violate condition (2). The restriction (15) to x_1/x_2 ≤ α_1/α_2 in Lemma 4.2 excludes precisely the profiles where condition (2) can fail: for such profiles the true threshold satisfies t_true ≥ 1, making the inequality automatic, while for the excluded A_1-rich profiles t_true < 1 and violations are possible. The case analysis in Section 5.4 therefore proves the negativity of a quantity that is unrelated to the event of interest on the excluded region, and no other argument in Sections 3--4 covers that region. This is a load-bearing gap: Theorem 1.1 relies on Lemma 4.2 for the whole weak regime.
  3. [Sections 5.3 and 5.4] The proof relies on finite computer verification for d ≤ 500 without providing code or certificates: the text states "One can quickly check with a computer that for d ≤ 500 the strong condition indeed holds" and "we verified this for all d,k ... in the range d ≤ 500," but no script, pseudocode, or certificate is included. Since Theorem 1.1 is stated for all d, this leaves a finite but nontrivial range unsupported in the written proof. This is less serious than the first two comments, but it should be addressed by making the verification reproducible or by replacing it with analytic bounds.
minor comments (6)
  1. [Section 2, Lemma 2.1] The proof of the equivalence (iii) ⇔ (ii') is only a citation to [3, Theorem 1] with a footnote explaining that it follows from max-flow-min-cut. For a paper that advertises a self-contained proof, a short derivation or a precise statement of the cited orientation theorem would be helpful.
  2. [Section 4, notation] The notation t_0 and t'_0 for the "smaller coefficient" thresholds is easy to confuse with the actual condition-(2) threshold; a remark distinguishing these two notions would prevent ambiguity, especially given the error in Eq. (14).
  3. [Section 5.1] In the text after Eq. (16), the symbol "ˆ𝑥𝑡" appears where "ˆ𝑥" is clearly intended; this typo makes the convexity discussion harder to follow.
  4. [Section 5.2] The displayed chain "−ℎ(1−𝑥)≤=−𝑥+ ..." contains a stray equals sign; it should read "−ℎ(1−𝑥) ≤ −𝑥 + ...".
  5. [Figure 1] Figure 1 is referenced in the proof of the k < d/4 case, but the figure itself is not included in the manuscript text; the claim that the fraction is below −1/9 on (0,1] should be either shown analytically or the figure should be supplied.
  6. [Section 5.3] The tables list thresholds k^sc_d for selected d, but the table for d ≤ 500 is not complete and the text only says a computer check was performed; providing the full table or a script would make the finite verification explicit.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the derivation is self-contained and rests on an external orientation theorem, not on fitted inputs or self-citation chains.

full rationale

The paper's central claim, Theorem 1.1, is derived by combining Lemma 2.1, a deterministic criterion for k-star decompositions in terms of subgraph edge counts, with first-moment estimates on induced subgraphs of the configuration model. Lemma 2.1 cites the Frank–Gyárfás orientation theorem [3] as its only external input; that theorem is not authored by the present paper's author, is stated as a general result about orientations with degree bounds, and the paper even notes it follows quickly from the integral max-flow min-cut theorem. The citation is therefore genuine independent support rather than a self-citation. The author's own prior work [4] appears only in the introduction as background on the complementary regime k>d/2 and plays no role in the proof of Theorem 1.1. The constants appearing in the proof, such as C0=1/(log 2-1/2), are chosen to satisfy explicit inequalities in the estimates, not fitted to the target conclusion or to any data. Condition (2) is proved by checking a worst-case bound over subset profiles; the exponential rates in Lemma 3.1 are derived from the configuration model's multinomial counting, not assumed. The claimed thresholds for the strong condition are obtained by analytic estimates and computer checks for d<=500, both of which are standard external verification procedures rather than circular reductions. No equation is defined in terms of the conclusion, no fitted parameter is renamed as a prediction, and no load-bearing premise is justified solely by a self-citation. Even if one viewed the proof's handling of certain subset-density regimes as incomplete, that would be a correctness concern, not a circularity concern. The derivation chain is therefore free from circularity.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The central claim rests on standard background results (orientation theorem, configuration model transfer, entropy bounds) rather than on fitted parameters or new postulated objects. The only non-shared numerical inputs are analytic constants chosen to satisfy strict inequalities; they are not free parameters in the statistical sense.

assumptions (3)
  • domain assumption Frank-Gyárfás orientation theorem: a graph has an orientation with prescribed out-degree bounds iff the corresponding edge-count conditions hold for all subsets (cited as [3, Theorem 1]).
    Used in Lemma 2.1 to establish the equivalence between k-star decompositions and orientation out-degrees; the paper notes it follows from the integral max-flow min-cut theorem.
  • domain assumption Configuration model transfer: conditioning the configuration model on simplicity yields the uniform simple d-regular graph, and the probability of simplicity is bounded below by a positive constant depending on d.
    Invoked in Section 3 to derive a.a.s. statements for G_{N,d} from G_{N,d}; standard result.
  • standard math Entropy bounds for multinomial coefficients: the inequalities used to estimate P_{M,r} in Lemma 3.1.
    Standard counting estimates, stated with a short proof sketch in the footnote.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Star decompositions via orientations." pith.science (2026). https://pith.science/paper/Y2HSIRA7

@misc{pith2026250605194,
  author       = {Pith},
  title        = {Pith review of: Star decompositions via orientations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Y2HSIRA7}},
  note         = {Machine review of arXiv:2506.05194}
}
abstract

A $k$-star decomposition of a graph is a partition of its edges into $k$-stars (i.e., $k$ edges with a common vertex). The paper studies the following problem: given $k \leq d/2$, does the random $d$-regular graph have a $k$-star decomposition (asymptotically almost surely, provided that the number of edges is divisible by $k$)? Delcourt, Greenhill, Isaev, Lidick\'y, and Postle proved the a.a.s. existence for every odd $k$ using earlier results regarding orientations satisfying certain degree conditions modulo $k$. In this paper we give a direct, self-contained proof that works for every $d$ and every $k<d/2-1$. In fact, we prove stronger results. Let $s\geq 1$ denote the integer part of $d/(2k)$. We show that the random $d$-regular graph a.a.s. has a $k$-star decomposition such that the number of stars centered at each vertex is either $s$ or $s+1$. Moreover, if $k < d/3$ or $k \leq d/2 - 2.6 \log d$, we can even prescribe the set of vertices with $s$ stars, as long as it is of the appropriate size.

Figures

Figures reproduced from arXiv: 2506.05194 by the authors.

Figure 1
Figure 1. The function 𝐹 (︂ 𝛽, 1 + 2𝛽 2 + 𝛽 )︂⧸︂𝐻(𝛽) compared to − 1 9 , proving that the strong condition holds whenever 𝑘 < 𝑑 4 Recall that 𝑑 = 2𝑠𝑘 + 𝑟 and 𝛽 = {︂ 𝑑 2𝑘 }︂ = 𝑟 2𝑘 . We start with the case 𝑘 < 𝑑/4. Then 𝑠 ≥ 2, and hence 𝑑 − 2𝑘 + 𝑟 𝑑 = 1 − 2𝑘 − 𝑟 2𝑠𝑘 + 𝑟 = 1 − 2𝑘(1 − 𝛽) 2𝑘(𝑠 + 𝛽) = 1 − 1 − 𝛽 𝑠 + 𝛽 ≥ 1 − 1 − 𝛽 2 + 𝛽 = 1 + 2𝛽 2 + 𝛽 . According to Proposition 3.3(ii) 𝐹(𝑥, 𝑡) is monotone decreasing in 𝑡, and hence … view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

5 extracted references · 4 canonical work pages

  1. [1]

    Decomposing random regular graphs into stars.arXiv, (2308.16037), 2023

    Michelle Delcourt, Catherine Greenhill, Mikhail Isaev, Bernard Lidick´ y, and Luke Postle. Decomposing random regular graphs into stars.arXiv, (2308.16037), 2023

    work page arXiv 2023

  2. [2]

    Random 4-regular graphs have 3-star decompositions asymptotically almost surely.European Journal of Combinatorics, 72:97–111, 2018

    Michelle Delcourt and Luke Postle. Random 4-regular graphs have 3-star decompositions asymptotically almost surely.European Journal of Combinatorics, 72:97–111, 2018

    work page 2018

  3. [3]

    How to orient graphs?Combinatorics, Coll

    Andr´ as Frank and Andr´ as Gy´ arf´ as. How to orient graphs?Combinatorics, Coll. Math. Soc. J. Bolyai, 18:353–364, 1976

    work page 1976

  4. [4]

    Star decompositions and independent sets in random regular graphs.arXiv, (2503.09458), 2025

    Viktor Harangi. Star decompositions and independent sets in random regular graphs.arXiv, (2503.09458), 2025

    arXiv 2025

  5. [5]

    Nowhere-zero 3-flows and modulo k-orientations.Journal of Combinatorial Theory, Series B, 103(5):587–598, 2013

    L´ aszl´ o Mikl´ os Lov´ asz, Carsten Thomassen, Yezhou Wu, and Cun-Quan Zhang. Nowhere-zero 3-flows and modulo k-orientations.Journal of Combinatorial Theory, Series B, 103(5):587–598, 2013. HUN-REN Alfr´ed R´enyi Institute of Mathematics, Budapest, Hungary Email address:harangi@renyi.hu

    work page 2013

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.