On the maximum size of 2-weakly compatible split systems

Pei Wu; Stefan Gr\"unewald

REVIEW 1 major objections 3 minor 15 references

On the maximum size of 2-weakly compatible split systems

T0 review · 1 major / 3 minor · reviewed 2026-08-28 · deepseek-v4-flash

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

Pith's one-line read The maximum size of a 2-weakly compatible split system on $n$ taxa is $O(n^{5/2})$, improving the previous $O(n^4)$ bound.

desk verdict Real improvement to O(n^{5/2}) for 2-weakly compatible split systems via a clever digraph representation, but the proof's key auxiliary claim skips a case that needs to be written out. read the letter →

arxiv 2608.23275 v1 pith:EBRXCDWW submitted 2026-08-24 math.CO q-bio.PE

Pei Wu , Stefan Grünewald This is my paper · ORCID

classification math.COq-bio.PE MSC 05C3505D0505C20

keywords 2-weaklycompatiblesplitsystemsphylogeneticnetworksTurán-typeproblemforbiddenconfigurationsdirectedgraphrepresentationdischargingmethodextremalcombinatoricsquartetweights

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

Phylogenetic trees are encoded as split systems, collections of bipartitions of the taxon set, and 2-weak compatibility is the condition that lets quartet weights be assembled into a phylogenetic network. Earlier work bounded any such system by $3\binom{n}{4}+\binom{n}{2}=O(n^4)$; this paper proves the substantially smaller bound $O(n^{5/2})$, while the best known lower bound is only quadratic. The result matters because it caps the number of splits a quartet-based network reconstruction method must consider, tightening the search space from quartic to five-halves order.

What carries the argument

The load-bearing object is the edge-labelled directed graph $G_r(S)$ that represents a split system $S$ relative to a fixed root $r$: each split is written as the part $a_r(s)$ not containing $r$, and a directed edge from $A$ to $A\cup\{x\}$ labelled $x$ is drawn exactly when those two parts come from splits of $S$. Edges labelled $x$ are precisely the $x$-pairs of $S$, so the edge count aggregates all pair-counting information. The proof combines this representation with a discharging argument. Vertices start with charge $C_0(A)=5-d(A)$; two discharging rules move charge from low-degree vertices to 6-vertices and to their partners (with a hard 6-vertex defined as a degree-6 vertex whose six neighbours split into three deletions $A-a_i$ and three additions $A+b_i$, with the swapped vertices $A-a_i+b_i$ present). The lemmas show every vertex whose split has size between 5 and $n-5$ ends with nonnegative charge. The only negative charge comes from the $O(n^2)$ small and large splits, whose numbers are bounded via auxiliary graphs: at most three 3-sets and at most seven 4-sets can contain any fixed taxon pair, giving the $cn^2$ error term. That bound $\#E\le\frac{5}{2}\#V+cn^2$ is exactly what the recurrence in Theorem 3 consumes.

What would settle it

Complete the omitted 'isolated edge' subcase in the proof of the seven-edge claim by exhibiting the forbidden four edges $e_1,\dots,e_4$ and four incident vertices $y_1,\dots,y_4$ with $y_i$ incident to $e_j$ exactly when $i=j$. A direct computational search for a 2-weakly compatible split system on six or seven taxa whose auxiliary graph $G_{\{x_1,x_2\}}$ has eight edges would also settle it: finding such a system falsifies the claimed quadratic error term, while confirming none exists supports the theorem.

Watch

Extended reading notes

Core claim

The central result, Theorem 1, is that for $|X|=n$ the maximum size of a 2-weakly compatible split system on $X$ is $O(n^{5/2})$. The proof establishes a stronger structural statement, Theorem 2: any directed graph $G=(V,E)$ representing such a split system satisfies $\#E\le \frac{5}{2}\#V+cn^2$ for a constant $c$ (the paper gives $c=25/24$). This edge bound is hereditary, holding for every restriction $S|_Y$ with $|Y|\ge 6$. Theorem 3 then converts the edge bound into a size bound through a recurrence: each gain of one taxon forces at least one new $x$-pair per vertex, and iterating the resulting inequality replaces the old quartic bound by $O(n^k)$ whenever the edge bound has the form $k\#V+O(n^\ell)$ with $\ell<k$. With $k=\frac{5}{2}$, the final bound is $O(n^{5/2})$.

