arxiv: 2605.12030 · v2 · submitted 2026-05-12 · 🧮 math.CO

Recognition: 2 theorem links

· Lean Theorem

A note on the chromatic number of Kneser graphs on chambers of projective planes and incidence-free sets

Klaus Metsch, Philipp Heering, Vladislav Taranchuk

Pith reviewed 2026-05-13 04:52 UTC · model grok-4.3

classification 🧮 math.CO

keywords Kneser graphchromatic numberprojective planesymmetric designincidence-free setperfect matchingincidence graph

0 comments

The pith

The chromatic number of the Kneser graph on chambers of a projective plane equals the incidence-free number of its incidence graph.

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

The paper gives an elementary proof that any symmetric design with an equinumerous incidence-free pair leaves a perfect matching between the remaining points and blocks in its incidence graph. It then applies the matching to prove that the chromatic number of the Kneser graph whose vertices are the chambers of a projective plane is exactly the maximum size of an incidence-free set in the plane's incidence structure. This equivalence unifies two quantities previously studied in separate parts of the literature on designs and graphs. A sympathetic reader would care because any bound or exact value obtained for one quantity immediately yields the same result for the other, and the result holds for every projective plane.

Core claim

In a symmetric (v,k,λ)-design D=(P,B), if (X,Y) is an equinumerous incidence-free pair, then the incidence graph admits a perfect matching between P minus X and B minus Y. This matching is used to establish that the chromatic number of the Kneser graph on the chambers of a projective plane is identical to the incidence-free number of the plane's incidence graph.

What carries the argument

The perfect matching between the remaining points and blocks after removal of an equinumerous incidence-free pair from a symmetric design, which directly equates the two graph parameters.

If this is right

The equivalence holds for every projective plane rather than only those with sufficiently large block size.
Any upper or lower bound previously known for one quantity transfers directly to the other.
Computations or constructions for incidence-free sets can now be reinterpreted as colorings of the chamber Kneser graph and vice versa.

Where Pith is reading between the lines

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

Matching algorithms from graph theory could be applied to compute or bound the common value for small planes.
The same matching technique might extend to other symmetric designs that are not projective planes.
The unification suggests checking whether known chromatic-number results for related Kneser graphs have direct design-theoretic translations.

Load-bearing premise

The argument requires the structure to be a symmetric design so that points and blocks are equinumerous, together with the removed sets having equal size and containing no incidences between them.

What would settle it

A symmetric design containing an equinumerous incidence-free pair whose removal leaves the incidence graph without a perfect matching, or a projective plane in which the Kneser chromatic number differs from the incidence-free number, would disprove the claims.

read the original abstract

Let $D=(\mathcal{P},\mathcal{B})$ be a symmetric $(v,k,\lambda)$-design and let $(X,Y)$ be an equinumerous incidence-free pair, with $X\subseteq \mathcal{P}$ and $Y\subseteq \mathcal{B}$. In this note, we give an elementary proof which shows the existence of a perfect matching between $\mathcal{P} \setminus X$ and $\mathcal{B}\setminus Y$ in the incidence graph of $D$. This recovers a result of Spiro, Adriaensen and Mattheus, who already showed this using different arguments for $k\geq 36$. We use this to connect some dots in the literature and prove that finding the chromatic number of the Kneser graph on chambers of a projective plane is equivalent to finding the incidence-free number of the incidence graph of the plane.

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.

Desk Editor's Note private letter to a colleague

This note gives an elementary Hall's theorem proof of perfect matchings in symmetric designs after removing equinumerous incidence-free pairs, then equates the Kneser chromatic number on chambers to the incidence-free number.

read the letter

