Pith. sign in

REVIEW 2 major objections 4 minor 15 references

Complete tripartite subgraphs of balanced tripartite graphs with large minimum degree

T0 review · 2 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read A small degree surplus over n forces complete tripartite subgraphs, including the octahedral graph, and the conjectured square-root threshold holds under a partial-degree condition.

desk verdict The stress-test note is correct: Theorem 1.5's proof has a numerical contradiction that breaks the argument, but the paper still contains a solid Theorem 1.4 and useful constructions. read the letter →

arxiv 2411.19773 v2 pith:SAODCCL3 submitted 2024-11-29 math.CO

Yihan Chen , Jialin He , Allan Lo , Cong Luo , Jie Ma , Yi Zhao This is my paper · ORCID
classification math.CO MSC 05C1505C35
keywords octahedralgraphcompletetripartitesubgraphsminimumdegreeZarankiewiczboundbalancedgraphsC6-blow-upextremaltheorytrianglecounting
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 studies a 1975 extremal-graph problem: how large must the minimum degree of a balanced tripartite graph with $n$ vertices in each part be to force a copy of $K_3(2)$, the octahedral graph. Its first theorem shows that $\delta(G) \ge n + 2n^{5/6}$ suffices, improving the earlier $n + (1+o(1))n^{11/12}$ bound and extending the argument to $K_3(s)$ with surplus $2(s-1)^{1/(s+1)}n^{1-1/(s(s+1))}$. Its second theorem confirms the original square-root conjecture under an extra condition: if every vertex also has at least $(1/5+7/c)n$ neighbours in each of the other two parts, then $\delta(G) \ge n + 305c^4\sqrt n$ forces a $K_3(2)$. The paper also builds $K_3(2)$-free tripartite graphs with minimum degree $n + (1-o(1))\sqrt n$, so the square-root order of the surplus cannot be lowered. A note added in proof records that the unconditional conjecture has since been settled elsewhere.

What carries the argument

The counting engine is the triangle count $T(xy)$ of an edge $xy$, together with the identity $d^+(y)+d^-(y)\ge n+t$ that follows from the minimum-degree condition. The proof of Theorem 1.4 double-counts triangles through a $t$-set $T_1$ and, for each $x\in T_1$, a $t$-set $T_x$ of its backward neighbours, applies convexity to pass from average triangle counts to many $s$-tuples, and then invokes the standard extremal bound on $K_{s,s}$-free bipartite graphs (the Zarankiewicz bound) to force a complete $K_{s,s}$; together with the chosen $s$ vertices this is $K_3(s)$. The square-root result is carried by a structural lemma: under $\delta\ge n$ and a positive linear one-sided minimum $\delta^+\ge 2\varepsilon n$, a $K_3(2)$-free graph must be nearly a blow-up of a six-cycle, with six parts $W_1,\ldots,W_6$ of size about $\delta^+(G)$ that are cyclically almost complete. A second structural lemma shows that two such six-cycle blow-ups, one from the forward orientation and one from the backward orientation, cannot coexist without creating a $K_3(2)$.

What would settle it

A concrete way to test Theorem 1.4 would be to search for an infinite family of balanced tripartite graphs with $\delta(G)\ge n+2n^{5/6}$ and no $K_3(2)$; the theorem predicts no such family exists for large $n$. For the conditional theorem, one could try to build a $K_3(2)$-free graph satisfying $\delta(G)\ge n+305c^4\sqrt n$ and partial degrees above $(1/5+7/c)n$; the theorem predicts this is impossible, and the proof's $C_6$-blow-up lemmas identify exactly where such a graph would have to break the structure.

Watch

Extended reading notes

Core claim