Load-bearing premise

The argument's load-bearing premise is a small counting step: for any fixed pair of taxa, at most seven four-element split parts can contain that pair. If that step were false, the $O(n^2)$ error term in the edge bound would collapse, and the recurrence would no longer give $O(n^{5/2})$.

Editorial extensions

If this is right

The maximum size of a 2-weakly compatible split system drops from $O(n^4)$ to $O(n^{5/2})$, leaving a gap to the quadratic lower bound of only half an exponent.
Because the edge bound holds for all restrictions $S|_Y$, no subcollection of a 2-weakly compatible system can be dense in the same sense; the bound is hereditary.
The constant $\frac{5}{2}$ in the edge bound is asymptotically optimal: the paper's explicit split system with $n(n-1)$ splits gives an associated digraph of average degree $5-o(1)$, so any further improvement must come from a different inequality, not from lowering the degree constant.
If the authors' Conjecture 1 ($\#E\le 2\#V+cn^2$) holds, the same recurrence would yield $M_2(n)=O(n^2\log n)$ and $M_2(n)=o(n^{2+\varepsilon})$ for every $\varepsilon>0$.
For quartet-based phylogenetic network reconstruction, the number of candidate splits is now bounded by $O(n^{5/2})$ instead of $O(n^4)$, directly shrinking the search space.

Reading between the lines

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

The root-directed graph representation is a general translation device: any split-system class defined by a forbidden configuration induces such digraphs, and an analogous discharging bound, if the small-split counts can be controlled, would give extremal exponents for $k$-weakly compatible systems with $k\ge 2$.
The bottleneck for reducing the exponent below $5/2$ is the auxiliary seven-edge bound on 4-splits, not the degree-5 discharging argument; a sharper or structurally different bound on the numbers of small splits would immediately improve the final exponent through Theorem 3.
The construction showing sharpness of Theorem 2 has only linearly many boundary splits, so it does not rule out a genuine $O(n^2)$ or $O(n^2\log n)$ maximum; the remaining gap is plausibly closed by controlling small splits rather than by modifying the discharging core.
The directed graph could double as an enumeration certificate: checking 2-weak compatibility and counting splits reduces to verifying local degree and small-configuration conditions on a graph of size comparable to the split system, which may give practical speedups in quartet-network software.

Share X Bluesky LinkedIn Reddit HN

Formalized claims in Lean

Claim #1: The central result, Theorem 1, is that for $|X|=n$ the maximum size of a 2-weakly compatible split system on $X$ is $O(n^{5/2})$. The proof establishes a stronger structural statement, Theorem 2: any directed graph $G=(V,E)$ representing such a split system satisfies $\#E\le \frac{5}{2}\#V+cn^2$ for a constant $c$ (the paper gives $c=25/24$). This edge bound is hereditary, holding for every restri

/-- @claim 1 The central result, Theorem 1, is that for $|X|=n$ the maximum size of a 2-weakly compatible split system on $X$ is $O(n^{5/2})$. The proof establishes a stronger structural statement, Theorem 2: any directed graph $G=(V,E)$ representing such a split system satisfies $\#E\le \frac{5}{2}\#V+cn^2$ for a constant $c$ (the paper gives $c=25/24$). This edge bound is hereditary, holding for every restri -/
def central_claim : Prop :=

Signed reviews

No signed human review yet.

Request a human review

A listed scientist reviews the paper for a fee and the review publishes here regardless of verdict. See the reviewers or get listed.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

The punchline: this paper delivers a real improvement, from O(n^4) to O(n^{5/2}), for the maximum size of 2-weakly compatible split systems, using a directed graph representation that is worth knowing even apart from the bound.

