Pith. sign in

REVIEW 4 major objections 5 minor 28 references

Packing tetrahedrons in edge-weighted graphs

T0 review · 4 major / 5 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 This paper proves that, for every $\mu>0$ and $t\in(0,1)$, every sufficiently large edge-weighted complete graph with minimum weighted degree at least $((1+3t)/4+\mu)n$ has a perfect packing by $K_4$s each of total weight more than $6t$.

desk verdict Settles the r=4 case of the BKL–Young conjecture, but the embedding-robustness step has two repairable gaps that need referee attention. read the letter →

arxiv 2506.07147 v1 pith:WF436HHC submitted 2025-06-08 math.CO

Wanting Sun , Shunan Wei , Donglei Yang This is my paper
classification math.CO MSC 05C7005C35
keywords edge-weightedgraphsheavyK4-factorweightedHajnal–Szemeréditheoremabsorptionmethodmulticolouredregularitylemmareachabilitytransferraltetrahedronpacking
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 a weighted analogue of the Hajnal–Szemerédi theorem for cliques of size four. It shows that if every vertex of a large edge-weighted complete graph has weighted degree at least $((1+3t)/4+\mu)n$, with all edge weights in $[0,1]$, then the vertices can be partitioned into disjoint $K_4$s each of total edge weight exceeding $6t$. This confirms the tetrahedron case of a conjecture that had already been settled for triangles, and the degree threshold is asymptotically best possible. The proof combines the absorption method with a multicoloured regularity lemma, and introduces geometric facts about heavy faces of a heavy $K_4$ that may be useful for larger cliques.

What carries the argument

The central object is the $t$-heavy $K_4$: a copy of $K_4$ whose six edge weights sum to more than $6t$. The argument is carried by three pieces: (i) the multicoloured regularity lemma and the associated weighted reduced graph, whose edge weight between two clusters is the colour-weighted sum of densities; (ii) an embedding lemma asserting that a heavy $K_4$ in the reduced graph yields linearly many vertex-disjoint heavy $K_4$s in the original graph; and (iii) the reachability/transferral framework, where two vertices are reachable if a small connector set completes each of them to a heavy $K_4$-factor, and parts are merged by finding index vectors that survive deletion of $\beta n$ vertices and whose difference is a unit transferral. Proposition 2.13 supplies the geometric engine: a heavy triangle plus a vertex with weight $>3t$ to it, or two disjoint heavy edges with mutual weight $>4t$, produces a heavy $K_4$ containing at least two heavy triangles and two heavy edges.

What would settle it

A concrete test: for fixed $t$ (say $t=1/2$) and large $n$ divisible by $4$, search for an edge-weighted complete graph with minimum weighted degree at least $((1+3t)/4+0.01)n$ that has no $t$-heavy $K_4$-factor. A finer local test checks the embedding lemma: build a two-coloured weighted graph whose reduced graph has a heavy $K_4$, but every transversal picking one vertex from each of the four corresponding clusters has total weight at most $6t$; such an example would invalidate the transferral step.

Watch

Extended reading notes

Core claim

The central discovery is that the weighted degree threshold $(1+3t)/4+o(1)$ forces a $t$-heavy $K_4$-factor, with the bound asymptotically optimal. The proof rests on two structural lemmas: an absorbing lemma and an almost-cover lemma. The almost-cover step selects a maximal family of heavy $K_4$s each containing at least two heavy triangles and two heavy edges, then shows the leftover is tiny by a lexicographic augmentation argument. The absorbing step shows that, under the degree condition, all but $o(n)$ vertices can be made $32$-reachable in pairs, so each set of four vertices admits linearly many disjoint absorbers. The paper thus turns a pure existence conjecture into a constructive mechanism: heavy $K_4$s can be packed densely, and the uncovered residue can be absorbed.

Load-bearing premise

The proof depends on a standard but unproved claim that a single heavy $K_4$ in the regularized skeleton of the graph can be expanded into many disjoint heavy $K_4$s in the actual graph; if that expansion needs stricter conditions than the paper states, the absorbing-set construction collapses.

Editorial extensions

If this is right

  • The threshold $((1+3t)/4+o(1))n$ is asymptotically best possible for $r=4$: the extremal construction with a large block of weight-$t$ edges shows no smaller bound can work.
  • For every fixed $t\in(0,1)$ and every sufficiently large $n$ divisible by $4$, the theorem guarantees a perfect $t$-heavy $K_4$-factor, so the conjecture is now confirmed for $r=2,3,4$.
  • The almost-cover lemma pins down the uncovered leftover explicitly: at most $9+3/\mu$ vertices remain after the greedy $K_4$-packing, and the absorbing set then swallows them, producing a perfect factor.
  • In any maximal family chosen as in the proof, at most three heavy triangles, $1/\mu$ heavy edges, and $1/\mu$ leftover vertices can survive, which is why the almost-cover is so strong.

