pith. sign in

arxiv: 2606.08506 · v2 · pith:GWJF4DTAnew · submitted 2026-06-07 · 🧮 math.CO · cs.DM

Almost balanced ordered biclique covering of graphs

Anand Babu , Ervin Ranjan , Maddipati Deshith Sai , Jatla Naga Sidhartha , Anagh Indu Suresh , Sreedhara Vishwas This is my paper

Pith reviewed 2026-06-27 18:08 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords biclique coveringordered bicliquesbalanced coveringGraham-Pollak theoremK_nmultiplicitycovering number
0
0 comments X

The pith

The paper proves nearly matching bounds on the size of almost-balanced ordered biclique coverings of K_n for fixed multiplicity k.

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

The paper defines f(n,k) as the smallest number of bicliques needed to cover every edge of the complete graph K_n at least once but at most k times, with an almost-balance condition on the ordering for each edge. It extends the Graham-Pollak theorem for k=1 and known results for k=2 by providing bounds for general fixed k. The main result shows that f(n,k) is at least roughly n to the power 1 over ceil(k/2) plus one, and at most roughly n to the power 1 over floor(k/2) plus one with an additional o(1) in the exponent. This matters because it shows how the covering size decreases as k increases in a specific polynomial way.

Core claim

For fixed k ≥ 2, (1+o(1))c1(k)·n^{1/(⌈k/2⌉+1)} ≤ f(n,k) ≤ (1+o(1))c2(k)·n^{1/(⌊k/2⌋+1)+o(1)}, where f(n,k) is the minimum size of a collection of bicliques such that every edge of K_n is covered by at least one and at most k bicliques, and for each edge the number of coverings in each direction differs by at most one.

What carries the argument

The function f(n,k) measuring the minimum size of an almost-balanced ordered biclique covering with multiplicity at most k.

If this is right

  • The lower bound exponent depends on ceil(k/2) +1.
  • The upper bound exponent depends on floor(k/2) +1 plus a vanishing term.
  • For k=2 the bounds reduce to the known square-root order.
  • Constants c1(k) and c2(k) exist that make the (1+o(1)) factors work.

Where Pith is reading between the lines

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

  • The balance condition may not change the asymptotic order compared to standard biclique coverings.
  • Similar bounds could hold for coverings of other dense graphs.
  • The construction for the upper bound might be adaptable to find explicit coverings for small k.

Load-bearing premise

The counting argument for the lower bound remains valid and achieves the stated exponent even after imposing the almost-balance condition on the coverings.

What would settle it

Finding the asymptotic growth rate of f(n,3) for large n and checking whether it matches n to the power 1/3 or is larger would test the lower bound.

read the original abstract

Let $f(n,k)$ be the minimum size of a collection of bicliques such that (i) every edge of the complete graph $K_n$ is covered by at least one and at most $k$ bicliques in the collection, and (ii) for each edge $\{u,v\}$, the number of bicliques in which $u$ appears in the first class and $v$ in the second class differs by at most one from the number of bicliques in which $u$ appears in the second class and $v$ in the first class. For $k=1$, $f(n,k)$ reduces to the biclique partition number of $K_n$, and the Graham-Pollak theorem gives $f(n,1)=n-1$. For $k=2$, $f(n,k)$ is the ordered biclique partition number of $K_n$, for which it is known that $c_1 n^{1/2} \le f(n,2) \le c_2 n^{1/2+o(1)}$ for some positive constants $c_1$ and $c_2$. In this note, we give almost tight bounds for $f(n,k)$ for fixed $k \ge 2$: \[ (1+o(1))c_1(k)\cdot n^{\frac{1}{\lceil k/2\rceil+1}} \le f(n,k) \le (1+o(1))c_2(k)\cdot n^{\frac{1}{\lfloor k/2\rfloor+1}+o(1)}, \] where $c_1(k)$ and $c_2(k)$ are positive constants.

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 / 1 minor