What's genuinely new: the representation itself—vertices are the root-avoiding parts of splits, edges correspond to adding one taxon—and the way the authors turn the Turán-type split-system question into a graph-degree problem. They prove a linear bound on edges, #E ≤ (5/2)#V + O(n^2), then convert that via a clean recurrence (Theorem 3) into the O(n^{5/2}) bound on split count. The previous upper bound was a linear-algebraic 3·C(n,4)+C(n,2), so the improvement is substantial. The discharging argument in Lemma 4 is intricate, but the charge bookkeeping is coherent, and the paper is self-contained. No circularity, no parameter fitting.

The soft spot is the one the stress-test note flags: in Section 3, the proof that each G_{x1,x2} has at most seven edges ends with the isolated-edge case being dismissed as 'yields the same contradiction.' No forbidden configuration is exhibited for that subcase. This step is load-bearing: it gives #A4 ≤ (7/6)C(n,2), which is exactly the O(n^2) error term in Theorem 2. If that case were false, the recurrence would not close at O(n^{5/2}). The case is probably true—with eight edges in a max-degree-3 graph, an isolated edge leaves seven edges, and those must contain either a vertex of degree 3 whose incident edges form a star or enough leaf edges—but 'probably' isn't a proof. A referee should ask for the case to be written out. I don't see this as destroying the result; the rest of the proof is consistent, and the missing case has the flavor of a routine-but-annoying subcase. Still, as written, the proof has a genuine gap at a critical point.

Other observations: the lower bound is only Ω(n^2), and the paper's own conjecture (Conjecture 1, #E ≤ 2#V + O(n^2)) would, via the recurrence, yield O(n^2 log n). So this is an important step, not the end of the story. The discussion of the near-sharpness of the 5/2 coefficient in Theorem 2 is honest and useful.

Who should read it: extremal set theorists and anyone working on split systems or quartet-based phylogenetic methods. It's not a desk-reject; it's exactly the kind of paper that deserves a careful referee. My recommendation: send it out, ask for the isolated-edge case to be expanded and for a bit more detail in the last part of Lemma 4 if the referee needs it. If the missing case confirms, accept.

Referee Report

1 major / 3 minor

Summary. The paper studies the maximum size of a 2-weakly compatible split system on an n-element set, a notion arising in phylogenetic network reconstruction. Previous work gave an upper bound of 3 binom(n,4)+binom(n,2) = O(n^4). The authors introduce a directed graph representation of a split system, prove via a discharging argument that every such graph has at most (5/2)|V| + c n^2 edges for an explicit constant c, and then use a recurrence on restrictions to derive the main theorem that the maximum size is O(n^{5/2}). The paper also describes a construction showing the coefficient 5/2 in the graph bound is asymptotically sharp and proposes a conjecture that would improve the bound further.

Significance. If the proof is completed, the result is a substantial quantitative improvement over the previous O(n^4) upper bound, bringing it closer to the Omega(n^2) lower bound. The graph representation of split systems appears to be a genuinely useful tool for Turán-type problems in this area. The proof is self-contained, uses no fitted parameters or circular assumptions, and yields explicit constants. The remaining bottleneck is a localized case analysis in the proof that an auxiliary graph has at most seven edges.

major comments (1)

[Section 3, proof of the claim 'G_{x1,x2} has at most seven edges'] The final case, in which the eight-edge subgraph G'_{x1,x2} contains an isolated edge, is dismissed with the sentence 'yields the same contradiction' but no forbidden configuration is exhibited. This is a load-bearing step: the bound #A4 <= (7/6) binom(n,2) depends on it, and that bound supplies the O(n^2) error term in Theorem 2 that is essential for the recurrence in Theorem 3 to produce O(n^{5/2}). Please provide the explicit argument, for example by showing that with an isolated edge the remaining seven edges force either a degree-3 vertex whose incident edges form a star or three edges with leaf endpoints, and that either alternative combined with the isolated edge creates the forbidden four-edge pattern.

minor comments (3)