The central claim is that a small surplus over $n$ in the minimum degree controls complete tripartite subgraphs. Theorem 1.4 states that for every $s\ge 2$ and sufficiently large $n$, every balanced tripartite graph $G_3(n)$ with $\delta(G)\ge n + 2(s-1)^{1/(s+1)}n^{1-1/(s(s+1))}$ contains $K_3(s)$; the $s=2$ case is the octahedron guarantee $\delta(G)\ge n+2n^{5/6}$. Theorem 1.5 states that with minimum partial degree at least $(1/5+7/c)n$, the weaker surplus $\delta(G)\ge n+305c^4\sqrt n$ still forces $K_3(2)$, matching the conjectured square-root form under this extra hypothesis. The proof actually establishes a slightly stronger inequality involving the one-sided minima $\delta^+(G)$ and $\delta^-(G)$, and the $K_3(2)$-free graphs admissible to the argument are shown to be nearly a blow-up of a six-cycle.

Load-bearing premise

The square-root theorem assumes, in addition to the degree condition, that every vertex is adjacent to at least about one-fifth of the vertices in each of the other two classes; without this partial-degree floor, the six-cycle blow-up structure and the inequalities that drive the proof are not available.

Editorial extensions

If this is right

  • For $s=2$, every balanced tripartite graph with minimum degree at least $n+2n^{5/6}$ contains an octahedral subgraph, improving the previous $n+(1+o(1))n^{11/12}$ threshold.
  • For every fixed $s$, a surplus of order $n^{1-1/(s(s+1))}$ forces $K_3(s)$; in particular, the surplus is sublinear for every $s$.
  • Under the partial-degree floor $(1/5+7/c)n$, the conjectured square-root minimum degree $n+305c^4\sqrt n$ forces $K_3(2)$, confirming the conjecture in this restricted setting.
  • The new constructions produce many $K_3(2)$-free tripartite graphs with minimum degree $n+(1-o(1))\sqrt n$, so the square-root surplus in the conjecture cannot be replaced by anything smaller in order of magnitude.
  • A note added in proof records that the unconditional form of the problem has since been settled; the present results stand as stronger bounds before that settlement and as a structural proof of the conditional form.

Reading between the lines

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

  • The six-cycle blow-up description suggests that the full conjecture could be approached by proving the remaining case in which both one-sided minima $\delta^+(G)$ and $\delta^-(G)$ are $o(n)$; the paper's closing remarks leave this case open.
  • The large constant $305c^4$ in the conditional theorem is far from the order of the extremal examples at $n+(1-o(1))\sqrt n$, so the sharp constant in front of $\sqrt n$ is a natural target; one testable avenue is to run the structural lemmas with smaller error parameters in place of $c^{-1}n$.
  • The triangle lower bound $f(n,t)\ge n^2(3t-n)/2$ may be reusable as a template for counting octahedra rather than triangles: a similar complement-counting identity could convert a surplus over $n+\sqrt n$ directly into a lower bound on the number of $K_3(2)$ copies, which would give an independent route to the conjecture.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 4 minor

Summary. The paper studies balanced tripartite graphs G=G3(n) and the minimum degree that forces a complete tripartite subgraph K3(s), with special attention to the octahedral graph K3(2). Theorem 1.4 gives a double-counting proof that δ(G) ≥ n + C n^{1-1/(s(s+1))} with C=2(s-1)^{1/(s+1)} forces K3(s), improving a bound of Bhalkikar and Zhao; the particular case s=2 yields δ(G) ≥ n + 2 n^{5/6}. Theorem 1.5 claims that, under an additional strong hypothesis on the minimum partial degree, δ(G) ≥ n + 305 c^4 n^{1/2} forces K3(2), which would qualitatively confirm the Bollobás–Erdős–Szemerédi conjecture in that restricted setting. Proposition 1.6 gives a lower bound on the minimum number of triangles in such graphs by n^2(3t-n)/2, with an extremal construction when n is even and t≥n/2. Section 4 supplies explicit K3(2)-free constructions with minimum degree n+(1-o(1))n^{1/2} and a gluing operation producing further examples. A note added in proof records that Problem 1.2 was subsequently settled by Di Braccio and Illingworth.

