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.

Small independent sets obstruct weak colourings

Statement

Let $H = (V, E)$ be a finite hypergraph with $∣ V ∣ = n > 0$ , and let $k$ be a positive integer. Call $I \subseteq V$ independent if it contains no hyperedge. If every independent set has size at most a real number $a$ and $k a < n$ , then $H$ has no weak $k$ -colouring. In comparisons and arithmetic with reals, natural numbers denote their canonical images in $R$ .

Statement references

Weak hypergraph colourings with singleton boundary

The cardinality | A| of a finite set

A subset of a finite set is finite, with | B| ≤ | A|, and equality holds if and only if B = A

The sum rule: a finite disjoint union is finite with | A ∪ B| = | A| + | B| and |⋃_i ∈ I Aᵢ| = ∑_i ∈ I| Aᵢ|, and a sum over a finite index set splits along a partition

The reals form a totally ordered field

Laws of finite sums and products in ℕ, and ι(∑_k<n aₖ) = ∑_k<n ι(aₖ)

Laws of finite sums and finite products

Facts & Assumptions

[F1]

Weak hypergraph colourings with singleton boundary defines weak colourings as maps to $[k] = {1, \dots, k}$ with no monochromatic hyperedge; unused colours are allowed.

[F2]

The cardinality | A| of a finite set defines finite cardinality. By A subset of a finite set is finite, with | B| ≤ | A|, and equality holds if and only if B = A, every subset of finite $V$ is finite. Clause 2 of The sum rule: a finite disjoint union is finite with | A ∪ B| = | A| + | B| and |⋃_i ∈ I Aᵢ| = ∑_i ∈ I| Aᵢ|, and a sum over a finite index set splits along a partition gives the cardinality of a finite pairwise disjoint union as the sum of its members' cardinalities.

[F3]

The reals form a totally ordered field supplies the ordered real field. Clauses 6 and 7 of Laws of finite sums and products in ℕ, and ι(∑_k<n aₖ) = ∑_k<n ι(aₖ) identify a finite natural sum with the real sum of its canonical images and preserve natural order under this embedding.

[F4]

Clauses 2 and 4 of Laws of finite sums and finite products give $\sum_{j < k} a = k a$ for a constant real list and monotonicity of real finite sums under termwise inequalities.

Proof

Given: The hypotheses of the statement.

Goal: No weak $k$ -colouring exists.

1.1givenF1F2

If $c : V \to [k]$ were a weak $k$ -colouring, put $C_{j} = {v \in V : c (v) = j + 1}$ for $0 \leq j < k$ . These sets are pairwise disjoint, cover $V$ , and are finite subsets of $V$ . Each $C_{j}$ is independent, since a hyperedge contained in it would be monochromatic. Hence $∣ C_{j} ∣ \leq a$ for every $j < k$ , including unused colours.

2.1givenF2F3F4step 1.1algebra∎

The finite partition formula gives $n = \sum_{j < k}^{N} ∣ C_{j} ∣$ . Passing to canonical real images and applying the real finite-sum laws gives $n = \sum_{j < k}^{R} ∣ C_{j} ∣ \leq \sum_{j < k}^{R} a = k a < n$ . This contradicts the real order, so no weak $k$ -colouring exists.

Depends on

Used by · 1

Finite sparse uniform hypergraphs obstruct a prescribed palette

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.