Summary. The paper defines f(n,k) as the minimum number of ordered bicliques such that every edge of K_n is covered between 1 and k times and, for each edge {u,v}, the number of coverings with u in the first part and v in the second differs by at most 1 from the reverse orientation. It proves that for each fixed k ≥ 2 the quantity satisfies (1+o(1))c_1(k) n^{1/(⌈k/2⌉+1)} ≤ f(n,k) ≤ (1+o(1))c_2(k) n^{1/(⌊k/2⌋+1)+o(1)}.

Significance. If the stated exponents are correct, the result supplies the first almost-tight asymptotic description of ordered biclique coverings under an almost-balance constraint, extending the Graham-Pollak theorem (k=1) and the known square-root bounds for k=2. The dependence of the exponents on ⌈k/2⌉ and ⌊k/2⌋ is a clean structural outcome that would be of interest to researchers working on biclique partitions, signed coverings, and algebraic methods in extremal graph theory.

major comments (1)
  1. [Lower-bound argument (main theorem)] The lower-bound claim (1+o(1))c_1(k) n^{1/(⌈k/2⌉+1)} extends a Graham-Pollak-style algebraic or counting argument to multiplicity-k ordered bicliques. The almost-balance condition forces the signed rank-1 matrices to nearly cancel off the diagonal; this may create additional linear dependencies not present in the unbalanced or k=2 setting. The manuscript must exhibit an explicit argument (in the section containing the lower-bound proof) showing that these dependencies do not raise the minimal number of summands above the claimed exponent. Without such a control the exponent 1/(⌈k/2⌉+1) is not guaranteed to survive.
minor comments (1)
  1. [Abstract] The abstract states that c_1(k) and c_2(k) are positive constants but gives no indication of how they are obtained; a one-sentence description of their origin (e.g., “arising from the solution of a certain linear program” or “from an explicit random construction”) would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for highlighting a potential subtlety in the lower-bound argument. We address the comment below and will incorporate a clarifying paragraph in the revised manuscript.

read point-by-point responses

  1. Referee: [Lower-bound argument (main theorem)] The lower-bound claim (1+o(1))c_1(k) n^{1/(⌈k/2⌉+1)} extends a Graham-Pollak-style algebraic or counting argument to multiplicity-k ordered bicliques. The almost-balance condition forces the signed rank-1 matrices to nearly cancel off the diagonal; this may create additional linear dependencies not present in the unbalanced or k=2 setting. The manuscript must exhibit an explicit argument (in the section containing the lower-bound proof) showing that these dependencies do not raise the minimal number of summands above the claimed exponent. Without such a control the exponent 1/(⌈k/2⌉+1) is not guaranteed to survive.

    Authors: We agree that an explicit control on possible extra dependencies is desirable for clarity. Our lower-bound proof proceeds by associating to each ordered biclique a signed rank-1 matrix whose off-diagonal entries are +1 or -1 according to the orientation, then summing these matrices with coefficients in {0,…,k} while enforcing the almost-balance condition (difference at most 1). The resulting matrix has entries bounded by k and is therefore invertible only if its rank is at least the claimed dimension; the balance condition is used directly to bound the Frobenius norm and to guarantee that the kernel dimension cannot exceed the unbalanced case by more than a constant factor independent of n. Nevertheless, to satisfy the referee’s request we will insert a short dedicated paragraph immediately after the main counting step that spells out why the near-cancellation on the diagonal does not introduce additional linear relations capable of lowering the required number of summands below the stated exponent. This addition will appear in the revised version of the lower-bound section. revision: yes

Circularity Check

0 steps flagged

No circularity: bounds extend known Graham-Pollak and k=2 results via independent constants

full rationale

The paper defines f(n,k) directly from the almost-balanced ordered biclique covering condition and states asymptotic bounds in terms of n and k-dependent positive constants c1(k), c2(k). The k=1 case reduces exactly to the external Graham-Pollak theorem (f(n,1)=n-1). The k=2 case is cited as previously known with matching exponents. No equations, parameters, or self-citations are shown to reduce the claimed exponents or constants to fitted inputs or prior self-referential definitions. The derivation chain therefore remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on the Graham-Pollak theorem for the base case and standard combinatorial techniques (counting or algebraic methods) for the generalization; no free parameters are fitted and no new entities are postulated.

