pith. sign in

arxiv: 2604.05491 · v1 · submitted 2026-04-07 · 🧮 math.CO · cs.DM

A counterexample to the conjecture on Biclique Partition number of Split Graphs and related problems

Anand Babu , Ashwin Jacob This is my paper

Pith reviewed 2026-05-10 19:53 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords split graphsbiclique partition numbercounterexampleco-chordal graphsGraham-Pollak theoremsingular tournamentsbinary rank
0
0 comments X

The pith

A specific split graph provides a counterexample showing that bp(G) need not equal mc(G^c) - 1.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper tests whether the biclique partition number of any split graph or co-chordal graph equals one less than the number of maximal cliques in its complement, an equality that would extend the Graham-Pollak theorem. It answers this negatively by exhibiting one split graph where the two quantities differ and then building an infinite family of similar graphs. The work also records structural facts about biclique partitions in split graphs and settles a separate open question on the existence of singular n-tournaments with binary rank n.

Core claim

The biclique partition number bp(G) of a constructed split graph G is not equal to mc(G^c) - 1, disproving the conjectured equality for split graphs.

What carries the argument

A split graph G whose edge set requires a biclique partition whose size differs from the number of maximal cliques in the complement minus one.

If this is right

  • The conjectured equality fails for split graphs and therefore does not extend the Graham-Pollak theorem to that class.
  • An infinite family of split graphs exists in which bp(G) differs from mc(G^c) - 1.
  • Biclique partitions of split graphs obey additional structural restrictions beyond the refuted equality.
  • Singular n-tournaments with binary rank exactly n do exist.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Generalizations of Graham-Pollak to larger graph families will likely require stricter conditions than co-chordality or split structure.
  • The same construction technique may produce counterexamples in other hereditary graph classes.
  • The newly settled tournament existence result may link biclique partition questions to rank problems over binary matrices.

Load-bearing premise

The presented graph is a split graph and the computed values of bp(G) and mc(G^c) are accurate enough to establish a genuine difference.

What would settle it

An explicit biclique partition of the given split graph whose size equals mc(G^c) - 1, or a proof that no such differing graph exists.

read the original abstract

The biclique partition number of a graph \(G\), denoted \( \operatorname{bp}(G)\), is the minimum number of biclique subgraphs needed to partition the edge set of $G$. Lyu and Hicks \cite{lyu2023finding} posed the open problem of whether \( \operatorname{bp}(G) = \operatorname{mc}(G^c) - 1 \) holds for every co-chordal graph or split graph, where \( \operatorname{mc}(G^c) \) denotes the number of maximal cliques in the complement of \( G \). Such a result would extend the celebrated Graham--Pollak theorem to a more general class of graphs. In this note, we answer this problem in the negative by providing a counterexample using a split graph. We also construct an infinite family of counterexamples and prove some structural properties of biclique partitions of split graphs. Finally, we solve an open problem posed by Siewert \cite{siewert2000biclique} on the existence of singular \(n\)-tournaments with binary rank \(n\).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper claims to negatively resolve the conjecture of Lyu and Hicks that bp(G) = mc(G^c) - 1 for every split graph (or co-chordal graph) G by exhibiting an explicit split-graph counterexample, constructing an infinite family of counterexamples, proving structural properties of biclique partitions in split graphs, and resolving Siewert's open question on the existence of singular n-tournaments with binary rank n.

Significance. If the explicit counterexample and its verification hold, the result is significant as a direct disproof of a natural extension of the Graham-Pollak theorem to split graphs. The infinite family and the resolution of the tournament problem provide additional value; the constructive approach makes the negative claim potentially falsifiable by direct checking of the finite graph.

major comments (1)
  1. [counterexample construction and verification] The central negative claim rests on the accuracy of the values bp(G) and mc(G^c) for the presented split graph (and the infinite family). The manuscript must include an explicit edge-by-edge verification that the listed bicliques form a partition of E(G) with no overlaps or omissions, together with an exhaustive enumeration of the maximal cliques of G^c showing that their number is strictly larger than bp(G) + 1. Without these finite combinatorial checks the inequality cannot be confirmed.
minor comments (2)
  1. [Section on the explicit counterexample] Clarify the precise split partition (clique side and independent-set side) used for the counterexample graph to make the absence of induced 2K2/C4/C5 immediate.
  2. [counterexample section] Add a small table or diagram listing the bicliques and the maximal cliques of the complement for the base counterexample to aid verification.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for highlighting the need for explicit verification of the central counterexample. We address this point below and will strengthen the manuscript accordingly.

