TheoremStatement: AI-generatedProof: AI-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Finite high-girth hypergraphs with no weak k-colouring

Statement

For integers $r \geq 2$ , $q \geq 3$ and $k \geq 1$ , there exists a finite $r$ -uniform hypergraph of Berge girth at least $q$ that has no weak $k$ -colouring, equivalently with weak chromatic number at least $k + 1$ .

Statement references

Berge cycles, incidence graphs and girth

Weak hypergraph colourings with singleton boundary

r-uniform hypergraphs and complete balanced r-partite r-graphs K⁽ʳ⁾_s,…,s

Finite edge-union sparsity excludes short Berge cycles

Finite sparse uniform hypergraphs obstruct a prescribed palette

The finite graph boundary gives two-uniform witnesses

Facts & Assumptions

[F1]

Berge cycles, incidence graphs and girth, Weak hypergraph colourings with singleton boundary and r-uniform hypergraphs and complete balanced r-partite r-graphs K⁽ʳ⁾_s,…,s fix the girth, palette and uniformity conventions. Finite edge-union sparsity excludes short Berge cycles converts edge-union sparsity to Berge girth.

[F2]

Finite sparse uniform hypergraphs obstruct a prescribed palette supplies finite sparse witnesses for $r \geq 3$ . The finite graph boundary gives two-uniform witnesses supplies the finite $r = 2$ boundary.

Proof

Given: The hypotheses of the statement.

Goal: Its asserted conclusion.

1.1givenF1F2construct

If $r \geq 3$ , apply F2 with $s = q - 1$ . Its finite witness has no weak $k$ -colouring and satisfies the sparsity hypothesis in F1, so F1 gives Berge girth at least $q$ . If $r = 2$ , use the finite boundary witness in F2 directly. This proves existence throughout the stated range.

2.1F1step 1.1algebra∎

Because $r \geq 2$ , the weak chromatic number exists by F1. Absence of a weak $k$ -colouring is equivalent to its least admissible positive palette size being greater than $k$ : every colouring into a smaller palette also maps into $[k]$ . For integers this is exactly the lower bound $k + 1$ .

Depends on

Used by · 1

High-girth hypergraphs for Construction 1

Dependency tree · 2 levels

Each result is drawn at its shortest distance from this item. Arrows run from prerequisites to the items that use them; this item has a heavier outline. External source nodes link directly to the cited text. The view shows up to two dependency steps; open a prerequisite to continue.