Pith. sign in

REVIEW 1 major objections 6 minor 18 references

On the Chromatic Number of Grassmann Graphs

T0 review · 1 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read The paper proves that for $q=2^e$ and even $n$, the chromatic number of the Grassmann graph $J_q(n,2)$ is strictly less than twice the clique lower bound $\binom{n-1}{1}_q$.

desk verdict Two new bounds for Grassmann graph chromatic numbers, with a real but patchable gap in the q=2^e homomorphism proof and an overstated Beutelspacher citation. read the letter →

arxiv 2505.22055 v1 pith:4IYEQF7U submitted 2025-05-28 math.CO

Jozefien D'haeseleer , Vladislav Taranchuk This is my paper
classification math.CO MSC 05C1551E20
keywords Grassmanngraphchromaticnumberq-analogueofJohnsonq-Kneserlineparallelismprojectivegeometryfinitefieldshomomorphism
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 paper studies the chromatic number of Grassmann graphs $J_q(n,m)$, whose vertices are the $m$-dimensional subspaces of $\mathbb{F}_q^n$ and whose edges join subspaces meeting in dimension $m-1$. It proves the general bounds $\binom{n-m+1}{1}_q \le \chi(J_q(n,m)) \le \binom{n}{1}_q$, the $q$-analogue of the folklore bounds for Johnson graphs. The main new result is for $m=2$, the graph whose vertices are the lines of the finite projective space $\mathrm{PG}(n-1,q)$: when $q=2^e$ and $n$ is even, $\chi(J_q(n,2))$ is strictly less than $2\binom{n-1}{1}_q$, forcing the chromatic number into a factor-of-two window around the clique lower bound. This matters because for these parameters the only previous general upper bound was the trivial degree bound, while the lower bound is the size of a clique and is attained exactly when a line parallelism exists.

What carries the argument

The load-bearing object is the bivariate map $g(x,y)=(x_1y+y_1x)^{q+1}+xy^q+x^qy$ on $V=\mathbb{F}_{q^{2k+1}}\times\mathbb{F}_q \cong \mathbb{F}_q^{2k+2}$. For any two $\mathbb{F}_q$-linearly independent vectors $x,y$, the set $\{g(z,w):z,w\in\langle x,y\rangle\}$ is an $e$-dimensional $\mathbb{F}_2$-subspace, so $g$ sends 2-spaces of $V$ to e-spaces of $\mathbb{F}_2^{(2k+1)e}$; Proposition 3.3 asserts that distinct 2-spaces sharing a 1-space have images meeting only at zero. That makes $g$ a homomorphism from $J_q(2k+2,2)$ into $K_2((2k+1)e,e)$ and converts the known chromatic number of the binary Kneser graph into an upper bound. For the general bounds, the machinery is a Moore-type determinant $\det(x_j^{q^i})_{i,j=0}^{m-1}$, whose value changes by an $\mathbb{F}_q^*$ factor under a change of basis, giving a well-defined coloring by cosets of $\mathbb{F}_{q^n}^*/\mathbb{F}_q^*$.

What would settle it

Search for a counterexample in the smallest nontrivial case, $q=4$, $n=4$: list all 2-spaces of $\mathbb{F}_4^4$ sharing a 1-space and test whether their images under $g$ in $\mathbb{F}_2^9$ intersect trivially; a single intersecting pair would disprove Proposition 3.3 and Theorem 1.3. Equivalently, test whether $cz^{q+1}=wz^q+w^qz$ has a nonzero solution $z\in\mathbb{F}_{4^3}$ for some $w$ and $c\in\mathbb{F}_4^*$.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.3: for every positive integer $e$, with $q=2^e$, and every even $n$, the Grassmann graph $J_q(n,2)$ satisfies $\binom{n-1}{1}_q \le \chi(J_q(n,2)) < 2\binom{n-1}{1}_q$. Equivalently, the lines of $\mathrm{PG}(n-1,q)$ can be partitioned into fewer than twice as many partial spreads as a full line parallelism would require, even in cases where no line parallelism exists. The proof constructs a graph homomorphism from $J_q(2k+2,2)$ into the binary Kneser graph $K_2((2k+1)e,e)$, whose chromatic number is known exactly, and the inequality follows by composing the homomorphism with an optimal coloring of that Kneser graph.

Load-bearing premise

The entire factor-two bound rests on the claim that the equation $cz^{q+1}=wz^q+w^qz$ has no nonzero solution in odd-degree extensions of $\mathbb{F}_{2^e}$; the paper states that the image of $wz^q+w^qz$ is a suitable $\mathbb{F}_q$-subspace but does not supply the trace calculation that makes this true, so this is the step where the argument would break if it broke.

