Pith. sign in

REVIEW 1 major objections 4 minor 17 references

A note on matchings and co-matchings in bipartite graphs

T0 review · 1 major / 4 minor · reviewed 2026-08-04 · deepseek-v4-flash

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

Pith's one-line read This paper quantifies how large a guaranteed complete-or-empty induced subgraph must be in a bipartite graph that forbids induced matchings and co-matchings, giving explicit lower and upper bounds in terms of the forbidden sizes.

arxiv 2607.23928 v2 pith:XQKLKYGO submitted 2026-07-27 math.CO

Sida Li This is my paper · ORCID
classification math.CO MSC 05C3505C6505C7005D40
keywords bipartitegraphsinducedmatchingsco-matchingspurepairsstronginduced-subgraphpropertylog-rankconjecturehypergraphRamseytheoryslicerank
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 author studies bipartite graphs that contain neither an induced matching of size k nor an induced co-matching of size ℓ, and asks how large a pure pair—a complete or empty induced subgraph—must be on both sides. The main theorem provides a lower bound on this pure-pair proportion that decays like an inverse binomial coefficient in k and ℓ; in the diagonal case this reads as at least (64√π/13 + o(1))√t/4^t. Complementing this, the paper constructs graphs that avoid matchings and co-matchings of size t while having no pure pairs beyond about √t/2^{t/2}, so the guaranteed proportion is pinned between two exponential bases. Off-diagonal results determine p(2,ℓ)=1/2 exactly and place p(3,ℓ) between roughly 1/(3ℓ) and ℓ^{-1/5}. The same questions for k-partite k-uniform hypergraphs behave very differently, with O(n^2)-edge slice-rank-one examples avoiding linear pure boxes for k≥3.

What carries the argument

The central object is the pure pair (X,Y): an induced subgraph that is either complete or empty and whose two parts have specified sizes relative to |A| and |B|. The lower bound is carried by a recurrence s_{2,ℓ}=s_{k,2}=2 and s_{k,ℓ} = (s_{k−1,ℓ}+s_{k,ℓ−1}+2 + sqrt((s_{k−1,ℓ}+s_{k,ℓ−1})^2+4))/2, whose solution is approximately (13/4)binom(k+ℓ−4,k−2). The induction partitions vertices into high- and low-degree sets and shows that any pure pair smaller than the claimed size forces either an induced matching, an induced co-matching, or contradiction by edge double-counting. For the upper bounds, the paper uses a uniform random graph at density 1/2 with equitable blow-ups, and for the k=3 bound

What would settle it

For the random graph G(L,L,1/2) with L=(1−2log t/t)√(2/e)√t·2^{t/2}, compute the expected number of induced matchings of size t; a direct estimate gives Θ(e^t/√t), meaning the local lemma cannot certify a survivor. If a second-moment calculation confirms that this expected count is typically realized, the claimed upper-bound construction at density 1/2 fails, and any recovery would require a different L or non-uniform edge probabilities.

Watch

Extended reading notes

Core claim

The paper's central claim is that forbidding induced matchings and co-matchings in bipartite graphs does not destroy the strong induced-subgraph property; rather, the guaranteed pure-pair proportion is controlled by a two-parameter recurrence whose closed form is a binomial coefficient. Concretely, a graph with no matching of size k and no co-matching of size ℓ must contain a pure pair (X,Y) with |X| ≥ 4/[13·binom(k+ℓ−4,k−2)−5] · |A| and |Y| likewise. The author also claims an upper-bound construction showing that, in the diagonal case, one cannot force pure pairs much larger than about √t/2^{t/2}, so p(t) sits between roughly √t/4^t and √t/2^{t/2}. In the off-diagonal regime, k=2 gives the

Load-bearing premise

The upper-bound construction depends on a probabilistic local lemma estimate that the paper asserts vanishes; a direct recalculation of the relevant product gives Θ(t^3), not zero, so the claimed existence of a graph with no large matchings and no large pure pairs at the stated parameters is not actually established.

Editorial extensions

