Pith. sign in

REVIEW 1 minor 1 cited by

A note on the Alon-Saks-Seymour problem

T0 review · 0 major / 1 minor · reviewed 2026-06-29 · grok-4.3

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

Pith's one-line read The function f(k) obeys the recursion f(k+1) ≤ f(k) + f(⌊k/4⌋), which solves to the explicit bound f(k) ≤ 2^{(log₂(4k))²/4}.

desk verdict Fox's note gives a clean new recursion f(k+1) ≤ f(k) + f(⌊k/4⌋) that halves the exponent in the best upper bound for the Alon-Saks-Seymour function. read the letter →

arxiv 2605.28915 v1 pith:GUQSUXVD submitted 2026-05-27 math.CO cs.DM

Jacob Fox This is my paper · ORCID
classification math.COcs.DM
keywords Alon-Saks-Seymourproblembicliquepartitionchromaticnumberrecursivebounduppercompletebipartitegraphsgraphcoloring
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

f(k) is the largest chromatic number that any graph can have when its edges are partitioned into at most k complete bipartite graphs. The paper supplies a direct combinatorial argument showing that any such graph on k+1 bicliques can be decomposed so its chromatic number is at most the sum of the numbers for a k-biclique graph and a roughly k/4-biclique graph. Solving the resulting recurrence produces the stated closed-form upper bound. The new bound cuts the exponent in the previous best upper bound by a factor approaching two. The result sits within a lower-order factor of the known construction that forces f(k) to be at least roughly 2 to the square of the log of k.

What carries the argument

The recursive inequality f(k+1) ≤ f(k) + f(⌊k/4⌋) obtained by partitioning the biclique cover of a (k+1)-graph into a k-cover and an approximately (k/4)-cover whose proper colorings combine without added colors.

What would settle it

An explicit graph whose edges partition into k+1 bicliques yet whose chromatic number exceeds f(k) + f(⌊k/4⌋) for some concrete k where the values of f are known or computable.

Watch

Extended reading notes

Core claim

We give a simple proof of the recursive upper bound f(k+1) ≤ f(k) + f(⌊k/4⌋). Consequently, f(k) ≤ 2^{(log_2 (4k))^2/4} for k ≥ 1. This improves the previous best known upper bound of Mubayi and Vishwanathan in the exponent by a factor which is asymptotically two. Note that these bounds are sharp up to a lower order factor in the exponent by the result of Balodis et al.

Load-bearing premise

Any biclique partition of size k+1 can be split into a partition of size k and one of size roughly k/4 such that the two resulting graphs can be colored separately and the colorings merged without using more colors than the sum of the two chromatic numbers.

Editorial extensions

If this is right

  • f(k) is at most 2 raised to (log base 2 of 4k) squared over 4.
  • The exponent is asymptotically half that of the Mubayi-Vishwanathan bound.
  • The upper bound matches the Balodis et al. lower bound up to lower-order terms in the exponent.
  • Iterating the recursion gives successively tighter numerical bounds for small k.

Reading between the lines

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

  • A different splitting ratio than 4 might produce a stronger recurrence.
  • The same partitioning idea may apply to other parameters that count the minimum number of bicliques needed to cover or partition the edges.
  • The technique could be tested on small explicit graphs to see whether the recursion is tight for moderate k.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 1 minor

Summary. The paper defines f(k) as the largest chromatic number of any graph whose edges can be partitioned into at most k bicliques. It supplies a direct combinatorial argument establishing the recursion f(k+1) ≤ f(k) + f(⌊k/4⌋) and solves the recurrence to obtain the explicit upper bound f(k) ≤ 2^{(log_2 (4k))^2/4} for k ≥ 1. This improves the exponent in the Mubayi–Vishwanathan bound by an asymptotic factor of two and is noted to be tight up to lower-order terms in the exponent by the Balodis et al. lower bound.

Significance. The result strengthens the best known upper bound on f(k) in the Alon–Saks–Seymour problem while supplying a short, self-contained, parameter-free combinatorial proof of the key recursion. The derived closed-form bound halves the previous exponent and narrows the gap to the known 2^{ ilde{\Omega}((\log k)^2)} lower bound to a lower-order factor. The manuscript therefore supplies both a quantitative improvement and a transparent argument that can be checked directly.

