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 sparse uniform hypergraphs obstruct a prescribed palette

Statement

For integers $r \geq 3$ , $s \geq 1$ and $k \geq 1$ there is a finite $r$ -uniform hypergraph with no weak $k$ -colouring such that every family of $t$ distinct edges, $1 \leq t \leq s$ , has union of size at least $1 + (r - 1) t$ .

Statement references

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

Weak hypergraph colourings with singleton boundary

The cardinality | A| of a finite set

Small independent sets obstruct weak colourings

Facts & Assumptions

[F1]

r-uniform hypergraphs and complete balanced r-partite r-graphs K⁽ʳ⁾_s,…,s and Weak hypergraph colourings with singleton boundary fix uniformity and weak colourings; The cardinality | A| of a finite set fixes finite size. Small independent sets obstruct weak colourings converts an independent-set bound to absence of a weak colouring.

[F2]

Erdős–Hajnal Theorem 13.3, with Definition 13.2, supplies the finite sparse set-systems and the independent-set bound stated in External input.

[F3]

The reals form a totally ordered field supplies ordered-real arithmetic. Clause 7 of Laws of finite sums and products in ℕ, and ι(∑_k<n aₖ) = ∑_k<n ι(aₖ) preserves and reflects natural-number order in the canonical real embedding. In real expressions, natural numbers denote these images.

[F4]

Real powers for positive bases, with the zero-base positive-exponent convention defines $x^{u} = \exp (u \log x)$ for $x > 0$ and real $u$ . The exponent, product, quotient, and iterated-power laws for positive real bases and real exponents supplies $x^{u + v} = x^{u} x^{v}$ . The natural logarithm as the inverse of the exponential function supplies $\log (\exp u) = u$ and $\exp (\log x) = x$ on their stated domains.

[F5]

Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm makes $\log$ strictly increasing on $(0, \infty)$ , and The exponential function is strictly increasing makes $\exp$ strictly increasing on $R$ . The exponential is positive and satisfies exp(-x)=1/exp(x) gives $\exp (u) > 0$ for all real $u$ .

[F6]

The Cauchy-sequence reals are Archimedean gives a canonical natural number larger than any prescribed real number.

Proof

Given: The hypotheses of the statement.

Goal: Its asserted conclusion.

1.1givenF2F3F4F5F6choose

Fix $r, s, k$ as given, and take $ε > 0$ and the integer $n_{0}$ from F2. By cofinality in F6, applied successively to the three real bounds, choose a natural number $n$ with $n > n_{0}$ , $n > 1$ and $n > \exp ((\log k) / ε)$ . Here $\log k$ is defined since $k \geq 1$ , and division by $ε$ is defined since $ε > 0$ . The order convention in F3 identifies this $n$ with a positive integer exceeding the imported threshold.

2.1F3F4F5step 1.1algebra

Applying the increasing logarithm to the positive quantities in the last inequality gives $\log n > \log (\exp ((\log k) / ε)) = (\log k) / ε$ . Multiplying by $ε > 0$ and applying the increasing exponential therefore gives $n^{ε} = \exp (ε \log n) > \exp (\log k) = k$ .

3.1F2F3F4F5step 1.1step 2.1algebra

Apply F2 at this integer $n$ . The resulting finite $r$ -uniform hypergraph has the stated edge-union inequalities, and every independent set has size at most $a = n^{1 - ε}$ . This is a positive real by F4 and F5. The power definition and inverse identity give $n^{1} = n$ , so the power law gives $a n^{ε} = n^{1 - ε} n^{ε} = n$ . Since $a > 0$ and $n^{ε} > k$ , ordered-field multiplication yields $k a < a n^{ε} = n$ .

4.1givenF1step 1.1step 3.1∎

The independent-set bound, $n > 0$ and $k a < n$ satisfy the hypotheses of the colouring-bound lemma in F1, so this hypergraph has no weak $k$ -colouring. Its edge-union inequalities from step 3.1 are unchanged, proving the statement.

External input

The following established result is used as an external premise, rather than claimed as a locally reconstructed proof: For each integer $r \geq 3$ and positive integer $s$ there are $ε > 0$ and $n_{0}$ such that for every integer $n > n_{0}$ there is an $r$ -uniform set-system on $n$ vertices which is $s$ -circuitless and has no independent subset of more than $n^{1 - ε}$ vertices. Here $s$ -circuitless means that every $t$ -edge subfamily, $1 \leq t \leq s$ , has union of size at least $1 + (r - 1) t$ .

Source notes

For this repair, read the cached full-text PDF introduction on PDF p.1 and Definition 13.2 and Theorem 13.3 on printed pp.94–95 (PDF pp.34–35); visually checked both printed pages, including the inequalities. The theorem is imported as stated, not proved locally. Only the beginning of its published proof on p.95 was read in this repair; no audit of the complete proof or reading of the whole paper is claimed. The finite $r = 2$ case and Corollary 13.4 are not used here.

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.

External dependencies

P. Erdős and A. Hajnal, On chromatic number of graphs and set-systems, Acta Mathematica Academiae Scientiarum Hungaricae 17 (1966), 61–99 · §13, Definition 13.2, printed p.94 (PDF p.34), and Theorem 13.3, printed p.95 (PDF p.35)

For each integer r≥3 and positive integer s there are ε>0 and n₀ such that for every integer n>n₀ there is an r-uniform set-system on n vertices which is s-circuitless and has no independent subset of more than n^(1−ε) vertices. Here s-circuitless means that every t-edge subfamily, 1≤t≤s, has union of size at least 1+(r−1)t.

Hypotheses: Fixed integers r≥3 and s≥1; n is a sufficiently large finite integer. Edges are distinct r-element subsets; independent means containing no whole edge.

Reading limits: For this repair, read the cached full-text PDF introduction on PDF p.1 and Definition 13.2 and Theorem 13.3 on printed pp.94–95 (PDF pp.34–35); visually checked both printed pages, including the inequalities. The theorem is imported as stated, not proved locally. Only the beginning of its published proof on p.95 was read in this repair; no audit of the complete proof or reading of the whole paper is claimed. The finite r=2 case and Corollary 13.4 are not used here.

Sources

P. Erdős and A. Hajnal, On chromatic number of graphs and set-systems, Acta Mathematica Academiae Scientiarum Hungaricae 17 (1966), 61–99 · §13, Definition 13.2, printed p.94 (PDF p.34), and Theorem 13.3, printed p.95 (PDF p.35)