If this is right

  • If a bipartite graph avoids induced matchings and co-matchings of size t, it must contain a complete or empty induced subgraph with parts of size at least (64√π/13 + o(1))√t/4^t of the original parts, giving explicit quantitative strong induced-subgraph behavior for every fixed t.
  • The upper construction shows that no guaranteed proportion above roughly √t/2^{t/2} is possible, so the true value of p(t) is determined up to a subexponential factor with exponential base between 4 and 2^{1/2}.
  • For k=2 the exact answer is p(2,ℓ)=1/2 for all ℓ, meaning the smallest forbidden matching already yields an optimal constant.
  • For k=3 the guaranteed pure-pair proportion is polynomial in ℓ, lying between about 1/(3ℓ) and ℓ^{-1/5}; closing this exponent gap is a concrete open problem suggested by the paper.
  • In k-partite k-uniform hypergraphs with k≥3, no analogue of the strong property survives: there exist O(n^2)-edge hypergraphs with slice-rank-one adjacency tensors that avoid linear-size pure boxes while forbidding matchings and co-matchings of size 2.

Reading between the lines

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

  • Editorial inference: if the binomial-coefficient lower bound is close to tight, then the log-rank-type obstruction supplied by permutation submatrices has a quantitative limit around 4^{-t}; the gap to the 2^{-t/2} upper bound suggests a natural target—improving the upper construction would directly sharpen the best monochromatic-submatrix guarantee for functions whose only rank obstructions are m
  • Editorial inference: the hypergraph construction with slice-rank-one adjacency tensor indicates that slice rank cannot detect matching-like forbidden patterns for k≥3, so a tensor-based log-rank conjecture would require a different notion of rank; testing whether the O(n^2) edge threshold is sharp for other ranks is a natural next step.
  • Editorial inference: the k=3 lower and upper bounds differ by a factor of ℓ^{4/5}; a promising route would be replacing the finite-geometry incidence graph with a random algebraic pseudorandom graph that has no K_{2,2} but weaker spectral expansion, to see whether the exponent 1/5 can be pushed toward 1.
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

1 major / 4 minor

Summary. The paper studies quantitative strong Erdős–Hajnal bounds for bipartite graphs avoiding induced matchings and co-matchings. It defines p(k,ℓ) and proves a lower bound via a recurrence (Theorem 1.1), giving a diagonal lower bound of order √t/4^t (Corollary 1.2). It claims a matching upper bound of order √t/2^{t/2} using a random construction and the Lovász Local Lemma (Theorem 1.3). Off-diagonal results include a lower bound for k=3 (Corollary 1.4) and an algebraic upper bound from generalized quadrangles (Theorem 1.5). The final sections extend some results to hypergraphs and slice rank (Theorems 1.6–1.8).

Significance. If the lower bound stands, the paper provides a new and nontrivial quantitative Erdős–Hajnal statement for matchings and co-matchings; the recurrence proof is elementary and appears correct. The generalized-quadrangle construction for k=3 is elegant and gives a polynomial upper bound with exponent 1/5. The hypergraph results, including the O(n^2)-edge threshold, are interesting. The paper does not ship machine-checked proofs or code, but the derivations are transparent enough to verify by hand. However, the advertised upper bound in Theorem 1.3 is not supported by the proof as written.

major comments (1)
  1. [§2.1, proof of Theorem 1.3] The LLL estimate is incorrect. With L=(1-2log t/t)√(2/e)√t 2^{t/2}, the correct asymptotic for the LLL expression is eP(A)(Δ+1)=Θ(t^{5/2}), not o(1). The displayed inequality eP(A)(Δ+1)≤3t^4(e L^{2-2/t}/t^{2t})^t appears to lose the 2^{t^2} factor in the denominator; substituting L gives e L^2/(t 2^t)=2(1-o(1)), so the t-th power is exponentially large. In fact the expected number of events is C(L,t)^2 P(A)=Θ(2^t/√t). Therefore the Lovász Local Lemma cannot be applied, and Theorem 1.3 — together with the upper bound in Corollary 2.1 — is not established.
