Alphabeta Math
TheoremStatement: AI-adaptedProof: 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.

High-girth hypergraphs for Construction 1

PDF p. 1: Construction 1, final lines; PDF p. 2: Construction 1, first sentence, citation [3]; PDF p. 4: References [3]

Statement

Let H be a finite simple graph with at least one vertex, let q≥3 be an integer, and let k≥1 be an integer. There is a finite ∣V(H)∣-uniform hypergraph of Berge girth at least q with no weak k-colouring. If ∣V(H)∣≥2, its weak chromatic number is defined and at least k+1. If ∣V(H)∣=1, the witness can be chosen with a singleton hyperedge and therefore has no defined weak chromatic number under the stated convention.

Facts & Assumptions

[F1]

By Hypergraph terminology used in Construction 1, a finite r-uniform hypergraph has hyperedges of size r; a weak k-colouring assigns one of k colours to each vertex and gives every hyperedge two differently coloured vertices. Its Berge girth is the least length of a Berge cycle, or infinity if no such cycle exists. A Berge cycle uses at least two distinct hyperedges. The weak chromatic number is the least positive palette size admitting a weak colouring, and is undefined if no such palette exists.

[F2]

Finite high-girth hypergraphs with no weak k-colouring supplies, for integers r≥2, q≥3 and k≥1, a finite r-uniform hypergraph of Berge girth at least q with no weak k-colouring and weak chromatic number at least k+1.

Proof

Given: A graph H and integers q,k satisfying the statement's hypotheses.

Goal: Construct the asserted hypergraph and establish the stated chromatic conclusions.

1.1givenF2assume-case

Put r=∣V(H)∣. If r≥2, apply F2 with these values of r,q,k. The resulting hypergraph has all the required properties, including the numerical chromatic bound.

1.2givenF1constructassume-case

If r=1, take the hypergraph with vertex set {v} and the single hyperedge {v}. It is finite and 1-uniform. It has no Berge cycle because a cycle requires at least two distinct hyperedges, so its girth is infinity and is at least q. Its singleton hyperedge cannot contain two differently coloured vertices, so no weak colouring exists for any positive palette; its weak chromatic number is therefore undefined.

2.1F1step 1.1step 1.2cases-exhaustive∎

The graph convention gives r≥1, so the two cases establish the conclusion.

Extraction notes

The article states the existence assertion using a chromatic-number inequality and attributes it to Erdős–Hajnal. For uniformity one, this item records the no-weak-colouring property used in Construction 1; the frozen finite-chromatic-number convention does not assign a numerical value to the singleton witness. The article passage does not explicitly settle that convention.

Depends on

Used by · 3

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.

Sources