[Section 3, paragraph after the definition of A3] The assertion that at most three sets in A3 contain any fixed pair {x1,x2} is stated without proof; a sentence explaining that four such 3-sets restrict to the forbidden configuration on six taxa would make this step self-contained.
[Section 3, proof of Lemma 4] There are several typographical slips in the taxon lists, for example 'the taxaa1,a2,a3,b2,b1,r' and 'the taxaa1,a2,a3,b3'; these should be corrected and the intended six-element restrictions written consistently.
[Section 5, construction] The claim that the graph G_2(S) for the displayed split system has average degree 5-o(1) is asserted without a detailed count; a short calculation or reference to the boundary cases would improve verifiability.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the O(n^{5/2}) proof is self-contained and does not reduce to its inputs.

full rationale

The paper's central claim, Theorem 1, is derived from Theorem 3's recurrence applied to the edge bound of Theorem 2. The proof of Theorem 2 is a self-contained discharging argument over the auxiliary digraph G_r(S), with the constants (5/2 for #V and 25/24 n^2 for the error term) obtained by charging arguments inside the paper rather than by fitting parameters. The only cited prior result used in the proof chain is the old O(n^4) upper bound from [15], which is background context; the new bound does not invoke it as a load-bearing step. The lower bound of Omega(n^2) is also independent. The auxiliary claim that each graph G_{x1,x2} has at most seven edges is the key numerical step, and it is argued from 2-weak compatibility rather than assumed; although the proof text dismisses the isolated-edge subcase with 'yields the same contradiction' without displaying the four forbidden edges, that omission is a gap in justification, not circular reasoning. No fitted quantity is renamed as a prediction, no definition is made in terms of the target bound, and no self-citation chain is used to force the conclusion. The paper is self-contained against the external benchmark: it improves a previously known upper bound using a genuinely new graph representation. Hence the circularity score is 0.

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

The proof uses standard combinatorics and the definition of 2-weak compatibility from [15]; no free parameters are fitted and no new entities are postulated. The graph G_r(S) is constructed from the split system itself, not assumed.

assumptions (3)

domain assumption The class of 2-weakly compatible split systems is closed under taking subsystems and restrictions.
Used in Theorem 3 to apply the graph bound (Theorem 2) to every restriction S|Y. The closure follows from the forbidden-configuration definition in Section 2 but is not separately proved.
domain assumption A split system is 2-weakly compatible if and only if it avoids the four-split configuration {123|456, 124|356, 125|346, 126|345}.
This is the working definition of the paper, imported from the phylogenetic literature [15]; the whole proof is built on this forbidden configuration.
standard math Standard results of finite combinatorics such as the handshaking lemma, Hall-type matching arguments, and the Sauer-Shelah theorem may be used without proof.
These background facts are invoked in the introduction and in the auxiliary graph arguments (Section 3).

how reviews work

0 comments

Cite this review

Pith. "Pith review of On the maximum size of 2-weakly compatible split systems." pith.science (2026). https://pith.science/paper/EBRXCDWW

@misc{pith2026260823275,
  author       = {Pith},
  title        = {Pith review of: On the maximum size of 2-weakly compatible split systems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EBRXCDWW}},
  note         = {Machine review of arXiv:2608.23275}
}

abstract

We consider a Tur\'an-type problem arising in phylogenetics: determining the maximum size of a 2-weakly compatible split system. This compatibility condition arises in the reconstruction of phylogenetic networks from quartet weights. It was previously shown that a 2-weakly compatible split system has size at most \[ 3\binom{n}{4}+\binom{n}{2}. \] We prove that the maximum size is $O(n^{5/2})$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 14 canonical work pages

[1]

R. P. Anstee and A. Sali. A survey of forbidden configuration results.Electronic Journal of Combinatorics, 20:Dynamic Survey 20, 2013. doi:10.37236/2379

work page doi:10.37236/2379 2013
[2]

Bandelt and A

H.-J. Bandelt and A. W. M. Dress. Split decomposition: A new and useful approach to phylogenetic analysis of distance data.Molecular Phylogenetics and Evolution, 1(3):242–252, 1992

work page 1992
[3]

P. Buneman. The recovery of trees from measures of dissimilarity. In F. R. Hodson, D. G. Kendall, and P. Tautu, editors,Mathematics in the Archaeological and Historical Sciences, pages 387–395. Edinburgh University Press, 1971

work page 1971
[4]