minor comments (4)
  1. [§2.1, proof of Theorem 1.3] The independence explanation contains a typo: 'no pair (x,y) lies in both X×Y and Y×Y′' should read 'X×Y and X′×Y′'. Also, independence holds when either |X∩X′|=0 or |Y∩Y′|=0, not only the former.
  2. [§4, proof of Theorem 1.7] The claim that 'the adjacency tensors of the matching and co-matching of size two have slice rank two' is inaccurate for k≥3: the co-matching tensor is the all-ones tensor minus the matching tensor, and its slice rank is 3, not 2. The proof only needs slice rank >1, so Theorem 1.7 is unaffected, but the statement should be corrected.
  3. [§2, base case of Theorem 1.1] The conclusion that neighborhoods are nested ('either N(x)⊆N(x′) or N(x′)⊆N(x)') follows from the absence of an induced 2-matching; the proof would be clearer with a one-sentence justification.
  4. [§2.1, blow-up step] The sentence 'for all X⊆A,Y⊆B with |X| ≥ ⌈m/L⌉ t and |Y| ≥ ⌈n/L⌉ t, we have that (X,Y) cannot be a pure pair' is terse. It would help to state explicitly that such sets must intersect at least t distinct blow-up classes on each side, so a pure pair would descend to a t-by-t pure pair in G′.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: all derivations are first-principles or rest on external standard lemmas; the main risk is an apparent LLL estimate error in Theorem 1.3, which is a correctness gap, not circularity.

full rationale

The paper contains no circular derivation. Theorem 1.1 is proved by induction with a recurrence derived from first principles: degree-threshold partitions, double-counting, and the inductive hypothesis applied to subgraphs. There are no fitted parameters renamed as predictions; p(k,ℓ) is defined as an extremal quantity and the proof establishes a lower bound by an explicit construction-free argument. The upper-bound constructions in Theorems 1.3 and 1.5 use random graphs and generalized quadrangles, with standard external tools (Lovász Local Lemma, expander mixing lemma, Payne–Thas) that do not encode the theorem's conclusions. The hypergraph results (Theorems 1.7, 1.8, 4.2) are self-contained probabilistic, alteration, and linear-algebra arguments. There are no self-citations by the author; cited works are external prior results used as lemmas. The main weakness is a correctness risk, not circularity: in the proof of Theorem 1.3, the Lovász Local Lemma verification appears to be wrong, since eP(A)(Δ+1) is polynomial in t, not o(1), for the chosen L. That would invalidate the claimed upper bound p(t) ≤ (√(e/2)+o(1))√t/2^{t/2}, but it is an error in an estimate, not a self-referential or fitted-input reduction.

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

The paper introduces no fitted parameters or new postulated objects. It relies on standard cited theorems, with the LLL application being the only load-bearing assumption that fails.

assumptions (6)
  • standard math Lovász Local Lemma
    Used in Theorem 1.3 to infer existence of a graph avoiding all bad events; the required condition is the fragile step.
  • standard math Stirling approximation and binomial asymptotics
    Used to convert the recurrence to binomial bounds and to diagonal asymptotics.
  • standard math Expander mixing lemma for biregular bipartite graphs
    Used in Lemma 3.3 for the symplectic generalized quadrangle incidence graph.
  • domain assumption Standard facts on symplectic generalized quadrangles W(3,q)
    Quoted from Payne–Thas: parameters, regularity, and singular values of the incidence matrix.
  • domain assumption Monotonicity and slice-rank values for diagonal tensors
    Used in Section 4 to show low slice rank forbids matchings/co-matchings of size 2.
  • standard math Prime number theorem for interpolation
    Used in the proof of Theorem 1.5 to choose q.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A note on matchings and co-matchings in bipartite graphs." pith.science (2026). https://pith.science/paper/XQKLKYGO

@misc{pith2026260723928,
  author       = {Pith},
  title        = {Pith review of: A note on matchings and co-matchings in bipartite graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XQKLKYGO}},
  note         = {Machine review of arXiv:2607.23928}
}
abstract

