Note on polychromatic coloring of hereditary hypergraph families II

D\"om\"ot\"or P\'alv\"olgyi

arxiv: 2604.24412 · v1 · submitted 2026-04-27 · 🧮 math.CO · cs.DM

Note on polychromatic coloring of hereditary hypergraph families II

D\"om\"ot\"or P\'alv\"olgyi This is my paper

Pith reviewed 2026-05-08 02:23 UTC · model grok-4.3

classification 🧮 math.CO cs.DM

keywords hypergraphpolychromaticcoloringconstructioneveryfamilieshereditaryuniform

0 comments

The pith

For every h >= 4 there exists a (2h-1)-uniform hypergraph with no polychromatic 3-coloring whose h-heavy restricted subhypergraphs are all 2-colorable, obtained as the complement of a suitable h-uniform hypergraph on 3h-1 vertices.

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

In hypergraph coloring a polychromatic coloring is one in which every edge receives many different colors. The authors want to know how large the edges must be before one can force a hypergraph to have no 3-coloring that is polychromatic on every edge. They build an example hypergraph whose edges all have size 2h-1. This hypergraph itself cannot be colored with three colors so that every edge sees all three colors. Yet if one looks only at the parts that contain at least h edges from any given collection, those parts can still be colored with two colors. The construction starts from ordinary h-uniform hypergraphs on 3h-1 points and takes their complements. For large h the existence of the right starting hypergraph is shown by a random counting argument. For the eight small values h from 4 to 8 the authors simply check every possible candidate by computer and list the working examples.

Core claim

For every integer h >= 4 we construct a (2h-1)-uniform hypergraph which has no polychromatic 3-coloring, but all of whose h-heavy restricted subhypergraphs are 2-colorable.

Load-bearing premise

That the complements of the chosen h-uniform hypergraphs on 3h-1 vertices indeed satisfy the polychromatic non-3-colorability while preserving 2-colorability of all h-heavy restrictions; this is verified probabilistically for h >= 9 and by exhaustive enumeration for 4 <= h <= 8.

read the original abstract

We extend a recent construction concerning polychromatic colorings of hereditary hypergraph families. For every integer $h\ge 4$ we construct a $(2h-1)$-uniform hypergraph which has no polychromatic $3$-coloring, but all of whose $h$-heavy restricted subhypergraphs are $2$-colorable. Together with the previously known case $h=3$, this gives examples with uniformity $2h-1$ for every $h\ge 3$. The construction is based on complements of suitable $h$-uniform hypergraphs on $3h-1$ vertices. For $h\ge 9$ we prove existence by a simple probabilistic argument; the remaining cases $4\le h\le 8$ are certified by a short exhaustive computer check, whose fully reproducible description and source code are included in the appendix.

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 extends the h=3 polychromatic construction to all h>=4 via complements on 3h-1 vertices, with a clean probabilistic proof for large h and reproducible computer checks for small h.

read the letter

The main takeaway is that the author finishes the job of producing (2h-1)-uniform examples that fail to be polychromatic 3-colorable while keeping all h-heavy restricted subhypergraphs 2-colorable. The method is the same complement construction used for h=3, now shown to work for every larger h. For h at least 9 a first-moment calculation on random h-uniform hypergraphs on 3h-1 points gives positive probability of the desired properties. For h from 4 to 8 the author simply enumerates all possibilities and certifies the good ones, with the exact search code and parameters printed in the appendix. Both routes are direct and checkable, so the central claim holds up without circularity or hidden parameters. The paper is short and focused. It adds the missing uniformities and supplies the verification tools, which is exactly what the subfield needs to know the bound 2h-1 is tight in this hereditary setting. The only real limitation is that the probabilistic argument is non-constructive for large h, but the statement only claims existence so that is not a flaw. The computer cases are finite and fully documented, which removes any practical doubt. Readers already working on polychromatic or hereditary hypergraph coloring will find this useful as a direct follow-up; it does not reorganize the broader area but it closes a clear gap with transparent evidence. The work is precise enough and the supporting material is reproducible enough that it should go to a serious referee rather than be desk-rejected.

Referee Report

0 major / 0 minor

Summary. The manuscript extends previous work on polychromatic colorings of hereditary hypergraph families. For every integer h ≥ 4, it constructs a (2h-1)-uniform hypergraph with no polychromatic 3-coloring such that all of its h-heavy restricted subhypergraphs are 2-colorable. The construction uses complements of h-uniform hypergraphs on 3h-1 vertices. Existence for h ≥ 9 is established via a probabilistic argument, while the cases 4 ≤ h ≤ 8 are verified through exhaustive enumeration with reproducible code provided in the appendix. Combined with the h=3 case, this covers all h ≥ 3.

