Pith. sign in

REVIEW 1 major objections 5 minor 21 references

Tur\'{a}n Problems for Vertex-disjoint Cliques in Multi-partite Hypergraphs

T0 review · 1 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read This paper proves exact formulas for the maximum number of edges avoiding k vertex-disjoint cliques in r-partite s-uniform hypergraphs, including a multipartite analogue of the Erdős matching conjecture and two related Turán problems.

desk verdict A solid exact Turán paper that genuinely extends the known graph and r-uniform results to s-uniform multipartite hypergraphs; refereeable after minor presentational fixes. read the letter →

arxiv 1908.05983 v3 pith:ZMVHSYKQ submitted 2019-08-16 math.CO

Erica L.L. Liu , Jian Wang This is my paper · ORCID
classification math.CO MSC 05C3505C65
keywords Turánnumbermulti-partitehypergraphsErdősmatchingconjectureshiftingtechniqueprobabilisticargumentgeneralizedvertex-disjointcliquesrainbow
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

This paper is about Turán-type extremal problems in multipartite hypergraphs: given an r-partite host hypergraph whose edges choose at most one vertex from each of r parts, how many edges can a subgraph have if it contains no k vertex-disjoint copies of a fixed clique? The paper answers this exactly for three families of forbidden configurations. For k disjoint s-vertex cliques, which form a matching of size k, it determines the extremal number whenever the smallest part is at least a polynomial in s and k, giving a multipartite analogue of the Erdős matching conjecture. For k disjoint r-vertex cliques, it gives an exact formula for all k at most the size of the smallest part. It also gives exact counts of s-cliques in subgraphs of r-partite graphs that contain no k disjoint copies of the complete graph K_r, under two explicit size regimes.

What carries the argument

The proof rests on three mechanisms. First, a left-shifting operator $S_{uv}$ replaces a vertex $v$ by an earlier vertex $u$ in the same part when that does not create an existing edge; repeated application yields a stable graph with the same edge count and no larger matching number, so the extremal graph can be assumed closed under replacing vertices by earlier ones. Inside this stable world, the proof of Theorem 1.3 isolates the first vertex of each part, separates high- and low-degree vertices, shows every edge must touch $V_1$, and finishes with a double-counting argument over $r$-element transversals. A base lemma partitions the edge set of $K^{(r)}_{n_1,\ldots,n_r}$ into $n_2\cdots n_r$ matchings of size $n_1$, which drives the $s=r$ base case. Second, Theorems 1.4 and 1.5 use a probabilistic argument: choose one random vertex from each part, count the expected number of edges or $s$-cliques in the random $r$-set, upper-bound the expectation by the probability of hitting a $K_r$, and then solve a small linear program whose optimal value is the claimed formula. Third, Theorem 1.6 uses a rainbow-matching result: if every vertex of the last part creates $k$ disjoint $(r-1)$-cliques, those cliques form a colored $(r-1)$-graph whose rainbow matching would build a forbidden $kK_r$.

What would settle it

For parameters satisfying the stated inequalities, exhibit any $kK^{(s)}_s$-free subgraph of $K^{(s)}_{n_1,\ldots,n_r}$ with more than $(k-1)\sum_{A \subset [2,r], |A|=s-1} n_A$ edges; for example, at the smallest open parameter point $s=3, r=4, k=2, n_1=n_2=n_3=n_4=70$, this means deciding by search or integer programming whether a 3-partite 3-graph on four parts of size 70 can have more than $14{,}700$ edges and no two disjoint edges.

Watch

Extended reading notes

Core claim