Editorial extensions

If this is right

  • For every even $n$ and $q=2^e$, the chromatic number of $J_q(n,2)$ is forced into the interval $[\binom{n-1}{1}_q, 2\binom{n-1}{1}_q)$, a multiplicative window of width two.
  • Any optimal coloring of the binary Kneser graph $K_2((n-1)e,e)$ translates through $g$ into a coloring of $J_q(n,2)$, so improvements on the Kneser side immediately improve the Grassmann bound.
  • In the cases where line parallelisms are known to exist, including $q=2,4,8,16$ with $n-1$ odd and $n$ a power of two with arbitrary prime power $q$, the new upper bound is consistent with the exact value; in the remaining even-$n$ cases it is the first bound within a constant factor of the lower bound.
  • The concluding computation for $q=4,n=4$ suggests that coloring only the induced subgraph of $e$-spaces produced by $g$ will not close the gap to the lower bound, so the homomorphism is likely not the final step toward exactness.

Reading between the lines

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

  • One could test whether composing $g$ with a structured but non-optimal coloring of the binary Kneser graph still beats the factor-two bound; the paper's small computation indicates the induced subgraph alone is too chromatic, but a different target graph might not be.
  • The determinant coloring for general $m$ is a $q$-analogue of coloring a Johnson graph vertex by the sum of its coordinates modulo $n$; understanding whether it is optimal for $m\ge3$ would parallel the known exact results for $J(n,3)$.
  • If the missing trace argument in Proposition 3.3 is filled, the same homomorphism may adapt to other pairs $(q,n)$ beyond even $n$ and $q=2^e$; conversely, any nonzero solution to the field equation $cz^{q+1}=wz^q+w^qz$ would mark precisely where such an extension fails.
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 / 6 minor

Summary. The paper studies the chromatic number of the Grassmann graph J_q(n,m). Section 2 proves Theorem 1.2, giving lower and upper bounds [n-m+1 choose 1]_q <= chi(J_q(n,m)) <= [n choose 1]_q, via a determinant whose entries are powers of a basis and a coloring by cosets of F_{q^n}^*/F_q^*. Section 3 specializes to m=2 and proves Theorem 1.3: for q=2^e and even n, chi(J_q(n,2)) < 2 [n-1 choose 1]_q. The proof constructs a homomorphism from J_q(2k+2,2) to the 2-Kneser graph K_2((2k+1)e,e) using the function g(x,y)=(x_1y+y_1x)^{q+1}+xy^q+x^qy, then applies known values of chi(K_2(n,m)). The paper also surveys line parallelisms in PG(n-1,q) and their implications for chi(J_q(n,2)).

Significance. If Theorem 1.3 is correct, it provides the first general upper bound for chi(J_q(n,2)) within a factor of 2 of the clique lower bound when q=2^e and n is even, improving on the trivial maximum-degree bound by an order of magnitude. The determinant coloring in Theorem 1.2 is explicit and self-contained, and it gives the q-analogue of the standard Johnson-graph bound. The homomorphism method is constructive and potentially transferable. The paper also helpfully collects known results on line parallelisms, although that survey contains an inconsistency noted below.

major comments (1)
  1. [Section 3, Proposition 3.3, Case 2] The proof of disjointness of the images of h_a and h_b contains an invalid inference. After reducing to (a+b)^2 x^{q+1} = x(y+z)^q + x^q(y+z), the text argues that since the image of wz^q+w^qz is an F_q-linear subspace, the equation cz^{q+1}=wz^q+w^qz has only the zero solution for every c in F_q^*. This does not follow: closure of the image under F_q-scalar multiplication says nothing about whether the nonlinear term cz^{q+1} can lie in that image, and the implication is exactly what needs to be proved. This step is load-bearing because it establishes that the outputs g(S) for distinct 2-spaces through a fixed x are pairwise disjoint, which is needed for the homomorphism to K_2 and hence for Theorem 1.3. The claim is nevertheless true and can be repaired in a few lines: for w != 0, substitute z = c^{-1} w t; the equation becomes t^{q+1}=t^q+t, which is the case w=1 of equation (4) proved in Lemma 3.2, while the case w=0 is immediate. Please replace the invalid inference with this argument.