axioms (1)
  • standard math Graham-Pollak theorem: the biclique partition number of K_n is n-1
    Invoked explicitly to recover the k=1 case and as the starting point for generalization.

pith-pipeline@v0.9.1-grok · 5869 in / 1384 out tokens · 30724 ms · 2026-06-27T18:08:49.997945+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

27 extracted references · 4 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

    1986

  2. [2]

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

    1997

  3. [3]

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

    2023

  4. [4]

    K. Amano. Upper bounds on the Ordered Biclique partition number of complete graphs.Discrete Applied Mathematics, 166:249–254, 2014

    2014

  5. [5]

    BoundsfortheGraham-Pollaktheoremfor hypergraphs.Discrete Mathematics, 342(11):3177–3181, 2019

    A.BabuandS.Vishwanathan. BoundsfortheGraham-Pollaktheoremfor hypergraphs.Discrete Mathematics, 342(11):3177–3181, 2019

    2019

  6. [6]

    Multicoveringhypergraphs.DiscreteMath- ematics, 344(6):112386, 2021

    A.BabuandS.Vishwanathan. Multicoveringhypergraphs.DiscreteMath- ematics, 344(6):112386, 2021

    2021

  7. [7]

    Improved Bounds for Multicovering Hypergraphs

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

    work page internal anchor Pith review Pith/arXiv arXiv 2022

  8. [8]

    Buchanan, A

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

    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

    2023

  10. [10]

    Cheng, M

    X. Cheng, M. Wang, Z. Xu, and C. H. Yip. Exact values and improved boundsonk-neighborlyfamiliesofboxes.EuropeanJournalofCombinatorics, 118:103926, 2024

    2024

  11. [11]

    S. M. Cioabă, A. Kündgen, and J. Verstraëte. On decompositions of com- plete hypergraphs.Journal of Combinatorial Theory, Series A, 116(7):1232– 1234, 2009

    2009

  12. [12]

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

    2013

  13. [13]

    Graphs,Matricesand Designs

    D. de Caen, D. A. Gregory, and D. Pritikin. Minimum biclique parti- tionsofthecompletegraphandrelateddesigns,in“Graphs,Matricesand Designs” (r. rees, ed.), 1993

    1993

  14. [14]

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

    1971

  15. [15]

    Onembeddinggraphsinsquashedcubes

    R.L.GrahamandH.O.Pollak. Onembeddinggraphsinsquashedcubes. InGraph Theory and Applications, pages 99–110. Springer, 1972

    1972

  16. [16]

    Grytczuk, A

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

    work page arXiv 2024

  17. [17]

    G. Hansel. Nombre minimal de contacts de fermeture nécessaires pour réaliserunefonctionbooléennesymétriquedenvariables.ComptesRendus Hebdomadaires Des Seances De L Academie Des Sciences, 258(25):6037, 1964

    1964

  18. [18]

    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

    2012

  19. [19]

    Leader, L

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

    2018

  20. [20]

    Leader and T

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

    2018

  21. [21]

    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

  22. [22]

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

    1984

  23. [23]

    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. InFounda- tionsofSoftwareTechnologyandTheoreticalComputerScience,pages176–187. Springer, 2000

    2000

  24. [24]

    Orderedbicliquepartitionsandcommunication complexity problems.Discrete Applied Mathematics, 184:248–252, 2015

    Y.ShigetaandK.Amano. Orderedbicliquepartitionsandcommunication complexity problems.Discrete Applied Mathematics, 184:248–252, 2015

    2015

  25. [25]

    Tverberg

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

    1982

  26. [26]

    Vishwanathan

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

    2008

  27. [27]

    Vishwanathan

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

    2013