The central discovery is that in each setting the natural ``put all edges through a small set'' construction is optimal. Theorem 1.3 states that for $2 \leq s \leq r$ and $n_1 \leq \cdots \leq n_r$, if $n_1 \geq s^3 k + sr$ for $s \leq r-2$, or $n_1 \geq s^3 k^2 + sr$ for $s = r-1$, or $n_1 \geq k$ for $s = r$, then $\operatorname{ex}_s(K^{(s)}_{n_1,\ldots,n_r}, kK^{(s)}_s) = (k-1)\sum_{A \subset [2,r], |A|=s-1} n_A$. The extremal graph keeps exactly the edges that meet a fixed $(k-1)$-subset of the first part, and no larger graph can avoid $k$ disjoint $s$-cliques. Theorem 1.4 gives $\operatorname{ex}_s(K^{(s)}_{n_1,\ldots,n_r}, kK^{(s)}_r) = \sum_{|A|=s} n_A - n_{[s]} + (k-1)n_{[2,s]}$ for $k \leq n_1$, with the extremal graph obtained by deleting all edges between a large subset of $V_1$ and $V_2$. Theorems 1.5 and 1.6 give exact values for the generalized Turán problem of maximizing the number of $K_s$ copies in a $kK_r$-free subgraph of an $r$-partite graph, the second using the condition $n_4 \geq r^r(k-1)k^{2r-2}$.

Load-bearing premise

The argument for Theorem 1.3 assumes the extremal graph can be taken stable under left-shifts, swapping a vertex for an earlier vertex in the same part without increasing the largest matching size, and every structural step in the proof depends on that stability.

Editorial extensions

If this is right

  • For $s = r$, Theorem 1.3 yields $\operatorname{ex}_r(K^{(r)}_{n_1,\ldots,n_r}, kK^{(r)}_r) = (k-1)n_2\cdots n_r$, so the edge partition into $n_2\cdots n_r$ matchings is optimal.
  • For $s = 2$, the results recover the known exact formulas for $\operatorname{ex}(K_{n_1,\ldots,n_r}, kK_2)$ and $\operatorname{ex}(K_{n_1,\ldots,n_r}, kK_r)$ as special cases.
  • The explicit formulas in Theorems 1.5 and 1.6 show that, for large enough last parts, the number of $K_s$ copies in a $kK_r$-free $r$-partite graph is maximized by a graph that is nearly complete except for all edges between a large subset of $V_1$ and $V_2$.
  • The hypotheses on $n_1$ are explicit polynomials in $s$ and $k$, giving effective ranges where the multipartite Erdős matching analogue holds exactly rather than asymptotically.

Reading between the lines

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

  • Beyond the paper's claims, the thresholds $n_1 \geq s^3 k$ and $n_1 \geq s^3 k^2$ appear to be artifacts of the induction and double-counting estimates; a natural next step is to determine the smallest $n_1$ for which the same extremal construction remains optimal.
  • The linear-programming lemma is generic: for any fixed forbidden family whose obstruction is controlled by the probability that a random $r$-set contains a forbidden clique, the same recipe should yield exact answers for shapes other than $K_r$.
  • Because the extremal graphs concentrate all edges on a small subset of the first part, the results suggest a strong stability property: every near-extremal $kK_s$-free subgraph must have most of its edges touching a small subset of $V_1$, which could be formulated as a stability theorem.
  • The rainbow-matching step only requires $n_4 \geq r^r(k-1)k^{2r-2}$; replacing it with a stronger rainbow-matching bound would immediately widen the range of Theorem 1.6.
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

1 major / 5 minor

Summary. The paper determines three Turán-type extremal numbers for vertex-disjoint cliques in r-partite s-uniform hypergraphs. Its central result, Theorem 1.3, gives the exact value of ex_s(K_{n_1,\ldots,n_r}^{(s)}, kK_s^{(s)}) for sufficiently large n_1, with the extremal construction consisting of all edges that touch a fixed (k-1)-subset of the first part. The companion Theorems 1.4--1.6 determine ex_s(K_{n_1,\ldots,n_r}^{(s)}, kK_r^{(s)}) for k ≤ n_1 and the generalized Turán number ex(K_{n_1,\ldots,n_r}, K_s, kK_r) under two sets of conditions. The proofs combine shifting/stability arguments, a decomposition of the complete r-partite r-graph into matchings, a probabilistic linear-programming argument, and a rainbow-matching bound imported from Glebov--Sudakov--Szabó. The paper also supplies a self-contained proof of the previously unpublished Theorem 1.1 of De Silva--Heysse--Young in an appendix.

