Weak hypergraph colourings with singleton boundary

A finite hypergraph here is a pair $\mathcal{H}=(V,E)$ in which $V$ is a finite set and $E$ is a set of subsets of $V$; members of $V$ are vertices and members of $E$ are hyperedges. For a positive integer $k$, a weak $k$-colouring is a function $c:V\to [k]=\{1,\dots ,k\}$ such that no hyperedge is monochromatic: for every $e\in E$ there are $x,y\in e$ with $c(x)\mathrm{\ne }c(y)$. Colours need not all be used.

If a weak $k$-colouring exists for some positive integer $k$, the weak chromatic number ${\chi }_w(\mathcal{H})$ is the least such $k$. Otherwise no finite weak chromatic number is assigned. In particular, this convention assigns $1$ to the hypergraph with empty vertex set and no edges.

For an $r$-uniform hypergraph, every hyperedge has exactly $r$ vertices. If $r\ge 2$, its weak chromatic number is defined. If it has a singleton hyperedge, it has no weak $k$-colouring for any positive integer $k$. An empty hyperedge likewise prevents every weak colouring.

The given finite-colouring definition supplies the palette, functions and monochromatic subsets, including the convention that the empty set is monochromatic. Thus the displayed condition is exactly the absence of monochromatic hyperedges, and a singleton or empty hyperedge cannot satisfy it.

The admissible positive integers form a subset of the natural numbers by separation. If this subset is nonempty, the well-ordering principle gives a least element; that element is unique. For an $r$-uniform hypergraph with $r\ge 2$ and nonempty $V$, let $n=\mathrm{\mid }V\mathrm{\mid }$. The finite-cardinality supplier gives $n\mathrm{\ne }0$ and a bijection $b:V\to n$, where $n=\{0,\dots ,n-1\}$. Define $s_n(m)=\sigma (m)$ for $m\in n$.

For natural numbers $u,v$, the membership-order supplier gives $u\in v$ if and only if $u<v$, and $u\in \sigma (v)$ if and only if $u\le v$; discreteness gives $u<v$ if and only if $\sigma (u)\le v$. If $m\in n$, then $m<n$, hence $\sigma (m)\le n$ and $\sigma (m)\in \sigma (n)$. Also $\sigma (m)\mathrm{\ne }0$ by the Peano-system supplier. Thus $s_n(m)\in [n]=\{i\in \sigma (n):i\mathrm{\ne }0\}$. Conversely, if $i\in [n]$, then $i$ is a nonzero natural number and $i\le n$. The nonzero-successor supplier gives $i=\sigma (m)$ for a natural number $m$. Discreteness now gives $m<n$, so $m\in n$ and $s_n(m)=i$. This proves surjectivity onto $[n]$. Successor injectivity from the Peano-system supplier proves that $s_n$ is injective, so $s_n:n\to [n]$ is a bijection.

Define $c(v)=s_n(b(v))$ for $v\in V$. If $c(v)=c(w)$, injectivity of $s_n$ gives $b(v)=b(w)$, and injectivity of $b$ gives $v=w$. For any $i\in [n]$, surjectivity of $s_n$ gives $m\in n$ with $s_n(m)=i$, and surjectivity of $b$ gives $v\in V$ with $b(v)=m$, so $c(v)=i$. Thus $c:V\to [n]$ is a bijection. It assigns different colours to different vertices, so each hyperedge contains two differently coloured vertices. If $V$ is empty, there are no $r$-element hyperedges and the empty function is a weak $1$-colouring. Hence the admissible set is nonempty in both cases. For the explicitly edgeless empty-vertex hypergraph, $1$ is the least positive integer, so its weak chromatic number is $1$.

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

Unrestricted finite colourings and used palettes

The cardinality | A| of a finite set

The natural numbers ℕ (von Neumann)

The Axiom Schema of Separation: for each formula φ, ∀ p̄ ∀ x ∃ y ∀ z (z ∈ y ↔ (z ∈ x ∧ φ(z,p̄)))

The well-ordering principle

The von Neumann naturals form a Peano system

Every nonzero natural number is a successor

On ℕ the order is membership: m < n ⟺ m ∈ n

Discreteness: σ(n) is the immediate successor

Injection, surjection, bijection