A. W. M. Dress, M. Klucznik, J. H. Koolen, and V. Moulton. A note on extremal combinatorics of cyclic split systems.Séminaire Lotharingien de Combinatoire, 47:Article B47b, 17 pp., 2001/02

work page 2001
[5]

A. W. M. Dress, J. H. Koolen, and V. Moulton.4n− 10.Annals of Combinatorics, 8(4):463–471, 2005

work page 2005
[6]

T. Fleiner. The size of 3-cross-free families.Combinatorica, 21(3):445–448, 2001

work page 2001
[7]

Grünewald, J

S. Grünewald, J. H. Koolen, V. Moulton, and T. Wu. The size of 3-compatible, weakly compatible split systems.Journal of Applied Mathematics and Computing, 40(1–2):249–259, 2012. 11

work page 2012
[8]

Kupavskii, J

A. Kupavskii, J. Pach, and I. Tomon. On the size ofk-cross-free families.Combinatorica, 39(1):153–164, 2019. doi:10.1007/s00493-017-3792-8

work page doi:10.1007/s00493-017-3792-8 2019

Show all 15 references

[9]

P. A. Pevzner. Non-3-crossing families and multicommodity flows.American Mathematical Society Translations, Series 2, 158:201–206, 1994

1994
[10]

N. Sauer. On the density of families of sets.Journal of Combinatorial Theory, Series A, 13(1):145–147, 1972. doi:10.1016/0097-3165(72)90019-2

1972 doi
[11]

S. Shelah. A combinatorial problem; stability and order for models and theories in infinitary languages.Pacific Journal of Mathematics, 41(1):247–261, 1972

1972
[12]

A. Suk. A note onKk,k-cross-free families.Electronic Journal of Combinatorics, 15(1):Research Paper 39, 6 pp., 2008

2008
[13]

P. Turán. On an extremal problem in graph theory.Matematikai ès Fizikai Lapok, 48:436–452, 1941

1941
[14]

V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities.Theory of Probability and Its Applications, 16(2):264–280, 1971

1971
[15]

J. Yang, S. Grünewald, and X. Wan. Quartet-Net: A quartet-based method to reconstruct phylogenetic networks.Molecular Biology and Evolution, 30(5):1206–1217, 2013. 12

2013

Pith tools

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

[1] [1]

R. P. Anstee and A. Sali. A survey of forbidden configuration results.Electronic Journal of Combinatorics, 20:Dynamic Survey 20, 2013. doi:10.37236/2379

work page doi:10.37236/2379 2013

[2] [2]

Bandelt and A

H.-J. Bandelt and A. W. M. Dress. Split decomposition: A new and useful approach to phylogenetic analysis of distance data.Molecular Phylogenetics and Evolution, 1(3):242–252, 1992

work page 1992

[3] [3]

P. Buneman. The recovery of trees from measures of dissimilarity. In F. R. Hodson, D. G. Kendall, and P. Tautu, editors,Mathematics in the Archaeological and Historical Sciences, pages 387–395. Edinburgh University Press, 1971

work page 1971

[4] [4]

A. W. M. Dress, M. Klucznik, J. H. Koolen, and V. Moulton. A note on extremal combinatorics of cyclic split systems.Séminaire Lotharingien de Combinatoire, 47:Article B47b, 17 pp., 2001/02

work page 2001

[5] [5]

A. W. M. Dress, J. H. Koolen, and V. Moulton.4n− 10.Annals of Combinatorics, 8(4):463–471, 2005

work page 2005

[6] [6]

T. Fleiner. The size of 3-cross-free families.Combinatorica, 21(3):445–448, 2001

work page 2001

[7] [7]

Grünewald, J

S. Grünewald, J. H. Koolen, V. Moulton, and T. Wu. The size of 3-compatible, weakly compatible split systems.Journal of Applied Mathematics and Computing, 40(1–2):249–259, 2012. 11

work page 2012

[8] [8]

Kupavskii, J

A. Kupavskii, J. Pach, and I. Tomon. On the size ofk-cross-free families.Combinatorica, 39(1):153–164, 2019. doi:10.1007/s00493-017-3792-8

work page doi:10.1007/s00493-017-3792-8 2019