Significance. If correct, the results give exact multipartite analogues of the Erdős matching conjecture in a substantial range, and they unify several previously known graph results: Theorem 1.3 specializes to Theorem 1.1 when s=2 and to Lemma 2.1 when s=r, and Theorem 1.4 recovers the r-uniform case. These external consistency checks are a genuine strength, as are the self-contained proofs of the shifting lemma and of Theorem 1.1. The probabilistic LP method is elegant and likely useful beyond this paper. I checked the boundary cases s=2 and s=r, the LP optimality argument, and the recurrences in the induction steps, and the algebra is internally consistent. The main concern is a missing t=0 case in the proof of Lemma 2.3; it is local and repairable, but it is load-bearing for Theorem 1.3 and the written proof is incomplete at that point.

major comments (1)
  1. [Section 2, Lemma 2.3, Case 2] The proof divides by t after combining inequality (2.1) with the bounds (2.2) and (2.7): inequality (2.3) is obtained from the preceding display by dividing by t, and inequality (2.8) is similarly obtained by dividing by t. However t = ν(H \setminus T_0) may be zero, in which case these divisions are invalid and the displayed conclusions become 0 ≤ 0. This is not a purely cosmetic issue, because (2.3) and (2.8) are the steps that produce the required contradiction. The authors should add a short separate treatment of t=0: in that case Claim 4 gives ν(H \setminus X) = 0, and since Y is nonempty, no edge of H \setminus X can contain a vertex of Y; hence every edge of H intersects X, so |Γ(T0)| ≤ |X| binom(r-1,s-1) n^{s-1} = (k-1) binom(r-1,s-1) n^{s-1}, contradicting (2.1). This repair is straightforward, but the proof as written is incomplete.
minor comments (5)
  1. [Section 3, Lemma 3.1] The statement defines a = w_{M+1}(b-M), but if b ≥ N then M = N and w_{N+1} is undefined. In the applications one has b < binom(r,s), so the intended range is sufficient, but the lemma should explicitly assume b < N or handle the boundary case separately.
  2. [Abstract and Theorem 1.3] The abstract states the condition n_1 ≥ s^3 k^2 + sr for Theorem 1.3, whereas the theorem itself only requires n_1 ≥ s^3 k + sr when s ≤ r-2. The abstract should either match the theorem or explicitly say that it states a simplified stronger sufficient condition.
  3. [Equations (3.2) and (4.2)] In both displayed equations the second conditional expectation is written as E(X(T)|A_T)Pr(A_T); it should be E(X(T)|\overline{A_T})Pr(\overline{A_T}). The intended meaning is clear from the context, but the notation should be corrected.
  4. [Section 2, Lemma 2.3, Claims 1 and 2] The proof uses the bounds n ≥ 2s^2k in Claim 1 and n ≥ 3s^2k in Claim 2 without stating them as hypotheses of Lemma 2.3. These follow from the stated assumptions n ≥ s^3k + sr for s ≥ 3, but it would be clearer to derive them explicitly before use.
  5. [Sections 4, lower bounds for Theorems 1.5 and 1.6] The lower-bound construction for the generalized Turán number is described and shown to be kK_r-free, but the text does not explicitly count the number of K_s copies it contains. Adding this short count would make the lower bound transparent rather than left to the reader.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the derivation is self-contained or rests on genuine external theorems.

full rationale