Significance. The double-counting proof of Theorem 1.4 is clear, self-contained, and its final comparison with the Zarankiewicz bound checks out; this is a genuine technical improvement over the previous bound, although the note added in proof indicates that the problem has since been settled with a stronger n+K n^{1-1/s} threshold. Proposition 1.6 is a nice, clean result giving an exact value of f(n,t) for even n and t≥n/2, and the constructions in Section 4 are explicit and verifiable. The main concern is Theorem 1.5: as written, its proof contains a numerical error that invalidates the reduction to Lemma 3.3, so the paper's headline conditional confirmation of the Bollobás–Erdős–Szemerédi conjecture is not established. If that theorem is repaired or removed and the paper is reframed around the results that remain new, the remaining content is publishable, but the current version cannot be accepted as it stands.

major comments (2)
  1. [Section 3, proof of Theorem 1.5] The displayed chain after (3.2) is arithmetically false. With α=(35c)^{-2}, the sets S_i^+ and S_i^- each have size 4α^{-2}√n, so n'=n-8(35c)^4√n and the deletion loss is 24α^{-2}√n = 24(35c)^4√n = 36,015,000 c^4√n. The paper claims δ(G') ≥ n+305c^4√n - 24(35c)^4√n ≥ n'+28c^2√n', but the middle expression is n-(36,015,000-305)c^4√n, which is far below n'=n-12,005,000c^4√n; indeed even δ(G')≥n' is not guaranteed. Consequently Lemma 3.3 cannot be applied and the final contradiction is unsupported. This is not a typo in a single constant: the later requirement T_{G'}(uv)≤n'/(30c)^2 forces α≤1/(900c^2), hence α^{-2}≥8.1×10^5 c^4, making the deletion loss at least 24·8.1×10^5 c^4√n, which already dwarfs the assumed excess 305c^4√n. The proof of Theorem 1.5 is therefore invalid as written; either the constant 305 must be replaced by a much larger one (of order at least 10^7–10^8 c^4 for this strategy) or the argument must be substantially reworked.
  2. [Note added in proof and Introduction] The note added in proof states that Problem 1.2 was settled by Di Braccio and Illingworth with a bound n+K n^{1-1/s} for K3(s). This supersedes Theorem 1.4: for s=2 it gives the conjectured n+O(√n) threshold, and for general s the exponent 1-1/s is smaller than 1-1/(s(s+1)). Since Theorems 1.4 and 1.5 are the paper's advertised main results, the manuscript should explicitly say in the introduction which contributions remain new after [5]—primarily Proposition 1.6 and the Section 4 constructions—and should not present an improved bound for a problem that has already been solved. This is a matter of framing and significance, not of mathematical correctness, but it is load-bearing for the paper's contribution claim.
minor comments (4)
  1. [Section 2, proof of Theorem 1.4] The symbol T(xy) is used both for the number of triangles containing edge xy and, later in the same proof, T(z1,...,zs) is defined as a set of edges; this overloading is confusing and should be renamed, for example E(z1,...,zs).
  2. [Section 3, around (3.6)] The constants 13√α and 5α in the estimates for |Wi| and |Uj| are not derived in the text; a short explanation of how they follow from Claim 3.5 (v) and (vii) would improve readability.
  3. [Section 4, Construction 4.1] The line 'B1 = B2 ∪ B3' is informal, since B2 and B3 are subsets of different vertex classes; the intended meaning is that B1 is partitioned into two sets of size t each, and this should be said explicitly.
  4. [Abstract] The sentence 'Bollobás, Erdős, and Szemerédi conjectured that n+cn^{1/2} suffices and there are many K3(2)-free tripartite graphs...' could be misread as saying the existence of such graphs is part of the conjecture; a semicolon or separate sentence would remove the ambiguity.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: Theorems 1.4 and 1.5 are proved by direct double counting and self-contained lemmas; self-citations are prior results being improved, not load-bearing inputs.

full rationale

I walked the derivation chains of Theorems 1.4 and 1.5. Theorem 1.4 is a double-counting proof built on the standard Kővári–Sós–Turán bound (Lemma 2.1); no parameter is fitted to the conclusion, and the constant C is chosen only to make the final inequality cross z(t,n;s,s). Theorem 1.5 is conditional and self-contained: it deletes small exceptional sets S_i^+ and S_i^- to form G', then invokes Lemmas 3.2 and 3.3, both proved in the paper from elementary counting arguments. The extra minimum-partial-degree hypothesis is a genuine strengthening of the hypotheses, not a restatement of the target K3(2). The self-citations ([2] by Bhalkikar and Zhao and [11] by Lo, Treglown, and Zhao) are prior results that the paper improves or surveys; they are not cited as the justification for the main estimates. The suspicious arithmetic in the δ(G') bound, where 24(35c)^4 swamps 305c^4, is a potential correctness defect, not a circularity: the claimed lower bound is not equivalent to the assumed degree by construction. The note added in proof discloses an external independent settlement of the problem. No circular step is present.

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