A class of bipartite graphs is said to have the strong Erd\H{o}s-Hajnal property if there exists $\varepsilon > 0$ such that every graph $((A, B), E)$ in the class contains a complete or empty induced subgraph with parts $X \subseteq A$, $Y \subseteq B$ where $|X| \ge \varepsilon|A|$ and $|Y| \ge \varepsilon|B|$. Scott, Seymour and Spirkl proved that it is enough to forbid a forest and the bipartite complement of a forest. In this paper, we provide quantitative bounds on $\varepsilon$ when we restrict to matchings.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 1 linked inside Pith

  1. [1]

    Crossing patterns of semi-algebraic sets.Journal of Combinatorial Theory, Series A, 111(2):310–326, 2005

    Noga Alon, J´ anos Pach, Rom Pinchasi, Radoˇ s Radoiˇ ci´ c, and Micha Sharir. Crossing patterns of semi-algebraic sets.Journal of Combinatorial Theory, Series A, 111(2):310–326, 2005

    2005

  2. [2]

    Factorization norms and an inverse theorem for MaxCut, 2025

    Igor Balla, Lianna Hambardzumyan, and Istv´ an Tomon. Factorization norms and an inverse theorem for MaxCut, 2025. https://arxiv.org/abs/2506.23989. 14

    arXiv 2025

  3. [3]

    Pure pairs

    Maria Chudnovsky, Alex Scott, Paul Seymour, and Sophie Spirkl. Pure pairs. I. Trees and linear anticomplete pairs.Advances in Mathematics, 375:107396, 2020

    2020

  4. [4]

    Ramsey-type theorems.Discrete Applied Mathematics, 25(1):37–52, 1989

    Paul Erd˝ os and Andr´ as Hajnal. Ramsey-type theorems.Discrete Applied Mathematics, 25(1):37–52, 1989

    1989

  5. [5]

    Springer Berlin Heidelberg, Berlin, Heidelberg, 2008

    Jacob Fox and J´ anos Pach.Erd˝ os-Hajnal-type Results on Intersection Patterns of Geometric Objects, pages 79–103. Springer Berlin Heidelberg, Berlin, Heidelberg, 2008

    2008

  6. [6]

    En route to the log-rank conjecture: New reductions and equivalent formulations

    Dmitry Gavinsky and Shachar Lovett. En route to the log-rank conjecture: New reductions and equivalent formulations. InAutomata, Languages, and Programming, pages 514–524, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg

    2014

  7. [7]

    Deterministic communication vs

    Mika G¨ o¨ os, Toniann Pitassi, and Thomas Watson. Deterministic communication vs. partition number. In2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 1077–1088, 2015

    2015

  8. [8]

    Geometric rank of tensors and subrank of matrix multiplication.Discrete Analysis, 2023

    Swastik Kopparty, Guy Moshkovitz, and Jeroen Zuiddam. Geometric rank of tensors and subrank of matrix multiplication.Discrete Analysis, 2023

    2023

Show all 17 references
  1. [9]

    Communication is bounded by root of rank.J

    Shachar Lovett. Communication is bounded by root of rank.J. ACM, 63(1), February 2016

    2016

  2. [10]

    Lattices, mobius functions and communications complexity

    L´ aszl´ o Lov´ asz and Michael Saks. Lattices, mobius functions and communications complexity. InProceedings of the 29th Annual Symposium on Foundations of Computer Science, SFCS ’88, page 81–90, USA, 1988. IEEE Computer Society

    1988

  3. [11]

    The partition rank of a tensor andk-right corners inF qn.Journal of Combina- torial Theory, Series A, 174:105190, 2020

    Eric Naslund. The partition rank of a tensor andk-right corners inF qn.Journal of Combina- torial Theory, Series A, 174:105190, 2020

    2020

  4. [12]

    On rank vs

    Noam Nisan and Avi Wigderson. On rank vs. communication complexity. InProceedings of the 35rd Annual Symposium on Foundations of Computer Science, pages 831–836, 1994

    1994

  5. [13]

    Payne and Joseph A

    Stanley E. Payne and Joseph A. Thas.Finite Generalized Quadrangles. EMS series of lectures in mathematics. European Mathematical Society, 2009

    2009

  6. [14]

    Pure pairs

    Alex Scott, Paul Seymour, and Sophie Spirkl. Pure pairs. IV. Trees in bipartite graphs.Journal of Combinatorial Theory, Series B, 161:120–146, 2023

    2023

  7. [15]

    Matrix discrepancy and the log-rank conjecture.Math

    Benny Sudakov and Istv´ an Tomon. Matrix discrepancy and the log-rank conjecture.Math. Program., 212(1):567–579, July 2024

    2024

  8. [16]

    A symmetric formulation of the Croot-Lev-Pach-Ellenberg-Gijswijt capset bound,

    Terence Tao. A symmetric formulation of the Croot-Lev-Pach-Ellenberg-Gijswijt capset bound,

  9. [2016]

    https://terrytao.wordpress.com/2016/05/18/a-symmetric-formulation-of-the-croot-lev– pach-ellenberg-gijswijt-capset-bound/. 15

    2016

Pith tools

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