Significance. If correct, the result supplies explicit examples separating the absence of polychromatic 3-colorings from the 2-colorability of all h-heavy restrictions within hereditary families of (2h-1)-uniform hypergraphs. Credit is due for the parameter-free probabilistic existence proof (standard first-moment method with explicit hypotheses) for h ≥ 9 and for the fully reproducible machine enumeration (with source code and exact search parameters supplied) for 4 ≤ h ≤ 8; both routes directly verify the two required coloring properties.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the manuscript and for recommending acceptance. The report accurately captures the main result and the two proof methods used.

Circularity Check

0 steps flagged

Minor self-citation to h=3 case; new constructions independently verified

full rationale

The paper constructs (2h-1)-uniform hypergraphs for h>=4 as complements of h-uniform hypergraphs on 3h-1 vertices. Existence for h>=9 follows from a direct probabilistic argument showing positive probability that a random instance has no polychromatic 3-coloring while all h-heavy restrictions are 2-colorable. Cases 4<=h<=8 are settled by exhaustive enumeration with supplied reproducible code. The reference to the previously known h=3 case is purely contextual and does not enter the proofs or verifications for the new constructions. No derivation reduces to a fitted parameter, self-definition, or load-bearing self-citation chain; all central claims rest on external probabilistic counting and machine verification.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

No free parameters are fitted to data. The only axioms invoked are the standard rules of the probabilistic method and the correctness of exhaustive enumeration over a finite set; both are domain-standard in combinatorics.

axioms (2)

standard math The probabilistic method applies to the random selection of h-uniform hypergraphs on 3h-1 vertices
Invoked in the existence proof for h >= 9
domain assumption Exhaustive enumeration over all possible h-uniform hypergraphs on 3h-1 vertices is feasible and correctly implemented
Used for the computer verification of 4 <= h <= 8

pith-pipeline@v0.9.0 · 5443 in / 1585 out tokens · 43894 ms · 2026-05-08T02:23:29.477651+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

4 extracted references · 4 canonical work pages

[1]

Berge, Balanced matrices, Mathematical Programming 2, 19–31, 1972

C. Berge, Balanced matrices, Mathematical Programming 2, 19–31, 1972

work page 1972
[2]

P´ alv¨ olgyi, Note on polychromatic coloring of hereditary hypergraph families, Graphs and Combina- torics 40 (2024), article 131

D. P´ alv¨ olgyi, Note on polychromatic coloring of hereditary hypergraph families, Graphs and Combina- torics 40 (2024), article 131

work page 2024
[3]

J. Pach, D. P´ alv¨ olgyi, G. T´ oth, Survey on Decomposition of Multiple Coverings, in Geometry, Intu- itive, Discrete, and Convex (I. B´ ar´ any, K. J. B¨ or¨ oczky, G. Fejes T´ oth, J. Pach eds.), Bolyai Society Mathematical Studies 24, 219–257, Springer-Verlag, 2014

work page 2014
[4]

K2" return True,

G. Dam´ asdi, B. Keszegh, J. Pach, D. P´ alv¨ olgyi, G. T´ oth, Coloring Geometric Hypergraphs: A Survey, in: New Probes into Discrete and Convex Geometry, Bolyai Society Mathematical Studies 33, J. Pach and G. T´ oth (eds.), to appear; also available as arXiv:2512.09509, 2025,https://arxiv.org/abs/2512.09509. 7 Appendix A The remaining finite cases It re...

work page arXiv 2025

[1] [1]

Berge, Balanced matrices, Mathematical Programming 2, 19–31, 1972

C. Berge, Balanced matrices, Mathematical Programming 2, 19–31, 1972

work page 1972

[2] [2]

P´ alv¨ olgyi, Note on polychromatic coloring of hereditary hypergraph families, Graphs and Combina- torics 40 (2024), article 131

D. P´ alv¨ olgyi, Note on polychromatic coloring of hereditary hypergraph families, Graphs and Combina- torics 40 (2024), article 131

work page 2024

[3] [3]

J. Pach, D. P´ alv¨ olgyi, G. T´ oth, Survey on Decomposition of Multiple Coverings, in Geometry, Intu- itive, Discrete, and Convex (I. B´ ar´ any, K. J. B¨ or¨ oczky, G. Fejes T´ oth, J. Pach eds.), Bolyai Society Mathematical Studies 24, 219–257, Springer-Verlag, 2014

work page 2014

[4] [4]

K2" return True,

G. Dam´ asdi, B. Keszegh, J. Pach, D. P´ alv¨ olgyi, G. T´ oth, Coloring Geometric Hypergraphs: A Survey, in: New Probes into Discrete and Convex Geometry, Bolyai Society Mathematical Studies 33, J. Pach and G. T´ oth (eds.), to appear; also available as arXiv:2512.09509, 2025,https://arxiv.org/abs/2512.09509. 7 Appendix A The remaining finite cases It re...

work page arXiv 2025