The results are pure extremal graph theory: no empirical data, no fitted parameters, no new postulated objects. The only hand-chosen numbers are explicit theorem constants chosen to make inequalities close. Proofs rely on standard results such as the Zarankiewicz bound and regular bipartite graphs from finite fields, plus the standard assumption of sufficiently large n.

free parameters (2)
  • C in Theorem 1.4 = C = 2(s-1)^(1/(s+1))
    Chosen by hand so that (C/2)^(s+1) = s-1, which closes the double-counting inequality; not fitted to data.
  • Constant 305 in Theorem 1.5 = 305
    Explicit large constant in the degree threshold n + 305 c^4 sqrt(n); selected to absorb error terms from deleting exceptional sets. Arbitrary.
assumptions (3)
  • standard math Kovari-Sos-Turan bound on z(m,n;s,s)
    Lemma 2.1, cited from [10]; used in Theorem 1.4 and Lemma 3.1 to force K_{s,s} in dense bipartite graphs.
  • standard math Existence of K2,2-free (q+1)-regular bipartite graphs for prime power q (Reiman [13])
    Used in Section 4 as the building block for K3(2)-free constructions with minimum degree n + (1-o(1)) sqrt(n).
  • domain assumption n sufficiently large (n >= n0(c)) for all main theorems
    Theorems 1.4 and 1.5 and Proposition 1.6 are asymptotic statements; constants depend on c and the constructions require large n.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Complete tripartite subgraphs of balanced tripartite graphs with large minimum degree." pith.science (2026). https://pith.science/paper/SAODCCL3

@misc{pith2026241119773,
  author       = {Pith},
  title        = {Pith review of: Complete tripartite subgraphs of balanced tripartite graphs with large minimum degree},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SAODCCL3}},
  note         = {Machine review of arXiv:2411.19773}
}
abstract

In 1975 Bollob\'{a}s, Erd\H{o}s, and Szemer\'{e}di asked what minimum degree guarantees an octahedral subgraph $K_3(2)$ in any tripartite graph $G$ with $n$ vertices in each vertex class. We show that $\delta(G)\geq n+2n^{\frac{5}{6}}$ suffices thus improving the bound $n+(1+o(1))n^{\frac{11}{12}}$ of Bhalkikar and Zhao obtained by following their approach. Bollob\'{a}s, Erd\H{o}s, and Szemer\'{e}di conjectured that $n+cn^{\frac{1}{2}}$ suffices and there are many $K_3(2)$-free tripartite graphs $G$ with $\delta(G)\geq n+cn^{\frac{1}{2}}$. We confirm this conjecture under the additional assumption that every vertex in $G$ is adjacent to at least $(1/5+\varepsilon)n$ vertices in any other vertex class.

Figures

Figures reproduced from arXiv: 2411.19773 by the authors.