The paper's derivations are not circular. The main extremal upper bounds are obtained from explicit structural arguments rather than from fitted inputs. Theorem 1.3 relies on Lemma 2.2, Frankl's shifting lemma, but the lemma is restated with attribution to [9] and a proof is included for the r-partite partial order; it does not assume the target result, and termination is justified by the strictly decreasing potential g. Lemma 2.3 is proved by induction on k using an explicit contradiction argument with the degree classes X and Y, and inequality (2.1) is derived from the matching number t, not from the desired extremal value. Lemma 2.1, the balanced r-uniform case, is proved by partitioning the edge set into n_2 ... n_r matchings of size n_1, so it is not merely imported by citation. The s=2 base case uses Theorem 1.1, but the paper supplies a full proof in the Appendix, and Theorem 1.2 is an external result of De Silva et al. The probabilistic arguments for Theorems 1.4-1.6 use Lemma 3.1, whose proof is internal, and Theorem 4.1 is an external rainbow-matching bound of Glebov, Sudakov and Szabó. No parameter is fitted to a subset of data and then renamed a prediction; no extremal construction is defined in terms of the quantity it is claimed to determine; and no load-bearing assertion reduces to a self-citation. Presentational gaps, such as the unstated t=0 division in Lemma 2.3 Case 2, are exposition issues rather than circularity.

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

The central claims rest on six external results and one standard calculus fact. None of these are fitted or invented: Lemma 2.1 (Aharoni-Howard argument) bounds the number of r-cliques via the shadow r-graph; Theorem 1.1 supplies the s=2 base case and is re-proved in the appendix because the original preprint is unpublished; Theorem 1.2 supplies the graph base case of Theorem 1.6; Frankl's shifting lemma carries the stability reduction in Section 2; the Glebov-Sudakov-Szabó bound selects the regime of Theorem 1.6; and Lemma 3.1 is a standard greedy LP optimality fact. There are no free parameters: the extremal formulas f, g, h are determined by explicit deletion constructions, and every constant in the proofs is derived from the n_i and k rather than fitted. No invented entities appear; the auxiliary hypergraph H* of r-clique copies is a proof device, not a new object.

assumptions (7)
  • domain assumption Frankl's shifting lemma: ν(S_{uv}(H)) ≤ ν(H), so an extremal graph may be assumed stable under ≺ (Lemma 2.2, cited to [9], proof sketched).
    Used throughout Section 2 to justify the stable extremal form; supports Claims 1-4 and the induction step of Theorem 1.3. Standard in extremal set theory but imported.
  • domain assumption ex_r(K_{n1,...,nr}, kK^{(r)}_r) = (k-1)n2···nr (Lemma 2.1, by the Aharoni-Howard matching-partition argument).
    Bounds the number of K^{(s)}_r copies through the shadow r-graph in Theorems 1.4-1.6, and is the s=r case of Theorem 1.3; the proof partitions edges into n2···nr matchings of size n1.
  • domain assumption ex(K_{n1,...,nr}, kK2) = (k-1)(n2+...+nr) (Theorem 1.1, De Silva-Heysse-Young; full proof in Appendix A).
    Base case s=2 of the double induction in Theorem 1.3; reproduced because the original preprint is not published online.
  • domain assumption ex(K_{n1,...,nr}, kKr) = Σ_{i<j} n_i n_j - n1n2 + (k-1)n2 (Theorem 1.2, De Silva et al. [6]).
    Base case s=2 for Theorem 1.6 and the s=2 boundary case of the h^{(s)} formula.
  • domain assumption Glebov-Sudakov-Szabó rainbow matching bound f(r,k) < (r+1)^{r+1}(k-1)k^{2r} (Theorem 4.1, [13]).
    The regime n4 ≥ r^r(k-1)k^{2r-2} in Theorem 1.6 is chosen so nr > f(r-1,k); without this bound the rainbow-matching step fails.
  • standard math Greedy LP optimality (Lemma 3.1): max Σx_i with Σ x_i/w_i ≤ b, 0 ≤ x_i ≤ w_i is attained by filling the largest w_i, plus the fractional remainder.
    Converts the probabilistic expectation bound (3.3)/(4.3) into the exact extremal value in Theorems 1.4 and 1.5.
  • standard math Taylor's theorem with Lagrange remainder, used at (2.4) to lower-bound n^{s-1} - (n-1)^{s-1}.
    Produces the final contradictions in Lemma 2.3 by comparing n against the s³k thresholds.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Tur\'{a}n Problems for Vertex-disjoint Cliques in Multi-partite Hypergraphs." pith.science (2026). https://pith.science/paper/ZMVHSYKQ