read point-by-point responses

  1. Referee: The central negative claim rests on the accuracy of the values bp(G) and mc(G^c) for the presented split graph (and the infinite family). The manuscript must include an explicit edge-by-edge verification that the listed bicliques form a partition of E(G) with no overlaps or omissions, together with an exhaustive enumeration of the maximal cliques of G^c showing that their number is strictly larger than bp(G) + 1. Without these finite combinatorial checks the inequality cannot be confirmed.

    Authors: We agree that the manuscript would benefit from more explicit, self-contained verification. In the revised version we will add a dedicated appendix containing: (i) an edge-by-edge listing for the base split-graph counterexample that confirms the proposed collection of bicliques partitions E(G) with neither overlaps nor omissions, and (ii) an exhaustive enumeration of all maximal cliques in G^c together with a direct count showing mc(G^c) > bp(G) + 1. For the infinite family we will supply a uniform combinatorial argument (based on the structural properties already proved in the paper) that verifies the same strict inequality holds for every member of the family, thereby avoiding case-by-case enumeration while still making the claim fully checkable. revision: yes

Circularity Check

0 steps flagged

No circularity: direct constructive counterexample

full rationale

The paper resolves the conjecture negatively via an explicit finite split graph G (plus an infinite family) whose biclique partition number bp(G) and complement maximal-clique count mc(G^c) are computed by direct enumeration. The central claim is the inequality bp(G) < mc(G^c)-1, established by exhibiting a concrete edge partition into bicliques and listing all maximal cliques of G^c; these are finite, verifiable combinatorial facts with no equations, fitted parameters, or self-referential definitions. Citations to Lyu-Hicks and Siewert are external and non-overlapping; no uniqueness theorem or ansatz is imported from the authors' prior work. The derivation chain is therefore self-contained and non-circular.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard combinatorial definitions of split graphs, bicliques, and maximal cliques; no free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (2)
  • standard math A split graph is a graph whose vertices can be partitioned into a clique and an independent set.
    Used to certify that the counterexample belongs to the class under study.
  • standard math The biclique partition number bp(G) is the smallest number of bicliques whose edge sets partition the edge set of G.
    Core definition for the quantity being compared to mc(G^c) - 1.