Reading between the lines

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

  • The same heavy-face geometry may transfer to the $r=5$ case: the concrete obstacle is the failure to guarantee a reachable pair among every constant-size vertex set under the threshold $(1+4t)/5+o(1)$, so a quantitative strengthening of the reachability lemma would likely unlock the next case.
  • The unstated inflation lemma is the riskiest tool: a computational search over small regular partitions could check whether a heavy $K_4$ in the reduced graph always yields linearly many disjoint heavy $K_4$s in the original graph; a single counterexample would not disprove the theorem but would expose where the proof needs repair.
  • The factor $32$ in the reachability parameter comes from iterating the merging lemma twice; tightening that chain would shrink the exceptional set $B$, potentially lowering the threshold's additive $\mu$ term in practice.
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

4 major / 5 minor

Summary. The paper proves Theorem 1.3: for every μ>0 and t∈(0,1), every sufficiently large n-vertex edge-weighted complete graph with minimum weighted degree at least ((1+3t)/4+μ)n contains a K4-factor in which each copy of K4 has total edge weight greater than 6t. This confirms Conjecture 1.2 for r=4. The proof combines a multicolored regularity lemma with an embedding lemma for heavy K4's, several geometric observations about heavy faces in tetrahedra, an almost-cover argument via maximal families of heavy K4's, and a lattice-based absorption framework in the spirit of Nenadov--Pehova and Han--Morris--Wang--Yang.

Significance. If the proof is completed, this resolves the next open case of the weighted Hajnal--Szemerédi conjecture of Balogh--Kemkes--Lee--Young, extending the triangle case proved by Balogh--Molla--Sharifzadeh. The paper contains several genuinely useful ingredients, most notably Proposition 2.13 on forced heavy triangles and heavy edges in heavy K4's, and the systematic use of transferrals in the reduced graph. It also ships detailed appendices for the standard absorbing machinery. However, the transferral step, which is load-bearing for the absorbing lemma, depends on an under-specified embedding lemma and on a robustness-counting step that is not justified as written. These gaps appear fixable, but they need to be addressed before the proof is fully rigorous.

major comments (4)
  1. [Section 2.2, Lemma 2.12] The proof of Lemma 2.12 is incomplete for pairs with w_ij=0. The text says 'arbitrarily pick ℓ_ij∈[p]', but if the chosen color has density 0 in G' between V_i and V_j, then G'_{ℓ_ij}[V_i,V_j] is empty and provides no edges into which to embed the K4. The proof should either choose a color with positive density for zero-weight pairs or explicitly embed such edges using the complete bipartite graph G[V_i,V_j] after verifying the required regularity and density hypotheses. This matters because Lemma 2.12 is the pivot that transfers heavy K4's from the reduced graph to linearly many vertex-disjoint heavy K4's in G.
  2. [Section 4.3, Claim 4.11] Claim 4.11 asserts that two heavy K4's in the reduced graph R with index difference u_1−u_2 yield two 4-vectors in I_P^{2β}(G,K4). This does not follow from Lemma 2.12 as stated, because Lemma 2.12 produces only βn vertex-disjoint copies. A forbidden set W of size 2βn can meet every one of those βn copies by taking one vertex from each, so no copy is guaranteed to survive in G−W. To certify (K4,2β)-robustness one needs at least (2β+1)n copies, i.e. Lemma 2.12 must be applied with a parameter β_emb≫2β and with a hierarchy such as β≪β_emb≪ε. Without this correction, the transferral argument in Lemma 4.9, and hence Lemma 4.4, does not formally go through.
  3. [Section 4.2, Fact 4.10] Fact 4.10 is used in the proof of Lemma 4.7 to chain reachability, but it is stated without proof and its hypotheses are imprecise. The statement does not say whether the m1 witnessing vertices are required to lie outside the forbidden set W, nor does it justify the constant m=min{m1−1,m2−4s}. Since Lemma 4.7 is a central structural step in proving Lemma 4.4, this fact needs a precise statement with a proof or a specific reference.
  4. [Section 4.3, Lemma 4.4] The constant hierarchy in the proof of Lemma 4.4, written as '1/n ≪ β, 1/k ≪ ε ≪ 1/p, β1 ≪ γ ≪ β′ ≪ μ', does not order β with respect to β1, γ, and β′. Later the proof asserts 'As β≪β′−γ' in the first case and uses β also in the second case for Claim 4.11. The hierarchy should explicitly include β≪β1 and β≪β′−γ (or an equivalent ordering) so that both uses of β are justified. This is a local, fixable issue but it is necessary for the proof of Lemma 4.4.
