Pith. sign in

REVIEW 17 references

Rainbow Tur\'an problems for a matching and any other graph

T0 review · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read The paper determines extremal edge counts (minimum, sum, product) for rainbow graph collections avoiding both a fixed graph F and a matching of size s+1.

arxiv 2505.14386 v1 pith:Q5EUZGNJ submitted 2025-05-20 math.CO

Dániel Gerbner , Shujing Miao This is my paper · ORCID
classification math.CO
keywords rainbowfreegraphcollectiongraphsldotsmembercalled
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

Imagine you have t graphs on the same set of n points, and each graph is a different color. A rainbow subgraph is one where you pick edges from different colors, never using the same color twice. You want to pack as many edges as possible while making sure no rainbow copy of F appears and no rainbow matching of size s+1 appears. Because there are several ways to count many edges, the paper studies three: the smallest color's edge count, the total edge count, and the product of the edge counts.

The main results are clean. For the smallest edge count, the paper shows that in most cases the extremal construction is a complete bipartite graph between a small set of s vertices and the rest, with an optimal rainbow structure on the small set. For the total edge count, forbidding a matching costs at most a linear number of edges compared to forbidding only F. For the product, the paper gives the order of magnitude for every possible F, with intricate case splits when F is a star or a star plus isolated edges.

The proofs rely on strong colors: colors that can extend any rainbow matching of size at most s. If there are too many strong colors, you immediately get a forbidden rainbow matching. The paper shows how to control the number of strong colors and how to concentrate edges near a small set of vertices. It also uses the Erdős-Sós conjecture for balanced trees in one of the theorems, making that part conditional.

Extended reading notes

Core claim

The paper claims to determine, for every graph F and every s, the rainbow Turán functions ext(n,{F,M_{s+1}}), ex^Σ_t(n,{F,M_{s+1}}), and ex^Π_t(n,{F,M_{s+1}}) (exactly or asymptotically) under the conditions t ≥ max{|E(F)|,s+1}. In particular, Theorem 1.3 states the order of magnitude of the product for all F, and Theorem 1.1 gives exact values for ext in four cases. If correct, this settles the rainbow extremal problem for the family {F,M_{s+1}} for all graphs F.

Load-bearing premise

The proof of Theorem 1.1(i)-(ii) relies on Lemma 2.3(ii), which asserts that a color with at least s(n-s) edges and fewer than s vertices of degree ≥ n/(2s) is strong. The proof claims 'there are at least n edges inside V', but the preceding inequalities only imply n - O(s^2) such edges, and the extension argument needs a positive margin over edges incident to the matching to be extended. If this lemma is false, the main minimum-edge formulas for non-bipartite and bipartite F could fail.

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.

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

No numbers are fitted to data; the paper is a pure mathematical derivation. Variables s, t, n, F are inputs, not fitted parameters. The paper introduces no new postulated objects: F[p] and F(F) are families borrowed from [11]. All constructions use standard graphs (stars, cliques, complete bipartite graphs).