pith-pipeline@v0.9.0 · 5491 in / 1432 out tokens · 66034 ms · 2026-05-10T19:53:45.681357+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages · 1 internal anchor

  1. [1]

    N. Alon. Decomposition of the completer-graph into completer-partite r-graphs.Graphs and Combinatorics, 2(1):95–100, 1986

    work page 1986

  2. [2]

    N. Alon. Neighborly families of boxes and bipartite coverings. InThe Mathematics of Paul Erd¨ os II, pages 27–31. Springer, 1997

    work page 1997

  3. [3]

    N. Alon, S. M. Cioab˘ a, B. D. Gilbert, J. H. Koolen, and B. D. McKay. Addressing johnson graphs, complete multipartite graphs, odd cycles, and random graphs.Experimental Mathematics, 30(3):372–382, 2021

    work page 2021

  4. [4]

    N. Alon, J. Grytczuk, A. P. Kisielewicz, and K. Przes lawski. New bounds on the maximum number of neighborly boxes in rd.European Journal of Combinatorics, 114:103797, 2023

    work page 2023

  5. [5]

    Babu and S

    A. Babu and S. Vishwanathan. Bounds for the Graham-Pollak theorem for hypergraphs.Discrete Mathematics, 342(11):3177–3181, 2019

    work page 2019

  6. [6]

    Babu and S

    A. Babu and S. Vishwanathan. Multicovering hypergraphs.Discrete Math- ematics, 344(6):112386, 2021

    work page 2021

  7. [7]

    Babu and S

    A. Babu and S. Vishwanathan. Improved bounds for covering hypergraphs. arXiv preprint arXiv:2208.12589, 2022

    work page internal anchor Pith review arXiv 2022

  8. [8]

    Buchanan, A

    C. Buchanan, A. Clifton, E. Culver, P. Frankl, J. Nie, K. Ozeki, P. Rom- bach, and M. Yin. On odd covers of cliques and disjoint unions.arXiv preprint arXiv:2408.08598, 2024. 11

    work page arXiv 2024

  9. [9]

    Buchanan, A

    C. Buchanan, A. Clifton, E. Culver, J. Nie, J. O’Neill, P. Rombach, and M. Yin. Odd covers of graphs.Journal of Graph Theory, 104(2):420–439, 2023

    work page 2023

  10. [10]

    Cioab˘ a, A

    S.M. Cioab˘ a, A. K¨ undgen, and J. Verstra¨ ete. On decompositions of complete hypergraphs.Journal of Combinatorial Theory, Series A, 116(7):1232–1234, 2009

    work page 2009

  11. [11]

    Cioab˘ a and M

    S.M. Cioab˘ a and M. Tait. Variations on a theme of Graham and Pollak. Discrete Mathematics, 313(5):665–676, 2013

    work page 2013

  12. [12]

    K. L. Collins and A. N. Trenk. Finding balance: Split graphs and related classes.The Electronic Journal of Combinatorics, pages P1–73, 2018

    work page 2018

  13. [13]

    graphs, matrices and de- signs

    D. de Caen, D.A. Gregory, and D. Pritikin. Minimum biclique partitions of the complete graph and related designs, in “graphs, matrices and de- signs”(R. Rees, Ed.), 1993

    work page 1993

  14. [14]

    R. J. Elzinga, D. A. Gregory, and K. N. Vander Meulen. Addressing the petersen graph.Discrete mathematics, 286(3):241–244, 2004

    work page 2004

  15. [15]

    M. C. Golumbic.Algorithmic graph theory and perfect graphs, volume 57. Elsevier, 2004

    work page 2004

  16. [16]

    Graham and L

    R.L. Graham and L. Lov´ asz. Distance matrix polynomials of trees.Ad- vances in Mathematics, 29(1):60–88, 1978

    work page 1978

  17. [17]

    Graham and H.O

    R.L. Graham and H.O. Pollak. On the addressing problem for loop switch- ing.Bell Labs Technical Journal, 50(8):2495–2519, 1971

    work page 1971

  18. [18]

    Graham and H.O

    R.L. Graham and H.O. Pollak. On embedding graphs in squashed cubes. InGraph theory and applications, pages 99–110. Springer, 1972

    work page 1972

  19. [19]

    Grytczuk, A

    J. Grytczuk, A. P. Kisielewicz, and K. Przes lawski. Neighborly boxes and bipartite coverings; constructions and conjectures.arXiv preprint arXiv:2402.02199, 2024

    work page arXiv 2024

  20. [20]

    P. L. Hammer and B. Simeone. The splittance of a graph.Combinatorica, 1:275–284, 1981

    work page 1981

  21. [21]

    Huang and B

    H. Huang and B. Sudakov. A counterexample to the Alon-Saks-Seymour conjecture and related problems.Combinatorica, 32(2):205–219, 2012

    work page 2012

  22. [22]

    Kratzke, B

    T. Kratzke, B. Reznick, and D West. Eigensharp graphs: Decomposition into complete bipartite subgraphs.Transactions of the American mathe- matical society, 308(2):637–653, 1988

    work page 1988

  23. [23]

    Leader, L

    I. Leader, L. Mili´ cevi´ c, and T.S. Tan. Decomposing the completer-graph. Journal of Combinatorial Theory, Series A, 154(Supplement C):21 – 31, 2018. 12

    work page 2018

  24. [24]

    Leader and T

    I. Leader and T. S. Tan. Odd covers of complete graphs and hypergraphs. arXiv preprint arXiv:2408.05053, 2024

    work page arXiv 2024

  25. [25]

    Leader and T.S

    I. Leader and T.S. Tan. Improved bounds for the Graham-Pollak Prob- lem for Hypergraphs.The Electronic Journal of Combinatorics, 25(1):1–4, 2018

    work page 2018

  26. [26]

    Lyu and I

    B. Lyu and I. V. Hicks. Finding biclique partitions of co-chordal graphs. Discrete Applied Mathematics, 337:278–287, 2023

    work page 2023

  27. [27]

    G.W. Peck. A new proof of a theorem of Graham and Pollak.Discrete Mathematics, 49(3):327–328, 1984

    work page 1984

  28. [28]

    Radhakrishnan, P

    J. Radhakrishnan, P. Sen, and S. Vishwanathan. Depth-3 arithmetic cir- cuits forS 2 n(x) and Extensions of the Graham-Pollak theorem. InInterna- tional Conference on Foundations of Software Technology and Theoretical Computer Science, pages 176–187. Springer, 2000

    work page 2000

  29. [29]

    D. J. Siewert.Biclique covers and partitions of bipartite graphs and digraphs and related matrix ranks of{0, 1}-matrices. University of Colorado at Denver, 2000

    work page 2000

  30. [30]

    Tverberg

    H. Tverberg. On the decomposition ofK n into complete bipartite graphs. Journal of Graph Theory, 6(4):493–494, 1982

    work page 1982

  31. [31]

    Vishwanathan

    S. Vishwanathan. A polynomial space proof of the Graham–Pollak theorem. Journal of Combinatorial Theory, Series A, 115(4):674–676, 2008

    work page 2008

  32. [32]

    Vishwanathan

    S. Vishwanathan. A counting proof of the Graham–Pollak theorem.Dis- crete Mathematics, 313(6):765–766, 2013. 13

    work page 2013