minor comments (5)
  1. [Lemma 2.11] The phrase 'edge-weigthed reduced graph' contains a typo and should read 'edge-weighted reduced graph'.
  2. [References] In reference [4], the author name 'Sharifzeadeh' should be 'Sharifzadeh'.
  3. [Notation throughout Section 4] Expressions such as w(v1v2v3, v4v5) and w(V(K_{r−1}), u) are used without a formal definition; the intended meaning is clear but a short notational remark would improve readability.
  4. [Fact 2.7] The statement of Fact 2.7 could be clarified by spelling out that the conclusion holds separately for every color ℓ∈[p] and by giving the standard one-paragraph proof, since this fact is used in Appendix A.
  5. [Appendix A] In the cleaning step of Appendix A, after subdividing clusters into smaller blocks, the text invokes Fact A.1 but does not explicitly verify that the density lower bound 'either 0 or at least d_ℓ' is preserved; a short explanation would prevent ambiguity.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: Theorem 1.3 is derived from the weighted degree condition through regularity and absorption tools, with the only in-house citations backed by appended proofs.

full rationale

The derivation chain for Theorem 1.3 is genuine: it reduces the theorem to an absorbing lemma (Lemma 2.3) and an almost-cover lemma (Lemma 2.4). The almost-cover proof is a lexicographic maximality argument using Proposition 2.13 and the weighted degree condition, with no step defining the target factor in terms of itself. The absorbing construction uses the lattice-based absorption framework of Nenadov--Pehova [22] and Han--Morris--Wang--Yang [14]; the latter is partly self-citational since Yang is a co-author, but Lemma 4.3 is proved in Appendix C and Lemma 4.9 in Appendix D, so the argument does not rest on an unverified self-citation. Lemma 2.12 transfers a heavy K4 in the reduced graph to linearly many disjoint heavy K4s in the original graph; although its proof has a minor technical gap for zero-weight cluster pairs (it arbitrarily picks a color that may have zero density), this is a correctness/tooling gap rather than circularity, because the reduced-graph heavy K4 is not defined in terms of the desired K4-factor. The degree threshold (1+3t)/4+mu is the conjecture's input, and the proof derives the factor from it; no fitted parameter is renamed as a prediction. The concluding remarks honestly identify limits for larger r. Thus there is no self-definitional reduction, no fitted input called prediction, and no load-bearing self-citation chain. Score 1 reflects only the presence of minor self-citations in the absorption framework, which are not load-bearing.

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

The theorem rests on standard regularity and absorption methods. The only nonstandard items are the unproved Fact 4.10 and the unstated embedding lemma; both are tools, not free parameters or invented entities.

assumptions (4)
  • standard math Szemerédi's regularity lemma in multicolored form (Theorem 2.8, from [1]).
    Used to obtain the regular partition and degree form in Section 2.2.
  • standard math Existence of a standard embedding lemma for regular pairs (invoked in Lemma 2.12).
    The paper does not state or prove the embedding lemma that turns a heavy K4 in the reduced graph into linearly many vertex-disjoint heavy K4s.
  • ad hoc to paper Fact 4.10 (reachability chaining).
    Stated without proof in Section 4.2; used in Lemma 4.7 to build reachability partitions.
  • domain assumption Lemma 4.5 from Balogh, Kemkes, Lee and Young [3] that every vertex lies in many heavy K4s.
    Used in the proof of Lemma 2.3 to cover the exceptional set B.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Packing tetrahedrons in edge-weighted graphs." pith.science (2026). https://pith.science/paper/WF436HHC

@misc{pith2026250607147,
  author       = {Pith},
  title        = {Pith review of: Packing tetrahedrons in edge-weighted graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WF436HHC}},
  note         = {Machine review of arXiv:2506.07147}
}
abstract

We prove that for all $\mu>0, t\in (0,1)$ and sufficiently large $n\in 4\mathbb{N}$, if $G$ is an edge-weighted complete graph on $n$ vertices with a weight function $w: E(G)\rightarrow [0,1]$ and the minimum weighted degree $\delta^w(G)\geq (\tfrac{1+3t}{4}+\mu)n$, then $G$ contains a $K_4$-factor where each copy of $K_4$ has total weight more than $6t$. This confirms a conjecture of Balogh--Kemkes--Lee--Young for the tetrahedron case.