minor comments (6)
  1. [Introduction, line-parallelism survey (item 2)] The statement that line parallelisms exist in PG(n-1,q) for every prime power q whenever n=2k (k>=2) appears to contradict the later sentence in the same section that existence of line parallelisms is still open for odd n-1, and it makes the following item (q=3,4,8,16) redundant. Please reconcile this with the cited literature; the standard citation of Beutelspacher's theorem covers PG(3,q), and the implication chi(J_q(n,2))=[n-1 choose 1]_q for all even n is not consistent with the current state of the art.
  2. [Section 3, opening] The sentence 'The function which will be used to demonstrate the homomorphism has was introduced by Hawtin' contains a typo ('has was') and should be reworded.
  3. [Section 3, Proposition 3.3, Case 2] The phrase 'Recall that in the proof of Lemma 3.1, we showed that the equation z^{q+1}=wz^q+w^qz only has the solution z=0' should refer to Lemma 3.2, where that equation is actually proved.
  4. [Section 3, Proposition 3.3, Case 1] The parenthetical 'p(x)=x^{q+1} is a permutation polynomial over F_q' should read 'over F_{q^{2k+1}}', as in Lemma 3.2.
  5. [Section 3, Lemma 3.2] In the branch x_1=y_1=0, the sentence 'xy^q+x^qy=0 only has the solution y=alpha x' reuses the symbol alpha that was already used for the assumed nonzero scalar; use a different letter such as c.
  6. [Section 4, Concluding Remarks] The statement that the upper bound 'improves upon the known bounds except when q=2,4,8,16, or when n is itself a power of 2' is not justified in the text; please cite the relevant results or explain the exception for n a power of two.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: both upper bounds are explicit colorings or homomorphisms to independently understood Kneser graphs, with no fitted parameter renamed as a prediction.

full rationale

The paper's claims are derived from explicit constructions and from external known results, not from the target chromatic number. Theorem 1.2 is proved by giving a concrete coloring: each m-space is assigned the coset of its determinant, with well-definedness and validity checked directly; the lower bound is a genuine clique of size [n-m+1 choose 1]_q. Theorem 1.3 is proved by constructing a homomorphism g from J_q(n,2) into the binary Kneser graph K_2((n-1)e,e), whose chromatic number is cited from prior independent work (Blokhuis et al., Chowdhury–Godsil–Royle, plus the elementary e=1 case). The homomorphism property is established by Lemmas 3.1 and 3.2 and Proposition 3.3, all proved in the paper. The only notable issue in the manuscript is a proof gap in Proposition 3.3, Case 2: the paper infers from the F_q-linearity of the image of w z^q + w^q z that c z^{q+1} = w z^q + w^q z has no nonzero solution for every nonzero c. That inference is not valid as written, since linearity of the image alone does not imply scaling the left side by c preserves the no-solution property. However, this is a correctness gap rather than circularity: the missing step is a short algebraic repair (substituting z = c^{-1} w t reduces to Lemma 3.2), and it does not assume or redefine the chromatic number. No fitted parameter is called a prediction, no load-bearing step reduces to a self-citation, and no definition is circular. The derivation is therefore self-contained with respect to circularity.

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

The central proofs rest on standard finite field facts: basis identification, linearized polynomial root bounds, permutation properties of x^{q+1}, and the trace-zero hyperplane. The only substantive external input is the cited chromatic number of binary q-Kneser graphs and the known parallelism results, which are independent prior work. No ad hoc constants or invented objects appear.

assumptions (6)
  • standard math The vector space F_q^n can be identified with the field F_{q^n} by fixing any basis of F_{q^n} over F_q.
    Used at the start of the proof of Theorem 1.2 to define determinants and coset colors.
  • standard math A nonzero linearized polynomial over F_{q^n} of degree q^{m-1} has at most q^{m-1} roots, and a zero determinant of the Wronskian-like matrix characterizes linear dependence.
    Proposition 2.1 relies on these standard finite field facts.
  • domain assumption For q=2^e and N=(2k+1)e, the chromatic number of the binary q-Kneser graph K_2(N,e) equals [N-e+1 choose 1]_2, per Blokhuis et al. and the elementary e=1 case.
    Used in the final step of Theorem 1.3 to bound the number of colors; this is an external cited theorem.
  • standard math In F_{q^{2k+1}} with q=2^e and 2k+1 odd, the image of u -> u^q + u is the trace-zero hyperplane, so no nonzero element of F_q lies in that image.
    The needed, unstated justification for the scaled equation in Proposition 3.3 Case 2.
  • standard math The map t -> t^{q+1} is a permutation of F_{q^{2k+1}} when gcd(q+1, q^{2k+1}-1)=1, which holds for q=2^e and 2k+1 odd.
    Used in Lemma 3.2 and Proposition 3.3 to show certain equations only have the zero solution.
  • domain assumption Known existence results for line parallelisms in PG(n-1,q), due to Baker, Beutelspacher, Feng-Xu, and Meszka, are correct.
    Used in the survey and concluding remarks, not in the proofs of Theorems 1.2 and 1.3.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the Chromatic Number of Grassmann Graphs." pith.science (2026). https://pith.science/paper/4IYEQF7U