@misc{pith2026190805983,
  author       = {Pith},
  title        = {Pith review of: Tur\'an Problems for Vertex-disjoint Cliques in Multi-partite Hypergraphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZMVHSYKQ}},
  note         = {Machine review of arXiv:1908.05983}
}
abstract

For two $s$-uniform hypergraphs $H$ and $F$, the Tur\'{a}n number $ex_s(H,F)$ is the maximum number of edges in an $F$-free subgraph of $H$. Let $s, r, k, n_1, \ldots, n_r$ be integers satisfying $2\leq s\leq r$ and $n_1\leq n_2\leq \cdots\leq n_r$. De Silva, Heysse and Young determined $ex_2(K_{n_1, \ldots, n_r}, kK_2)$ and De Silva, Heysse, Kapilow, Schenfisch and Young determined $ex_2(K_{n_1, \ldots, n_r},kK_r)$. In this paper, as a generalization of these results, we consider three Tur\'{a}n-type problems for $k$ disjoint cliques in $r$-partite $s$-uniform hypergraphs. First, we consider a multi-partite version of the Erd\H{o}s matching conjecture and determine $ex_s(K_{n_1, \ldots, n_r}^{(s)},kK_s^{(s)})$ for $n_1\geq s^3k^2+sr$. Then, using a probabilistic argument, we determine $ex_s(K_{n_1, \ldots, n_r}^{(s)},kK_r^{(s)})$ for all $n_1\geq k$. Recently, Alon and Shikhelman determined asymptotically, for all $F$, the generalized Tur\'{a}n number $ex_2(K_n,K_s,F)$, which is the maximum number of copies of $K_s$ in an $F$-free graph on $n$ vertices. Here we determine $ex_2(K_{n_1, \ldots, n_r}, K_s, kK_r)$ with $n_1\geq k$ and $n_3=\cdots=n_r$. Utilizing a result on rainbow matchings due to Glebov, Sudakov and Szab\'{o}, we determine $ex_2(K_{n_1, \ldots, n_r}, K_s, kK_r)$ for all $n_1, \ldots, n_r$ with $n_4\geq r^r(k-1)k^{2r-2}$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

21 extracted references · 20 canonical work pages

  1. [1]

    Aharoni and D

    R. Aharoni and D. Howard, A rainbow r-partite version of the Erd˝ os-Ko-Rado theo- rem, Combin. Probab. Comput. 26 (2017) 321–337

    work page 2017

  2. [2]

    Alon and C

    N. Alon and C. Shikhelman, Many T copies in H-free graphs, J. Combin. Theory Ser. B 121 (2016) 146–172

    work page 2016

  3. [3]

    Bennett, S

    P. Bennett, S. English and M. Talanda-Fisher, Weighted T ur´ an problems with appli- cations, Discrete Math. 342 (2019) 2165–2172

    work page 2019

  4. [4]

    Bollob´ as, On genaralized graphs, Acta Math

    B. Bollob´ as, On genaralized graphs, Acta Math. Acad. Sc i. Hungar. 16 (1965) 447– 452. 18

    work page 1965

  5. [5]

    Bollob´ as, D

    B. Bollob´ as, D. E. Daykin and P. Erd˝ os, Sets of independ ent edges of a hypergraph, Quart. J. Math. Oxford Ser. 21 (1976) 25–32

    work page 1976

  6. [6]

    De Silva, K

    J. De Silva, K. Heysse, A. Kapilow, A. Schenfisch and M. You ng, Tur´ an numbers of vertex-disjoint cliques in r-partite graphs, Discrete Math. 341 (2018) 492–496

    work page 2018

  7. [7]

    Erd˝ os, A problem on independent r-tuples, Ann

    P. Erd˝ os, A problem on independent r-tuples, Ann. Univ. Sci. Budapest. E¨ otv¨ os Sect. Math. 8 (1965) 93–95

    work page 1965

  8. [8]

    Frankl, An extremal problem for two families of sets, E uropean J

    P. Frankl, An extremal problem for two families of sets, E uropean J. Combin. 3 (1982) 125–127

    work page 1982

Show all 21 references
  1. [9]

    Frankl, The shifting technique in extremal set theory , Surv

    P. Frankl, The shifting technique in extremal set theory , Surv. Combin. 123 (1987) 81–110

    1987

  2. [10]

    Frankl, V

    P. Frankl, V. R¨ odl and A. Ruci´ nski, On the maximum numb er of edges in a triple system not containing a disjoint family of a given size, Comb in. Probab. Comput. 21 (2012) 141–148

    2012

  3. [11]

    Frankl, Improved bounds for Erd˝ os’ matching conjecture, J

    P. Frankl, Improved bounds for Erd˝ os’ matching conjecture, J. Combin. Theory Ser. A 120 (2013) 1068–1072

    2013

  4. [12]

    Frankl, On the maximum number of edges in a hypergraph with given matching number, Discrete Appl

    P. Frankl, On the maximum number of edges in a hypergraph with given matching number, Discrete Appl. Math. 216 (2017) 562–581

    2017

  5. [13]

    Glebov, B

    R. Glebov, B. Sudakov and T. Szab´ o, How many colors guar antee a rainbow match- ing? Electron. J. Combin. 21 (2014) #P1.27

    2014

  6. [14]

    Han and Y

    J. Han and Y. Zhao, Tur´ an number of disjoint triangles i n 4-partite graphs, arXiv e-prints (Jun. 2019) arXiv:1906.01812

    2019 arXiv

  7. [15]

    Keevash, Hypergraph Tur´ an problems, Surv

    P. Keevash, Hypergraph Tur´ an problems, Surv. Combin. 392 (2011) 83–140

    2011

  8. [16]

    Ma and Y

    J. Ma and Y. Qiu, Some sharp results on the generalized Tu r´ an numbers, European J. Combin. 84 (2019) https://doi.org/10.1016/j.ejc.2019 .103026

    2019 doi

  9. [17]

    Mantel, Problem 28, Wiskundige Opgaven 10 (1907) 60– 61

    W. Mantel, Problem 28, Wiskundige Opgaven 10 (1907) 60– 61

    1907

  10. [18]

    Sidorenko, What we know and what we do not know about Tu r´ an numbers, Graphs Combin

    A. Sidorenko, What we know and what we do not know about Tu r´ an numbers, Graphs Combin. 11 (1995) 179–199

    1995

  11. [19]

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

    P. Tur´ an, On an extremal problem in graph theory, (Hung arian), Mat. Fiz. Lapok 48 (1941) 436–452

    1941

  12. [20]

    Zykov, On some properties of linear complexes, Mat

    A.A. Zykov, On some properties of linear complexes, Mat . Sb. 66 (1949) 163–188. A A proof of Theorem 1.1. Lemma A.1. For n1 ≤ n2 ≤ n3 and k ≤ n1, ex(Kn1,n 2,n 3, kK 2) = ( k − 1)(n2 + n3). 19 Proof. First, we prove the lemma for n1 = n2 = n3 = n by induction on k. Clearly, th...

    1949

  13. [21]

    For any u ∈ V (G) and S ⊂ V (G), let d(u, S ) be the number of neighbors of u in S

    − 3 = 4 n − 2k + 4. For any u ∈ V (G) and S ⊂ V (G), let d(u, S ) be the number of neighbors of u in S. Then, it follows that d(x1, V (G′′)) + d(y1, V (G′′)) + d(z1, V (G′′)) ≥ 4n − 2k + 4. Since ( Y ∪ Z) \ (∪M ′) \ T0 has at most 2( n − 1) − (k − 3) = 2 n − k + 1 vertices, we...

Pith tools

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