assumptions (6)
  • standard math Hall's marriage theorem
    Used in Lemma 2.2, Proposition 2.6, and Theorem 1.1(iii) to construct rainbow matchings and analyze auxiliary bipartite graphs.
  • standard math Meshulam's theorem on rainbow matchings
    Cited to [3]; used in Theorem 1.1(i) to conclude that the other at least s colors contain a rainbow M_s.
  • standard math Chvátal-Hanson theorem: ex(n,{S_q,M_{2s+1}}) is bounded by a constant depending on s and q
    Used in Theorem 1.3(iii) to show that a non-strong color with many edges contains a large star S_q.
  • standard math Erdős-Gallai theorem on the extremal number for matchings
    Applied implicitly to bound ex(n,M_{s+1}) = s(n-s)+binom(s,2) for large n in Theorem 1.2(i) and in lower bound constructions.
  • standard math Kővári-Sós-Turán theorem
    Used in Proposition 4.1 to show that F-free graphs have o(n^2) edges for bipartite F, enabling the linear error term.
  • domain assumption Erdős-Sós conjecture for balanced trees
    Explicitly assumed in Theorem 1.1(iv) to bound ex(|U'|,F) ≤ (p-1)|U'|; the theorem is conditional on this conjecture.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Rainbow Tur\'an problems for a matching and any other graph." pith.science (2026). https://pith.science/paper/Q5EUZGNJ

@misc{pith2026250514386,
  author       = {Pith},
  title        = {Pith review of: Rainbow Tur\'an problems for a matching and any other graph},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Q5EUZGNJ}},
  note         = {Machine review of arXiv:2505.14386}
}
abstract

For a family of graphs $\cF$, a graph is called $\cF$-free if it does not contain any member of $\cF$ as a subgraph. Given a collection of graphs $(G_1,\ldots,G_t)$ on the same vertex set $V$ of size $n$, a rainbow graph on $V$ is obtained by taking at most one edge from each $G_i$. We say that a collection is rainbow $\cF$-free if it contains no rainbow copy of any member of $\cF$. In this paper, we study the maximum values of $min_{i\in [t]}|E(G_i)|$, $\sum_{i=1}^{t}|E(G_i)|$ and $\prod_{i=1}^{t}|E(G_i)|$ among rainbow $\{F,M_{s+1}\}$-free collections $(G_1,\ldots,G_t)$ on $n$ vertices.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 15 canonical work pages

  1. [1]

    Aharoni, E

    R. Aharoni, E. Berger, M. Chudnovsky, D. Howard, and P. Seym our, Large rainbow matchings in general graphs, European J. Combin. 79 (2019), 222-227

    work page 2019

  2. [2]

    Aharoni, M

    R. Aharoni, M. DeVos, S. Gonz´ alez Hermosillo de la Maza, A. Montejano, and R. ˇS´ amal, A rainbow version of Mantel’s theorem, Adv. Comb. (2020), no. 2, 12 pp

    work page 2020

  3. [3]

    Aharoni, and D

    R. Aharoni, and D. Howard, Size conditions for the existence of r ainbow matchings, (2011), preprint

    work page 2011

  4. [4]

    Alon, and P

    N. Alon, and P. Frankl, Tur´ an graphs with bounded matching number, J. Comb. Theory Series B. 165 (2024), 223–229

    work page 2024

  5. [5]

    Chv´ atal, and D

    V. Chv´ atal, and D. Hanson, Degrees and matchings, J. Comb. Theory Series B. 20 (1976), no. 2, 128–138

    work page 1976

  6. [6]

    Erd˝ os, Extremal problems in graph theory, In Theory of graphs and its applications, Proc

    P. Erd˝ os, Extremal problems in graph theory, In Theory of graphs and its applications, Proc. Sympos. Smolenice . (1964), 29–36. 15

    work page 1964

  7. [7]

    Erd˝ os, and T

    P. Erd˝ os, and T. Gallai, On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar. 10 (1959), 337–356

    work page 1959

  8. [8]

    Falgas-Ravry, K

    V. Falgas-Ravry, K. Markstr¨ om, and E. R¨ aty, Rainbow variations on a theme by Mantel: extremal problems for Gallai colouring templates, Combinatorica. 44 (2024), no. 5, 977- 1010

    work page 2024

Show all 17 references
  1. [9]

    Frankl, Graphs without rainbow triangles, arXiv preprint, arX iv:2203.07768

    P. Frankl, Graphs without rainbow triangles, arXiv preprint, arX iv:2203.07768

    arXiv

  2. [10]

    F¨ uredi, and M

    Z. F¨ uredi, and M. Simonovits, The history of degenerate (bipa rtite) extremal graph problems. In Erd˝ os centennial (pp. 169-264). Berlin, Heidelberg: Sp ringer Berlin Hei- delberg. (2013)

    2013

  3. [11]

    Gerbner, On Tur´ an problems with bounded matching number , J

    D. Gerbner, On Tur´ an problems with bounded matching number , J. Graph Theory . (2023), 1–7

    2023

  4. [12]

    Z. He, P. Frankl, E. Gy˝ ori, Z. Lv, N. Salia, C. Tompkins, K. Varga, and X. Zhu, Extremal results for graphs avoiding a rainbow subgraph, Electron. J. Combin. 31 (2024), no. 1, Paper No. 1.28

    2024

  5. [13]

    Keevash, D

    P. Keevash, D. Mubayi, B. Sudakov, and J. Verstra¨ ete, Rainbow Tur´ an problems,Com- bin. Probab. Comput. 16 (2007), no. 1, 109–126

    2007

  6. [14]

    Keevash, M

    P. Keevash, M. Saks, B. Sudakov, and J. Verstra¨ ete, Multic olour Tur´ an problems,Adv. in Appl. Math. 33(2004), no. 2, 238–262

    2004

  7. [15]

    K˝ ov´ ari, V

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

    1954

  8. [16]

    W. Sun, G. Wang, and L. Wei, Transversal structures in graph systems: A survey, arXiv preprint, arXiv:2412.01121

    arXiv

  9. [17]

    Tur´ an, Egy gr´ afelm´ eleti sz´ els˝ o´ ert´ ekfeladatr´ ol,Mat

    P. Tur´ an, Egy gr´ afelm´ eleti sz´ els˝ o´ ert´ ekfeladatr´ ol,Mat. Fiz. Lapok . 48 (1941), 436–452. 16

    1941

Pith tools

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