The punchline is that the authors recover the Spiro-Adriansen-Mattheus matching result for all parameters with a short double-counting plus Hall argument, and they turn the matching into an explicit equivalence between the chromatic number of the Kneser graph on chambers and the maximum incidence-free set size in the incidence graph of a projective plane. Both directions of the equivalence are spelled out directly from the matching property. That connection is new and cleanly stated. The proof itself looks elementary and avoids the earlier size restriction, which is the main technical step forward. The paper does this without extra machinery, so the argument is easy to check once you have the incidence graph in front of you. Soft spots are limited. The scope stays narrow to symmetric designs and projective planes, so the result mainly helps people already working on Kneser graphs or incidence structures rather than opening a broad new direction. The equivalence follows mechanically once the matching is in hand, so the novelty sits mostly in making that link explicit rather than in a deeper structural insight. No circularity or hidden parameter restrictions appear in the outline. This is for readers in finite geometry and extremal graph theory who care about chromatic numbers of design-derived graphs. Someone already following the Spiro et al. line or looking for elementary reductions in design graphs will find it useful. It deserves a serious referee because the proof is short, self-contained, and removes an artificial bound while adding a usable equivalence; a referee can verify the Hall application in a few pages and decide if the connection is worth archiving.

Referee Report

0 major / 3 minor

Summary. The paper gives an elementary proof that any symmetric (v,k,λ)-design D admits a perfect matching in its incidence graph between P∖X and B∖Y whenever (X,Y) is an equinumerous incidence-free pair. It then uses the matching to show that the chromatic number of the Kneser graph on chambers of a projective plane equals the incidence-free number of the plane's incidence graph, thereby equating two quantities previously studied separately in the literature.

Significance. The elementary argument via double counting and Hall's theorem recovers the matching result of Spiro–Adriansen–Mattheus (previously obtained only for k≥36 by different methods) and establishes a direct equivalence between the Kneser chromatic number on chambers and the incidence-free number. This linkage is a clear contribution that may allow techniques from one problem to be transferred to the other; the explicit, parameter-free derivation is a strength.

minor comments (3)

[Proof of Theorem 1] The statement of Hall's condition in the proof of the matching (around the application after removing X and Y) would benefit from an explicit sentence confirming that the neighborhood sizes remain at least as large as the subset sizes for all subsets of P∖X.
[Section 3] The equivalence direction from colorings to incidence-free sets is sketched but would be clearer if the correspondence between color classes and the removed sets (X,Y) were written as a short lemma with the exact size relation.
[Introduction] A brief comparison paragraph noting how the new argument differs from Spiro et al. (e.g., avoidance of the k≥36 hypothesis) would help readers situate the note.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript and for the positive assessment. We are grateful for the recommendation to accept the paper.

Circularity Check

0 steps flagged

No significant circularity; elementary matching proof is self-contained

full rationale

The paper supplies an independent elementary argument (double counting plus Hall's theorem on the bipartite incidence graph of a symmetric (v,k,λ)-design after deleting an equinumerous incidence-free pair) that establishes the perfect matching. This argument does not rely on the prior result of Spiro et al. as a premise; it recovers that result for smaller k while deriving the Kneser-chromatic-number equivalence directly from the matching correspondence. No step reduces by definition to its own inputs, no fitted parameter is renamed as a prediction, and the central claim rests on explicit combinatorial reasoning rather than a self-citation chain.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claims rest on the standard definition and incidence properties of symmetric designs together with basic bipartite matching theorems; no new free parameters or invented entities are introduced.

axioms (1)

standard math Every pair of distinct points lies in exactly λ blocks and every pair of distinct blocks intersects in exactly λ points (symmetric design axioms).
Invoked implicitly in the definition of D and the incidence graph throughout the note.

pith-pipeline@v0.9.0 · 5448 in / 1284 out tokens · 70382 ms · 2026-05-13T04:52:22.880879+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

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

IndisputableMonolith.Foundation.RealityFromDistinction reality_from_one_distinction unclear
Theorem 1.1: equinumerous incidence-free pair yields perfect matching in incidence graph via local λ-regular matchings and fractional matching weights
IndisputableMonolith.Cost.FunctionalEquation washburn_uniqueness_aczel unclear
Corollary 1.5: optimal coloring of Kneser graph on chambers equivalent to maximum equinumerous incidence-free set