Figures

Figures reproduced from arXiv: 2506.07147 by the authors.

Figure 1
Figure 1. Claim 3.1. Proof. Suppose that M = {e1, e2, . . . , eK} with ei = uiu ′ i and K > 1 µ . By a similar argument as Claim 3.1, we obtain that there exists a heavy K4, say R ∈ R with V (R) = {v1, v2, v3, v4}, satisfying w(∪ K i=1ei , R) ≥ 2K(1 + 3t + 3µ). Without loss of generality, assume that w(ei , R) ≥ w(ej , R) and w(ui , R) ≥ w(u ′ i , R) for each 1 ≤ i < j ≤ K. Hence w(e1, R) > 2(1 + 3t) and w(e2, R) ≥ 2K(1 + 3t … view at source ↗
Figure 2
Figure 2. w(v2, e1) > 2t. e1 e2 v1 v2 v3 v4 [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 4
Figure 4. v1v2v4 is a heavy triangle. Combining Claims 3.1-3.3, we know that at most 9 + 3 µ vertices are not covered by R. This completes the proof. 11 [PITH_FULL_IMAGE:figures/full_fig_p011_4.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

28 extracted references · 27 canonical work pages

  1. [1]

    A version of Szemer\'edi's regularity lemma for multicolored graphs and directed graphs that is suitable for induced graphs

    M. Axenovich and R. Martin. A version of Szemer´ edi’s regularity lemma for multi- colored graphs and directed graphs that is suitable for induced graphs. arXiv preprint arXiv:1106.2871, 2016

    work page Pith review arXiv 2016

  2. [2]

    Balogh, D

    J. Balogh, D. Bradaˇ c, and B. Lidick´ y. Weighted Tur´ an theorems with applications to Ramsey-Tur´ an type of problems. J. Graph Theory, 2025.https://doi.org/10.1002/ jgt.23244

    work page 2025

  3. [3]

    Balogh, G

    J. Balogh, G. Kemkes, C. Lee, and S. J. Young. Towards a weighted version of the Hajnal– Szemer´ edi Theorem.Comb. Prob. Comput., 22(3):346–350, 2013

    work page 2013

  4. [4]

    Balogh, T

    J. Balogh, T. Molla, and M. Sharifzeadeh. Triangle factors of graphs without large inde- pendent sets and of weighted graphs. Random Struct. Algorithms, 49(4):669–693, 2016

    work page 2016

  5. [5]

    Chang, J

    F. Chang, J. Han, J. Kim, G. Wang, and D. Yang. Embedding clique-factors in graphs with lowℓ-independence number. J. Combin. Theory Ser. B, 161:301–330, 2023

    work page 2023

  6. [6]

    Chang, J

    Y. Chang, J. Han, Y. Kohayakawa, P. Morris, and G. O. Mota. Factors in randomly perturbed hypergraphs. Random Structures Algorithms, 60(2):153–165, 2022

    work page 2022

  7. [7]

    M. Chen, J. Han, G. Wang, and D. Yang.H-factors in graphs with small independence number. J. Combin. Theory Ser. B, 169:373–405, 2024

    work page 2024

  8. [8]

    Corr´ adi and A

    K. Corr´ adi and A. Hajnal. On the maximal number of independent circuits in a graph. Acta Math. Acad. Sci. Hungar., 14:423–439, 1963

    work page 1963

Show all 28 references
  1. [9]

    R. Diestel. Graph Theory, volume 173 of Graduate Texts in Mathematics. Springer, Berlin, Heidelberg, 6th edition, 2025

    2025

  2. [10]

    G. A. Dirac. Some theorems on abstract graphs. Proc. Lond. Math. Soc., s3-2(1):69–81, 1952

    1952

  3. [11]

    Erd˝ os and V

    P. Erd˝ os and V. T. S´ os. Some remarks on Ramsey’s and Tur´ an’s theorem. InCombinatorial theory and its applications, I-III (Proc. Colloq., Balatonf¨ ured,1969), volume 4 of Colloq. Math. Soc. J´ anosBolyai, pages 395–404. North-Holland, Amsterdam-London, 1970

    1969

  4. [12]

    J. Gao, S. Jiang, H. Liu, and M. Sankar. Generalized Ramsey–Tur´ an density for cliques. Forum Math. Sigma, 13:e78 1–27, 2025

    2025

  5. [13]

    Hajnal and E

    A. Hajnal and E. Szemer´ edi. Proof of a conjecture of P. Erd˝ os. Comb. Theory Appl., 2(4):601–623, 1970

    1970

  6. [14]

    J. Han, P. Morris, G. Wang, and D. Yang. A Ramsey-Tur´ an theory for tilings in graphs. Random Struct. Algorithms, 64(1):94–124, 2024

    2024

  7. [15]

    Keevash and R

    P. Keevash and R. Mycroft. A geometric theory for hypergraph matching. Memoirs Am. Math. Soc., 233(1098):vi–95, 2015

    2015

  8. [16]

    H. A. Kiersteadk and A. V. Kostochka. A short proof of the Hajnal–Szemer´ edi theorem on equitable colouring. Comb. Prob. Comput., 17(2):265–270, 2008. 19

    2008

  9. [17]

    Knierim and P

    C. Knierim and P. Su.K r-factors in graphs with low independence number. J. Combin. Theory Ser. B, 148:60–83, 2020

    2020

  10. [18]

    Koml´ os and M

    J. Koml´ os and M. Simonovits. Szemer´ edi’s regularity lemma and its applications in graph theory. In Combinatorics, Paul Erd˝ osis eighty, Vol. 2 (Keszthely, 1993), volume 2 of Bolyai Soc. Math. Stud., pages 295–352. J´ anos Bolyai Math. Soc., Budapest, 1996

    1993

  11. [19]

    K¨ uhn and D

    D. K¨ uhn and D. Osthus. Embedding large subgraphs into dense graphs. London Math. Soc. Lecture Note Ser., 365:137–167, 2009

    2009

  12. [20]

    K¨ uhn and D

    D. K¨ uhn and D. Osthus. The minimum degree threshold for perfect graph packings. Combinatorica, 29(1):65–107, 2009

    2009

  13. [21]

    Lo and K

    A. Lo and K. Markstr¨ om.F-factors in hypergraphs via absorption. Graphs and Combinatorics, 31(3):679–712, 2015

    2015

  14. [22]

    Nenadov and Y

    R. Nenadov and Y. Pehova. On a Ramsey-Tur´ an variant of the Hajnal-Szemer´ edi theorem. SIAM J. Discret. Math., 34(2):1001–1010, 2020

    2020

  15. [23]

    R¨ odl, A

    V. R¨ odl, A. Ruci´ nski, and E. Szemer´ edi. Perfect matchings in large uniform hypergraphs with large minimum collective degree. J. Combin. Theory Ser. A, 116(3):613–636, 2009

    2009

  16. [24]

    V. T. S´ os. On extremal problems in graph theory. In Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969), pages 407–410. Gordon and Breach, New York-London-Paris, 1970

    1969

  17. [25]

    T. D. Townsend. Extremal problems on graphs, directed graphs and hypergraphs. Phd thesis, University of Birmingham, 2015. Appendix A Proof of Lemma 2.9 We use the following fact to prove Lemma 2.9. F act A.1.Given constantsη > ε >0 and a bipartite graphG=X∪Y, if (X, Y) isε-reg...

    2015

  18. [26]

    Asε ′ ≤ ε2 4p and all but at mostε ′k′2 pairs (V ′ i , V′ j ) are ε′-regular inG, the number of vertices we have moved toV ′ 0 is at most ε′k′2 ·m ′2 ε 4 n ≤ ε 4 n

    After deleting these edges, we observe that the degree of any vertexv∈Vin graphG ℓ is 20 at leastd Gℓ(v)− ε 4 nfor eachℓ∈[p]. Asε ′ ≤ ε2 4p and all but at mostε ′k′2 pairs (V ′ i , V′ j ) are ε′-regular inG, the number of vertices we have moved toV ′ 0 is at most ε′k′2 ·m ′2 ε...

  19. [27]

    Asε ′ ≤ ε2 4p , the number of vertices we have moved toV ′ 0 in this stage is at most pε′n2 2 ε 2 n ≤ ε 4 n

    Now, in eachG ℓ, for every vertexv∈V, we delete at most (d ℓ + 2ε′)m′ ·k ′ + ε 4 n≤(d ℓ + ε 2 )n edges incident tov. Asε ′ ≤ ε2 4p , the number of vertices we have moved toV ′ 0 in this stage is at most pε′n2 2 ε 2 n ≤ ε 4 n. After the above process, we observe that for eachℓ∈...

  20. [28]

    Call this new exceptional setV 0 and the other blocks V1, . . . , Vk. Denote byG ′ the resulting spanning subgraph after removing. It is easy to check thatG ′ together with the vertex partitionP={V 0, V1, . . . , Vk}satisfies properties (1), (2), (4) and (5) by Fact A.1. For e...

Pith tools

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