Figure 1
Figure 1. Graph of Lemma 3.3. Proof of Theorem 1.5. This proof of the theorem actually proves the following slightly stronger statement: For every c ≥ 58, there exists n0 = n0(c) such that every tripartite graph G = G3(n) with n ≥ n0, δ(G) ≥ n + 305 c 4n 1 2 and 2δ +(G) + 2δ −(G) + max{δ +(G), δ−(G)} ≥ 1 + 35c −1  n (3.1) contains a K3(2). Suppose to the contrary that there exists a K3(2)-free tripartite graph G = G3(n) sati… view at source ↗
Figure 2
Figure 2. Graph in Construction 4.1. The condition n ≥ t 2 + t + 1 (which implies t(t − 1) ≤ n − 2t − 1) ensures that we can join every vertex of Bi to t vertices in Aj for i = 2, j = 3 and i = 3, j = 2, with the additional constraint that any two distinct vertices of Bi share at most one common neighbor in Aj . Furthermore, n ≥ 5t guarantees that each vertex in A1 has degree at least n + t. Thus, in this construction, the mi… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

  1. [5]

    Di Braccio and F

    F. Di Braccio and F. Illingworth, The Zarankiewicz problem on tripartite graphs, arXiv:2412.03505 (2024)

    work page arXiv 2024

  2. [1]

    Alon, The linear arboricity of graphs, Isr

    N. Alon, The linear arboricity of graphs, Isr. J. Math. 62(3) (1988), 311–325

    work page 1988

  3. [2]

    Bhalkikar and Y

    A. Bhalkikar and Y. Zhao, On subgraphs of tripartite graphs, Discrete Math. 346(1) (2023), 113152

    work page 2023

  4. [3]

    Bollob´ as, P

    B. Bollob´ as, P. Erd˝ os and E. G. Straus, Complete subgraphs of chromatic graphs and hypergraphs, Utilitas Math. 6 (1974), 343–347

    work page 1974

  5. [4]

    Bollob´ as, P

    B. Bollob´ as, P. Erd˝ os and E. Szemer´ edi, On complete subgraphs ofr-chromatic graphs, Discrete Math. 13(2) (1975), 97–107

    work page 1975

  6. [6]

    Erd˝ os, Unsolved problems, In Proceedings of the Conference on Combinatorial Mathematics held at the Mathematical Institute, 3-7 July 1972 (D

    P. Erd˝ os, Unsolved problems, In Proceedings of the Conference on Combinatorial Mathematics held at the Mathematical Institute, 3-7 July 1972 (D. J. A. Welsh and D. R. Woodall, eds) The Institute of Mathematics and its Applications (1972), pp. 351–363

    work page 1972

  7. [7]

    Haxell, A note on vertex list colouring, Combin

    P. Haxell, A note on vertex list colouring, Combin. Probab. Comput. 10(4) (2001), 345–347. 14

    work page 2001

  8. [8]

    Haxell and T

    P. Haxell and T. Szab´ o, Odd independent transversals are odd,Combin. Probab. Comput. 15(1-2) (2006), 193–211

    work page 2006

Show all 15 references
  1. [9]

    Jin, Complete subgraphs of r-partite graphs, Combin

    G. Jin, Complete subgraphs of r-partite graphs, Combin. Probab. Comput. 1(3) (1992), 241–250

    1992

  2. [10]

    K˝ ov´ ari, V

    T. K˝ ov´ ari, V. T. S´ os and P. Tur´ an, On a problem of Zarankiewicz,Colloq. Math. 3 (1954), 50–57

    1954

  3. [11]

    A. Lo, A. Treglown and Y. Zhao, Complete subgraphs in a multipartite graph, Combin. Probab. Comput. 31(6) (2022), 1092–1101

    2022

  4. [12]

    Mantel, Opgaven28, Wiskd

    W. Mantel, Opgaven28, Wiskd. Opgaven Met Oplossingen 10 (1907), 60–61

    1907

  5. [13]

    Reiman, ¨Uber ein Problem von K

    I. Reiman, ¨Uber ein Problem von K. Zarankiewicz, Acta Math. Acad. Sci. Hungar. 9 (1958), 269–273

    1958

  6. [14]

    Szab´ o and G

    T. Szab´ o and G. Tardos, Extremal problems for transversals in graphs with bounded degree, Combinatorica 26(3) (2006), 333–351

    2006

  7. [15]

    Tur´ an, On an extremal problem in graph theory (in Hungarian), Mat

    P. Tur´ an, On an extremal problem in graph theory (in Hungarian), Mat. Fiz. Lapok 48 (1941), 436–452. E-mail address: cyh2020@mail.ustc.edu.cn E-mail address: majlhe@ust.hk E-mail address: s.a.lo@bham.ac.uk E-mail address: luoc@mail.ustc.edu.cn E-mail address: jiema@ustc.edu....

    1941

Pith tools

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