@misc{pith2026250522055,
  author       = {Pith},
  title        = {Pith review of: On the Chromatic Number of Grassmann Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4IYEQF7U}},
  note         = {Machine review of arXiv:2505.22055}
}
abstract

In this paper we study the chromatic number of the Grassmann graphs $J_q(n, m)$. We show that $\binom{n-m+1}{1}_q \leq \chi(J_q(n, m)) \leq \binom{n}{1}_q$, which is analogous to the best-known bounds for the chromatic number of the Johnson graphs $J(n, m)$. When $m = 2$, determining $\chi(J_q(n, 2))$ is equivalent to determining the smallest number of partial line parallelisms that one can partition the lines of PG$(n-1, q)$ into. We survey known results about line parallelisms and their implications for $\chi(J_q(n, 2))$. Finally, we prove that when $q$ is any power of two, and $n$ is any even integer, then $\chi(J_q(n, 2)) < 2\binom{n-1}{1}_q$.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

18 extracted references · 16 canonical work pages

  1. [1]

    R. D. Baker. Partitioning the planes of AG 2m(2) into 2-designs. Discrete Math. , 15(3):205–211, 1976

    work page 1976

  2. [2]

    Beutelspacher

    A. Beutelspacher. On parallelisms in finite projective spaces. Geometriae Dedicata, 3:35–40, 1974

    1974

  3. [3]

    Blokhuis, A

    A. Blokhuis, A. E. Brouwer, A. Chowdhury, P. Frankl, T. Mussche, B. Patk´ os, and T. Sz˝ onyi. A Hilton-Milner theorem for vector spaces. Electron. J. Combin. , 17(1):Re- search Paper 71, 12, 2010

    work page 2010

  4. [4]

    Chowdhury, C

    A. Chowdhury, C. Godsil, and G. Royle. Colouring lines in projective space. J. Combin. Theory Ser. A , 113(1):39–52, 2006

    work page 2006

  5. [5]

    T. Etzion. Optimal partitions for triples. J. Combin. Theory Ser. A , 59(2):161–176, 1992

    work page 1992

  6. [6]

    T. Etzion. Partitions of triples into optimal packings. J. Combin. Theory Ser. A , 59(2):269–284, 1992

    work page 1992

  7. [7]

    Etzion and S

    T. Etzion and S. Bitan. On the chromatic number, colorings, and codes of the Johnson graph. Discrete Appl. Math. , 70(2):163–175, 1996

    work page 1996

  8. [8]

    R. L. Graham and N. J. A. Sloane. Lower bounds for constant weight codes. IEEE Trans. Inform. Theory, 26(1):37–43, 1980

    work page 1980

Show all 18 references
  1. [9]

    D. R. Hawtin. Transitive ( q − 1)-fold packings of PGn(q). Discrete Math., 348(3):Paper No. 114330, 4, 2025

    2025

  2. [10]

    J. W. P. Hirschfeld. Projective geometries over finite fields . Oxford Mathematical Monographs. The Clarendon Press, Oxford University Press, New York, second edition, 1998

    1998

  3. [11]

    Ihringer

    F. Ihringer. The chromatic number of the q-Kneser graph for large q. Electron. J. Combin., 26(1):Paper No. 1.50, 12, 2019

    2019

  4. [12]

    N. L. Johnson. Combinatorics of spreads and parallelisms , volume 295 of Pure and Applied Mathematics (Boca Raton) . CRC Press, Boca Raton, FL, 2010. 11

    2010

  5. [13]

    Lov´ asz

    L. Lov´ asz. Kneser’s conjecture, chromatic number, and homotopy. J. Combin. Theory Ser. A , 25(3):319–324, 1978

    1978

  6. [14]

    J. X. Lu. On large sets of disjoint Steiner triple systems. I. J. Combin. Theory Ser. A , 34(2):140–146, 1983

    1983

  7. [15]

    J. X. Lu. On large sets of disjoint Steiner triple systems. IV, V, VI. J. Combin. Theory Ser. A , 37(2):136–163, 164–188, 189–192, 1984

    1984

  8. [16]

    M. Meszka. The chromatic index of projective triple systems. J. Combin. Des. , 21(11):531–540, 2013

    2013

  9. [17]

    Teirlinck

    L. Teirlinck. A completion of Lu’s determination of the spectrum for large sets of disjoint Steiner triple systems. J. Combin. Theory Ser. A , 57(2):302–305, 1991

    1991

  10. [18]

    Xu and T

    L. Xu and T. Feng. The chromatic index of finite projective spaces. Journal of Combi- natorial Designs , 31(9):432–446, 2023. 12

    2023

Pith tools

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