LemmaStatement: 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 edge-union sparsity excludes short Berge cycles

Statement

Let $r \geq 2$ and $q \geq 3$ be integers. Suppose a finite $r$ -uniform hypergraph has $∣ ⋃ A ∣ \geq 1 + (r - 1) t$ whenever $A$ is a family of $t$ distinct hyperedges with $1 \leq t \leq q - 1$ . Then its Berge girth is at least $q$ .

Statement references

Berge cycles, incidence graphs and girth

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

A Berge cycle bounds the union of its hyperedges

The cardinality | A| of a finite set

Facts & Assumptions

[F1]

Berge cycles, incidence graphs and girth defines Berge girth, r-uniform hypergraphs and complete balanced r-partite r-graphs K⁽ʳ⁾_s,…,s defines uniformity, and A Berge cycle bounds the union of its hyperedges bounds the union of the edges of any Berge cycle. The cardinality | A| of a finite set defines the finite cardinalities used in both union-size bounds.

Proof

Given: The hypotheses of the statement.

Goal: Its asserted conclusion.

1.1F1given

If a Berge cycle had length $t < q$ , its integer length and the integrality of $q$ would give $2 \leq t \leq q - 1$ . Its distinct edge family would have union of size at most $(r - 1) t$ by the cycle-union bound.

2.1givenF1step 1.1∎

The assumed sparsity inequality applied to that family gives union size at least $1 + (r - 1) t$ , a contradiction. Thus no such cycle exists, which is exactly the asserted girth bound, including the acyclic case.

Depends on

Used by · 1

Finite high-girth hypergraphs with no weak k-colouring

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.