minor comments (1)
  1. The statement of the bound in the abstract and introduction should explicitly record the base cases used to initiate the recurrence (e.g., the values of f(1) through f(4)) so that the induction is fully anchored.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the manuscript, for highlighting the improvement over the Mubayi–Vishwanathan bound, and for recommending acceptance. We have no revisions to make in response to the report.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity

full rationale

The paper establishes the recursive upper bound f(k+1) ≤ f(k) + f(⌊k/4⌋) via an explicit combinatorial partitioning argument that decomposes a (k+1)-biclique cover into a k-cover and an ⌊k/4⌋-cover; this step is self-contained and does not rely on any fitted parameters, self-referential definitions, or prior results by the same author. The closed-form bound is then obtained by standard iteration of the recurrence under monotonicity, which is a mechanical consequence rather than a reduction to the target quantity. No load-bearing self-citations, ansatzes, or renamings appear in the derivation chain.

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

The paper is a short combinatorial proof note that relies only on standard definitions of chromatic number and biclique edge partitions; it introduces no free parameters, ad-hoc axioms, or new entities.

assumptions (1)
  • standard math Standard definitions and basic properties of graph chromatic number and edge partitions into complete bipartite graphs.
    The function f(k) and the recursion are defined and proved using these background concepts from graph theory.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A note on the Alon-Saks-Seymour problem." pith.science (2026). https://pith.science/paper/GUQSUXVD

@misc{pith2026260528915,
  author       = {Pith},
  title        = {Pith review of: A note on the Alon-Saks-Seymour problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GUQSUXVD}},
  note         = {Machine review of arXiv:2605.28915}
}
abstract

Let $f(k)$ be the maximum possible chromatic number of a graph whose edge set can be partitioned into at most $k$ complete bipartite graphs. Alon, Saks, and Seymour conjectured that $f(k)=k+1$ for all $k$. While the conjecture was verified for $k \leq 9$ by Gao et al., it was disproved by Huang and Sudakov, and further Balodis et al. proved that $f(k) \geq 2^{\widetilde{\Omega}((\log k)^2)}$. In this note, we give a simple proof of the recursive upper bound $f(k+1) \leq f(k)+f(\lfloor k/4 \rfloor)$. Consequently, $f(k) \leq 2^{(\log_2 (4k))^2/4}$ for $k \geq 1$. This improves the previous best known upper bound of Mubayi and Vishwanathan in the exponent by a factor which is asymptotically two. Note that these bounds are sharp up to a lower order factor in the exponent by the result of Balodis et al.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Optimal Unambiguous DNFs and Alon-Saks-Seymour

    cs.CC 2026-08 accept novelty 8.0 of 10

    Optimal unambiguous DNFs yield χ(G)≥exp(Ω(log² bp(G))), matching the known upper bound and resolving the Alon-Saks-Seymour problem up to constants.

Reference graph

Works this paper leans on

5 extracted references · cited by 1 Pith paper

  1. [1]

    Balodis, S

    K. Balodis, S. Ben-David, M. Göös, S. Jain, and R. Kothari, Unambiguous DNFs and Alon-Saks- Seymour,SIAM J. Comput., Special Section FOCS 2021 (2023), FOCS21-157–FOCS21-173

    2021

  2. [2]

    Z. Gao, B. D. McKay, R. Naserasr, and B. Stevens, Bipartite edge partitions and the former Alon- Saks-Seymour conjecture,Australas. J. Combin.66(2016), 211–228

    2016

  3. [3]

    Göös, Lower bounds for clique vs

    M. Göös, Lower bounds for clique vs. independent set, inFOCS 2015, pp. 1066–1076

    2015

  4. [4]

    Huang and B

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

    2012

  5. [5]

    Mubayi and S

    D. Mubayi and S. Vishwanathan, Bipartite coverings and the chromatic number,Electron. J. Combin. 16(2009), Note 34, 5 pp. 2

    2009

Pith tools

Reviewed June 29, 2026 · model on record in the stance chip above.