# Minimal vertex covers in infinite hypergraphs

Tamás Csernák  Eötvös University of Budapest, Hungary<EMAIL_ADDRESS>and
Lajos Soukup  Alfréd Rényi Institute of Mathematics, Eötvös Loránd Research
Network, Budapest, Hungary<EMAIL_ADDRESS>
###### Abstract.

If $A$ is a set and $S$ is a set of cardinals, write

${[A]}^{S}=\\{B\subset A:|B|\in S\\}.$

In this paper a hypergraph will be identified with the family of its edges. A
hypergraph $\mathcal{E}$ possesses property $\operatorname{C}(k,\rho)$ iff
$|\bigcap\mathcal{E}^{\prime}|<{\rho}$ for each
$\mathcal{E}^{\prime}\in{[\mathcal{E}]}^{k}$.

If ${\lambda}$ and ${\rho}$ are cardinals, $S$ is a set of cardinals,
$k\in{\omega}$, then we write

$\mathbf{M}\mathbb{(}{\lambda},{S},k,{\mu})\to\mathbf{MinVC}$

iff every hypergraph $\mathcal{E}\subset{[{\lambda}]}^{S}$ possessing property
$\operatorname{C}(k,{\rho})$ has a minimal vertex cover. If $S=\\{\kappa\\}$,
then we simply write
$\mathbf{M}({{\lambda}},{\kappa},{k},{{\mu}})\to\mathbf{MinVC}$ for
$\mathbf{M}({{\lambda}},\\{{\kappa}\\},{k},{{\mu}})\to\mathbf{MinVC}$.

A set $S$ of cardinals is nowhere stationary iff $S\cap{\alpha}$ is not
stationary in ${\alpha}$ for any ordinal ${\alpha}$ with
$cf({\alpha})>{\omega}$. In particular, countable sets of cardinals, and sets
of successor cardinals are nowhere stationary.

In this paper we prove:

  1. (1)

$\mathbf{M}\mathbb{(}{\lambda},{S},2,k)\to\mathbf{MinVC}$ for each nowhere
stationary set $S$ of cardinals and $k<{\omega}\leq{\lambda}$ and
$k\in{\omega}$,

  2. (2)

$\mathbf{M}\mathbb{(}{\lambda},{{\kappa}},2,{\omega})\to\mathbf{MinVC}$ for
each ${\omega}_{2}\leq{\kappa}\leq{\lambda}$ provided $GCH$ holds,

  3. (3)

$\mathbf{M}\mathbb{(}{\lambda},{{\kappa}},2,{\rho})\to\mathbf{MinVC}$ provided
${\rho}<\beth_{\omega}\leq{\kappa}\leq{\lambda}$,

  4. (4)

$\mathbf{M}\mathbb{(}{\lambda},{{\omega}},r,k)\to\mathbf{MinVC}$ provided
${\omega}\leq{\lambda}$ and $k,r\in{\omega}$,

  5. (5)

$\mathbf{M}\mathbb{(}{\lambda},{{\omega}_{1}},3,k)\to\mathbf{MinVC}$ provided
${\omega}_{1}\leq{\lambda}$ and $k\in{\omega}$.

###### Key words and phrases:

infinite hypergraph, vertex cover, minimal vertex cover, Shelah’s revised GCH,
almost disjoint,

###### 2010 Mathematics Subject Classification:

03E05, 05C63, 05C65, 05C69

The preparation of this paper was partially supported by OTKA grants K 129211

##  1\. Introduction

A hypergraph is a pair of sets $\left\langle V,\mathcal{E}\right\rangle$ such
that the elements of $\mathcal{E}$ are non-empty subsets of $V$. We are
interested in hypergraphs $\left\langle V,\mathcal{E}\right\rangle$ whose
edges cover $V$ in the sense that $V=\cup\mathcal{E}$. To shorten notations,
in this case the hypergraph will be identified with the family $\mathcal{E}$
of its edges.

Given a hypergraph $\mathcal{E}$ a vertex set $Y\subset\cup\mathcal{E}$ is a
vertex cover of $\mathcal{E}$ iff $Y\cap E\neq\emptyset$ for each
$E\in\mathcal{E}$. We say that a vertex cover $Z$ is a minimal vertex cover of
$\mathcal{E}$ iff no proper subset of $Z$ is a vertex cover of $\mathcal{E}$.

Using the terminology of Erdős and Hajnal [2] we say that a hypergraph
$\mathcal{E}$ possesses property $\operatorname{C}(k,\rho)$ iff
$|\bigcap\mathcal{E}^{\prime}|<{\rho}$ for each
$\mathcal{E}^{\prime}\in{[\mathcal{E}]}^{k}$.

Dominic van der Zypen [1, 9] raised the following question: Assume that
$r\in{\omega}$. Does every hypergraphs which possesses property
$\operatorname{C}(2,r)$ have a minimal vertex cover?

In [6] Komjáth gave some partial answers. To formulate them precisely we
introduce some more notations.

We define the edge cardinality spectrum of a hypergraph $\mathcal{E}$,
$\|\mathcal{E}\|$, as the cardinalities of the edges of the hypergraph:

$\|\mathcal{E}\|=\\{|E|:E\in\mathcal{E}\\}.$

If $A$ is a set and $S$ is a set of cardinals, write

${[A]}^{S}=\\{B\subset A:|B|\in S\\}.$

If $S=\\{{\kappa}\\}$, then we will use the standard notation
${[A]}^{{\kappa}}$ instead of ${[A]}^{\\{{\kappa}\\}}$.

If ${\lambda}$ and ${\rho}$ are cardinals, $S$ is a set of cardinals,
$k\in{\omega}$, then we write

$\mathbf{M}\mathbb{(}{\lambda},{S},k,{\rho})\to\mathbf{MinVC}$

iff every hypergraph $\mathcal{E}\subset{[{\lambda}]}^{S}$ possessing property
$\operatorname{C}(k,{\rho})$ has a minimal vertex cover.

Komjath ([6, Corollary 8]) proved that

  1. (k1)

$\mathbf{M}\mathbb{(}{\lambda},{{\omega}\cup\\{{\kappa}\\}},2,k)\to\mathbf{MinVC}$
for each ${\omega}\leq{\kappa}\leq{\lambda}$.

In this paper we prove a strengthening of this result. To formulate our
theorem we need to introduce the following notion. A set $S$ of ordinals is
nowhere stationary iff $S\cap{\alpha}$ is not stationary in ${\alpha}$ for any
ordinal ${\alpha}$ with $cf({\alpha})>{\omega}$. In particular, countable sets
of cardinals, and sets of successor cardinals are nowhere stationary. In
Section 3 we prove:

######  Theorem 1.1.

$\mathbf{M}\mathbb{(}{\lambda},{S},2,r)\to\mathbf{MinVC}$ for each cardinal
${\lambda}$ and $r\in{\omega}$ provided that $S$ is a nowhere stationary set
of cardinals.

Komjáth ([6, Theorems 16 and 17]) also proved

  1. (k2)

$\mathbf{M}\mathbb{(}{\lambda},{{\omega}\cup\\{{\kappa}\\}},2,{\omega})\to\mathbf{MinVC}$
for each ${\omega}_{1}\leq{\kappa}\leq{\lambda}$ provided $V=L$,

  2. (k3)

GCH does not imply that
$\mathbf{M}\mathbb{(}\aleph_{{\omega}+1},{{\omega}_{1}},2,{\omega})\to\mathbf{MinVC}$.

In Section 2 we show that the assumption $V=L$ can be relaxed to $GCH$
provided we strengthen the assumption ${\kappa}\geq{\omega}_{1}$ to
${\kappa}\geq{\omega}_{2}$.

######  Theorem 1.2.

If GCH holds, then
$\mathbf{M}\mathbb{(}{\lambda},{{\omega}\cup\\{{\kappa}\\}},2,{\omega})\to\mathbf{MinVC}$
for each ${\omega}_{2}\leq{\kappa}\leq{\lambda}$.

One can conjecture that one can not obtain positive ZFC theorems for
hypergraphs which possesses property $\operatorname{C}(2,{\rho})$ for some
${\rho}\geq{\omega}$. But this is not true: in Section 2, using Shelah’s
Revised CGH theorem, we prove in ZFC:

######  Theorem 1.3.

$\mathbf{M}\mathbb{(}{\lambda},{{\omega}\cup\\{{\kappa}\\}},2,\rho)\to\mathbf{MinVC}$
for each ${\rho}<\beth_{\omega}\leq{\kappa}\leq{\lambda}$.

In Section 4 we consider hypergraphs possessing property
$\operatorname{C}(k,r)$ for $3\leq k<{\omega}$, and we prove the following
results.

######  Theorem 1.4.

$\mathbf{M}\mathbb{(}{\lambda},{{\omega}},r,k)\to\mathbf{MinVC}$ provided
${\omega}\leq{\lambda}$ and $k,r\in{\omega}$

######  Theorem 1.5.

$\mathbf{M}\mathbb{(}{\lambda},{{\omega}_{1}},3,k)\to\mathbf{MinVC}$ provided
${\omega}_{1}\leq{\lambda}$ and $k\in{\omega}$.

### Notations and basic observations.

We use the standard notation of infinite combinatorics.

If $\mathcal{F}\subset\mathcal{P}(X)$, $x\in X$ and $Y\subset X$, write

$\mathcal{F}(x)=\\{F\in\mathcal{F}:x\in F\\},$
$\mathcal{F}[Y]=\\{F\in\mathcal{F}:F\cap Y\neq\emptyset\\}\text{ and
}\mathcal{F}[-Y]=\\{F\in\mathcal{F}:F\cap Y=\emptyset\\},$

and

$\mathcal{F}\restriction Y=\\{F\cap Y:F\in\mathcal{F}[Y]\\}\text{ and
}\mathcal{F}\sqcap Y=\mathcal{F}\cap\mathcal{P}(Y).$

Observe that $\emptyset\notin\mathcal{F}\restriction Y$.

######  Observation 1.6.

Assume that $\mathcal{E}$ is a hypergraph and $Y$ is a vertex cover of
$\mathcal{E}$. Then $Y$ is a minimal vertex cover of $\mathcal{E}$ iff there
is a function $w:Y\to\mathcal{E}$ such that $w(y)\cap Y=\\{y\\}$ for each
$y\in Y$.

We will say that $w$ is a witnessing function, or that $w$ witnesses the
minimality of $Y$.

If $\left\langle X_{\alpha}:{\alpha}<{\delta}\right\rangle$ is a sequence of
sets, and ${\beta}<{\delta}$, write
$X_{<{\beta}}=\bigcup_{{\alpha}<{\beta}}X_{\alpha}$. We define
$X_{\leq{\beta}}$, $X_{>{\beta}}$, etc. analogously.

##  2\. Maximizing well ordering

Given a hypergraph $\mathcal{E}$ a well-ordering $\preceq$ of the vertex set
of $\mathcal{E}$ is called a maximizing well-ordering iff every edge
$E\in\mathcal{E}$ has a $\preceq$-maximal element.

If ${\lambda}$ and ${\rho}$ are cardinals, $S$ is a set of cardinals,
$k\in{\omega}$, then we write

$\mathbf{M}\mathbb{(}{\lambda},{S},k,\rho)\to\mathbf{MaxWO}$

iff every hypergraph $\mathcal{E}\subset{[{\lambda}]}^{S}$ possessing property
$\operatorname{C}(k,{\rho})$ has a maximizing well-ordering.

In [6] Komjáth observed that Klimo [5, Theorem 5] practically proved that if a
hypergraph has a maximizing well order then it has a minimal vertex cover,
i.e.

$\mathbf{MaxWO}\to\mathbf{MinVC}$

In [6, Theorem 7] Komjáth actually proved that
$\mathbf{M}\mathbb{(}{\lambda},{{\kappa}},2,k)\to\mathbf{MaxWO}$ for each
${\omega}\leq{\kappa}\leq{\lambda}$. So if
$\mathcal{E}\subset{[{\lambda}]}^{{\omega}\cup\\{{\kappa}\\}}$, then
$\mathcal{E}\cap{[{\lambda}]}^{{\kappa}}$ has a maximizing well-order
$\preceq$, which is also a maximizing well-order for $\mathcal{E}$ because
non-empty finite sets have maximal elements in any ordering.

Using the same approach to yield Theorems 1.2 and 1.3 it is enough to prove
the following two theorems.

######  Theorem 2.1.

If GCH holds, then
$\mathbf{M}\mathbb{(}{\lambda},{{\kappa}},2,{\omega})\to\mathbf{MaxWO}$ for
each ${\omega}_{2}\leq{\kappa}\leq{\lambda}$.

######  Theorem 2.2.

$\mathbf{M}\mathbb{(}{\lambda},{{\kappa}},2,\rho)\to\mathbf{MaxWO}$ for each
${\rho}<\beth_{\omega}\leq{\kappa}\leq{\lambda}$.

First we need a general stepping up method.

######  Definition 2.3.

Let $\mathcal{A}$ be a hypergraph, ${\lambda}=|\bigcup A|$. We say that a
continuous, increasing sequence $\left\langle
G_{\alpha}:{\alpha}<cf({\lambda})\right\rangle\subset{[\bigcup\mathcal{A}]}^{<{\lambda}}$
is a good cut of $\mathcal{A}$ iff

  1. (i)

$G_{0}=\emptyset$ and
$\bigcup_{{\alpha}<cf({\lambda})}G_{\alpha}=\bigcup\mathcal{A}$,

  2. (ii)

$\forall A\in\mathcal{A}$ $\exists{\alpha}<cf({\lambda})$ $A\subset
G_{{\alpha}+1}$ and $|G_{\alpha}\cap A|<|A|$.

######  Definition 2.4.

Given hypergraphs $\mathcal{A}$ and $\mathcal{B}$ we say that $\mathcal{B}$ is
a shrink of $\mathcal{A}$ and we write $\mathcal{B}\ll\mathcal{A}$ iff
$\forall B\in\mathcal{B}$ $\exists A\in\mathcal{A}$ such that $B\subset A$ and
$|A\setminus B|<|A|$.

######  Theorem 2.5.

Let ${\kappa}$ be an infinite cardinal. Assume that $\mathbb{A}$ is a
collection of hypergraphs with the following properties:

  1. (a)

If $\mathcal{A}\in\mathbb{A}$ and $\mathcal{B}\ll\mathcal{A}$, then
$\mathcal{B}\in\mathbb{A}$.

  2. (b)

if $\mathcal{A}\in\mathbb{A}$, and ${\lambda}=|\bigcup\mathcal{A}|>{\kappa}$
then $\mathcal{A}$ has a good cut.

(1) If

  1. (c)

every $\mathcal{A}\in\mathbb{A}$ with $|\bigcup\mathcal{A}|\leq{\kappa}$ has a
minimal vertex cover,

then every $\mathcal{A}\in\mathbb{A}$ has a minimal vertex cover.

(2) If

  1. (c’)

every $\mathcal{A}\in\mathbb{A}$ with $|\bigcup\mathcal{A}|\leq{\kappa}$ has a
maximizing well order,

then every $\mathcal{A}\in\mathbb{A}$ has a maximizing well-order.

###### Proof.

(1) By induction on ${\lambda}=|\bigcup\mathcal{A}|$.

If ${\lambda}={\kappa}$, then (c) implies the statement.

Assume that ${\lambda}>{\kappa}$. Let $\left\langle
G_{\alpha}:{\alpha}<cf({\lambda})\right\rangle$ be a good cut of $\mathcal{A}$
by (b).

By transfinite induction on ${\alpha}<{\lambda}$ we will define
$Y_{\alpha}\subset G_{{\alpha}+1}\setminus G_{\alpha}$ and a function
$w_{\alpha}:Y_{\alpha}\to\mathcal{A}\sqcap G_{{\alpha}+1}$ such that
$Y_{\leq{\alpha}}(=\bigcup_{{\alpha}^{\prime}\leq{\alpha}}Y_{{\alpha}^{\prime}})$
is a minimal vertex cover of $\mathcal{A}\sqcap G_{{\alpha}+1}$ witnessed by
$w_{\leq\alpha}$, as follows.

Assume that $\left\langle Y_{\zeta}:{\zeta}<{\alpha}\right\rangle$ and
$\left\langle w_{\zeta}:{\zeta}<{\alpha}\right\rangle$ are defined. Let

$\mathcal{A}_{\alpha}=\big{(}\mathcal{A}[-Y_{<{\alpha}}]\sqcap
G_{{\alpha}+1}\big{)}\restriction(G_{{\alpha}+1}\setminus G_{\alpha}).$

Then $\mathcal{A}_{\alpha}\ll\mathcal{A}$, so
$\mathcal{A}_{\alpha}\in\mathbb{A}$ by (a). Since
$|\bigcup\mathcal{A}_{\alpha}|\leq|G_{{\alpha}+1}|<{\lambda}$, by the
inductive assumption $\mathcal{A}_{\alpha}$ has a minimal vertex cover
$Y_{\alpha}$ witnessed by a function $w_{\alpha}$.

After the inductive construction put
$Y=\bigcup_{{\alpha}<cf({\lambda})}Y_{\alpha}$ and
$w=\bigcup_{{\alpha}<cf({\lambda})}w_{\alpha}$. Then $Y$ is a minimal vertex
cover of $\mathcal{A}$ witnessed by $w$.

(2) By induction on ${\lambda}=|\bigcup\mathcal{A}|$.

If ${\lambda}={\kappa}$, then (c’) implies the statement.

Assume that ${\lambda}>{\kappa}$. Let $\left\langle
G_{\alpha}:{\alpha}<cf({\lambda})\right\rangle$ be a good cut of $\mathcal{A}$
by (b).

For each ${\alpha}<{\kappa}$ consider the family

$\mathcal{A}_{\alpha}=\\{A\setminus G_{\alpha}:A\in\mathcal{A},A\subset
G_{{\alpha}+1},|A\cap G_{\alpha}|<|A|\\}.$

Then $\mathcal{A}_{\alpha}\ll\mathcal{A}$ and so
$\mathcal{A}_{\alpha}\in\mathbb{A}$ by (a).

Since $|\bigcup\mathcal{A}_{\alpha}|\leq|G_{{\alpha}+1}|<{\lambda}$, by the
inductive assumption, the family $\mathcal{A}_{\alpha}$ has a maximizing well
order $\preceq_{\alpha}$. We can assume that $\preceq_{\alpha}$ is a well-
order of $G_{{\alpha}+1}\setminus G_{\alpha}$. Define the well ordering
$\preceq$ of $\bigcup\mathcal{A}$ as follows:

  1. (1)

if ${\alpha}<{\beta}<{\lambda}$, then

$(G_{{\alpha}+1}\setminus G_{\alpha})\prec(G_{{\beta}+1}\setminus G_{\beta}),$

  2. (2)

$\preceq\restriction(G_{{\alpha}+1}\setminus G_{\alpha})=\preceq_{\alpha}$.

Then $\preceq$ is a maximizing well-order of $\mathcal{A}$. ∎

###### Proof of Theorem 2.1.

We want to apply Theorem 2.5(2). So let

$\mathbb{A}=\\{\mathcal{A}:\exists{\lambda}\geq{\kappa}\geq{\omega}_{2}\
(\mathcal{A}\subset{[{\lambda}]}^{{\kappa}}\text{ has property
$\operatorname{C}(2,{\omega})$})\\}.$

We should verify properties 2.5(a,b,c’)

(a) is trivial by definition.

To show (b) assume that $\mathcal{A}\in\mathbb{A}$,
${\lambda}=\bigcup\mathcal{A}>{\kappa}$. Next we should recall a lemma from
[3]:

######  Lemma 2.6 ([3, Lemma 8.5]).

Assume that $\lambda\geq\omega_{2}$ and ${\mu}^{\omega}={\mu}^{+}$ holds for
each ${\mu}<{\lambda}$ with $cf({\mu})={\omega}$. If $\mathcal{A}$ is an
hypergraph with property $\operatorname{C}(2,{\omega})$ and $X$ is any set
with $\,|X|<\lambda$, then

$\big{|}\\{A\in\mathcal{A}:|X\cap A|>\omega\\}\big{|}\leq|X|.$

Next, by transfinite recursion on ${\zeta}<{\lambda}$, define a a continuous
sequence of subsets of ${\lambda}$, $\left\langle
M_{\zeta}:{\zeta}<{\lambda}\right\rangle$, such that

  1. (1)

$M_{0}=\emptyset$ and ${\zeta}\subset
M_{\zeta}\in{[{\lambda}]}^{{\kappa}+|{\zeta}|}$ for ${\zeta}>0$,

  2. (2)

if $A\in\mathcal{A}$ and $|A\cap M_{\zeta}|>{\omega}$, then $A\subset
M_{{\zeta}+1}$.

By Lemma 2.6, if $M_{\zeta}$ is given, we can choose a suitable
$M_{{\zeta}+1}$.

Let $\left\langle{\lambda}_{\alpha}:{\alpha}<cf({\lambda})\right\rangle$ be a
strictly increasing cofinal sequence of limit ordinals in ${\lambda}$.

Let $G_{\alpha}=M_{{\lambda}_{\alpha}}$ for ${\alpha}<cf({\lambda})$ of
$\mathcal{A}$. We claim that $\left\langle
G_{\alpha}:{\alpha}<cf({\lambda})\right\rangle$ is a good cut.

Let $A\in\mathcal{A}$ be arbitrary. Since $|A|\geq{\omega}_{2}$, there is
${\zeta}<{\lambda}$ such that $|A\cap M_{\zeta}|>{\omega}$, and so $A\subset
M_{{\zeta}+1}$. Thus we can define

${\alpha}=\min\\{{\alpha}^{\prime}<{\lambda}:|G_{{\alpha}^{\prime}}\cap
A|\geq{\omega}_{2}\\}.$

Since $G_{\alpha}=M_{{\lambda}_{\alpha}}$ and ${\lambda}_{\alpha}$ is a limit
ordinal, there is ${\xi}<{\lambda}_{\alpha}$ with $|A\cap M_{\xi}|>{\omega}$,
and so $A\subset M_{{\xi}+1}\subset G_{\alpha}$.

If ${\alpha}$ is a limit ordinal then there is ${\beta}<{\alpha}$ with
${\xi}<{\lambda}_{\beta}$, and so $A\subset M_{{\xi}+1}\subset G_{\beta}$
which contradicts the minimality of ${\alpha}$.

Thus ${\alpha}={\beta}+1$ for some ${\beta}$, and so $A\subset G_{{\beta}+1}$
and $|G_{\beta}\cap A|\leq{\omega}_{1}<{\kappa}$.

Se we checked property 2.5(b).

(c) is straightforward: if $\mathcal{A}\subset{[{\kappa}]}^{{\kappa}}$ is
$\operatorname{C}(2,\omega)$, then $|\mathcal{A}|\leq{\kappa}$ by Lemma 2.6,
so we can write $\mathcal{A}=\\{A_{\zeta}:{\zeta}<{\xi}\\}$. Now let $\preceq$
is a well ordering of ${\kappa}$ such that writing
$A_{\zeta}^{\prime}=A_{\zeta}\setminus A_{<{\zeta}}$ we have

  1. (1)

$A^{\prime}_{\xi}\prec A^{\prime}_{\eta}$ for ${\xi}<{\eta}<{\lambda}$,

  2. (2)

the order type of $A^{\prime}_{\eta}$ is ${\kappa}+1$, i.e.
$A^{\prime}_{\eta}$ has a $\preceq$-maximal element.

Then $\preceq$ maximizes $\mathcal{A}$.

Thus we verified condition 2.5(2)(b) and so we can apply Theorem 2.5(2) to
show that every $\mathcal{A}\in\mathbb{A}$ has a maximizing well-ordering. ∎

###### Proof of Theorem 2.2.

We want to apply Theorem 2.5(2). So let

$\mathbb{A}=\\{\mathcal{A}:\exists{\lambda}\geq{\kappa}\geq{\beth_{\omega}}>{\rho}\
(\mathcal{A}\subset{[{\lambda}]}^{{\kappa}}\text{ has property
$\operatorname{C}(2,{\rho})$})\\}.$

We should verify properties 2.5(a,b,c’).

(a) is trivial by definition.

To show (b) assume that $\mathcal{A}\in\mathbb{A}$,
${\lambda}=\bigcup\mathcal{A}>{\kappa}$. Next we should recall a lemma from
[4] which based on the following celebrated result of Shelah.

######  Shelah’s Revised CGH Theorem ([8, Theorem 0.1]).

If ${\mu}\geq{\beth_{\omega}}$, then ${\mu}^{[{\nu}]}={\mu}$ for each large
enough regular cardinal ${\nu}<{\beth_{\omega}}$.

######  Lemma 2.7 ([4, Lemma 3.3]).

If ${\lambda}\geq{\beth_{\omega}}>{\mu}$, and
$\\{A_{\alpha}:{\alpha}<\tau\\}\subset\bigl{[}{\lambda}\bigr{]}^{{\beth_{\omega}}}$
is a hypergraph which property $\operatorname{C}(2,{\mu})$, then
$\tau\leq{\lambda}$, and there is an increasing, continuous sequence
$\left\langle
G_{\zeta}:{\zeta}<cf({\lambda})\right\rangle\subset\bigl{[}{\lambda}\bigr{]}^{<{\lambda}}$
such that

$\forall{\zeta}<cf({\lambda})$ $\forall{\alpha}\in G_{\zeta+1}\setminus
G_{\zeta}$ $(\ |A_{\alpha}\cap G_{\zeta}|<{\beth_{\omega}}$ and
$A_{\alpha}\subset G_{{\zeta}+1}\ )$. (2.1)

This Lemma just claims Claims 2.5(b).

(c) is straightforward: if $\mathcal{A}\subset{[{\kappa}]}^{{\kappa}}$ is
$\operatorname{C}(2,\omega)$, then $|\mathcal{A}|\leq{\kappa}$ by Lemma 2.7,
so we can write $\mathcal{A}=\\{A_{\zeta}:{\zeta}<{\xi}\\}$. Now repeat an
argument from the proof of the previous theorem: let $\preceq$ is a well
ordering of ${\kappa}$ such that writing
$A_{\zeta}^{\prime}=A_{\zeta}\setminus A_{<{\zeta}}$ we have

  1. (1)

$A^{\prime}_{\xi}\prec A^{\prime}_{\eta}$ for ${\xi}<{\eta}<{\lambda}$

  2. (2)

the order type of $A^{\prime}_{\eta}$ is ${\kappa}+1$, i.e.
$A^{\prime}_{\eta}$ has a $\preceq$-maximal element.

Then $\preceq$ maximizes $\mathcal{A}$.

Thus we verified condition 2.5(2)(b) and so we can apply Theorem 2.5(2) to
show that every $\mathcal{A}\in\mathbb{A}$ has a maximizing well-ordering.

∎

##  3\. Inhomogeneous families

In [6, Theorem 6] Komjáth proved that
$\mathbf{M}\mathbb{(}{\lambda},{{\kappa}},2,k)\to\mathbf{MaxWO}$, and so
$\mathbf{M}\mathbb{(}{\lambda},{{\omega}\cup\\{{\kappa}\\}},2,k)\to\mathbf{MinVC}$
for each ${\omega}\leq{\kappa}\leq{\lambda}$.

In this section we want to prove Theorem 1.1 which relaxes the requirements
concerning the edge cardinality spectrum of the hypergraphs.

###### Proof of Theorem 1.1.

Let $r$ be a fixed natural number.

For any infinite cardinal ${\kappa}$ let $\Delta(\kappa)$ be the following
statement:

  * if $S$ is a nowhere stationary set of cardinals with $\sup S\leq{\kappa}$ then every hypergraph $\mathcal{A}\subset{[{\kappa}]}^{S}$ possessing property $C(2,r)$ has a minimal vertex cover.

We prove $\Delta(\kappa)$ for each infinite ${\kappa}$ by transfinite
induction on ${\kappa}$.

For ${\kappa}={\omega}$,
$\mathcal{A}\subset{[{\omega}]}^{<{\omega}}\cup{[{\omega}]}^{\omega}$, so
$\Delta(\omega)$ is just a special case of [6, Corollary 9].

So assume that ${\kappa}>{\omega}$ and $\Delta(\mu)$ holds for each infinite
cardinal ${\mu}<{\kappa}$.

To prove $\Delta(\kappa)$ let $S$ be a nowhere stationary set of cardinals
with $\sup S\leq{\kappa}$, and let $\mathcal{A}\subset{[{\kappa}]}^{S}$ be a
hypergraph with property $\operatorname{C}(2,r)$.

Let $\left\langle{\kappa}_{\alpha}:{\alpha}<{\delta}\right\rangle$. be the
strictly increasing enumeration of $S\cap{\kappa}$.

Write $\mathcal{B}=\mathcal{A}\cap{[{\kappa}]}^{<{\kappa}}$ and
$\mathcal{C}=\mathcal{A}\cap{[{\kappa}]}^{{\kappa}}$. Adding pairwise disjoint
"dummy" sets to $\mathcal{A}$ we can assume that $|\mathcal{C}|={\kappa}$. Let
$\left\langle C_{\xi}:{\xi}<{\kappa}\right\rangle$ be an enumeration of
$\mathcal{C}$.

Step 1. Construction of a chain of cardinals.

We define an increasing sequence of cardinals
$\left\langle{\mu}_{\zeta}:{\zeta}<{\kappa}\right\rangle$ as follows.

Let ${\mu}_{0}=0$.

If ${\kappa}={\mu}^{+}$ then let ${\mu}_{\zeta}={\mu}$ for each
$1\leq{\zeta}<{\kappa}$.

If ${\kappa}$ is an uncountable limit cardinal, let ${\rho}=cf({\delta}$.

Since $S$ is not stationary in ${\kappa}$, there is a a strictly increasing
continuous sequence of infinite cardinals,
$\left\langle{\nu}_{\alpha}:{\alpha}<{\rho}\right\rangle$, which is cofinal in
${\kappa}$, and ${\nu}_{\alpha}\notin S$ for each limit ordinal
${\alpha}<{\rho}$. For $1\leq{\zeta}<{\kappa}$ let

${\mu}_{\zeta}=\min\\{{\nu}_{\alpha}:{\nu}_{\alpha}\geq{\zeta}\\}.$

Observe that the sequence
$\left\langle{\mu}_{\zeta}:{\zeta}<{\kappa}\right\rangle$ is increasing and
continuous.

Step 2. The inductive construction.

By transfinite recursion on ${\zeta}<{\kappa}$ we will define an increasing,
continuous sequence $\left\langle M_{\zeta}:{\zeta}<{\kappa}\right\rangle$ of
subsets of ${\kappa}$, a sequence $\left\langle
Y_{\zeta}:{\zeta}<{\omega}\right\rangle$ of pairwise disjoint subsets of
${\kappa}$, and a sequence $\left\langle
w_{\zeta}:{\zeta}<{\kappa}\right\rangle$ of functions such that

  1. (1)ζ

${\zeta}\subset M_{\zeta}\in{[{\kappa}]}^{{\mu}_{\zeta}}$,

  2. (2)ζ

if $B\in\mathcal{B}$, $|B\cap M_{\zeta}|\geq r$ and $|B|\leq|M_{\zeta}|$ then
$B\subset M_{\zeta}$,

  3. (3)ζ

If ${\zeta}=0$ or ${\zeta}$ is a limit ordinal, then $M_{\zeta}=M_{<{\zeta}}$
and $Y_{\zeta}=w_{\zeta}=\emptyset$,

  4. (4)ζ

if ${\zeta}={\eta}+1$, then $Y_{\zeta}\subset(M_{{\zeta}}\setminus
M_{\eta})\cap{\kappa}$ and

$w_{\zeta}:Y_{\zeta}\to\big{(}\mathcal{B}[-Y_{\leq{\eta}}]\sqcap
M_{\zeta}\big{)}\cup\\{C_{\eta}\\},$

  5. (5)ζ

$\mathcal{A}[Y_{\leq{\zeta}}]\supset(\mathcal{B}\sqcap\mathcal{M}_{\zeta})\cup\\{C_{\xi}:{\xi}<{\zeta}\\}$,

  6. (6)ζ

$w_{\leq{\zeta}}(y)\cap Y_{\leq{\zeta}}=\\{y\\}$ for each $y\in
Y_{\leq{\zeta}}$,

  7. (7)ζ

if $C_{\eta}=w_{\zeta}(y)$ for some $y\in Y_{\zeta}$, then

$C_{\eta}\cap\bigcup((\mathcal{B}[-Y_{\leq{\eta}}])\cap{[{\kappa}]}^{\leq|M_{\zeta}|})\subset
M_{\zeta}.$

Step 3. The inductive step.

Assume that we have constructed $\left\langle
Y_{\xi}:{\xi}<{\zeta}\right\rangle$ and $\left\langle
w_{\xi}:{\xi}<{\zeta}\right\rangle$ such that (1)ξ-(7)ξ hold for
${\xi}<{\zeta}$.

If ${\zeta}=0$, then let $M_{\zeta}=Y_{\zeta}=w_{\zeta}=\emptyset$. Since
${\mu}_{0}=0$, (1)ζ holds. The other requirements are trivial.

If ${\zeta}$ is a limit ordinal, take $M_{\zeta}=M_{<{\zeta}}$ and
$Y_{\zeta}=w_{\zeta}=\emptyset$.

Then (1)ζ holds because ${\mu}_{\zeta}=\sup\\{{\mu}_{\xi}:{\xi}<{\zeta}\\}$.

To check (2)ζ, assume that $B\in\mathcal{B}$, $|B\cap M_{\zeta}|\geq r$ and
$|B|\leq|M_{\zeta}|$.

Since $M_{\zeta}=M_{<{\zeta}}$, there is ${\xi}<{\zeta}$ such that $|B\cap
M_{\xi}|\geq r$.

Next we show that $|B|\leq|M_{\eta}|$ for some ${\eta}<{\zeta}$. We know that
$|B|\leq|M_{\zeta}|$. If $|M_{\eta}|<|M_{\zeta}|$ for each ${\eta}<{\zeta}$,
then $|M_{\zeta}|={\mu}_{\zeta}={\nu}_{\alpha}$ for some limit ${\alpha}$, and
so $|M_{\zeta}|\notin S$, and so $|B|<|M_{\zeta}|$. Since
$M_{\zeta}=\bigcup_{{\eta}<{\zeta}}M_{\eta}$, there is ${\eta}<{\zeta}$ such
that $|B|\leq|M_{\eta}|$.

Let ${\sigma}=\max({\xi},{\eta})$.

Then $|B\cap M_{\sigma}|\geq r$ and $|B|\leq|M_{\sigma}|$, and so $B\subset
M_{\sigma}\subset M_{\zeta}$ by (2)σ. Thus (2)ζ holds.

(3)ζ holds by the construction.

(4)ζ is void.

To check (5)ζ first observe that for each ${\eta}<{\xi}$,
$C_{\eta}\in\mathcal{A}[Y_{\leq{\eta}+1}]$ by (5)η+1, so
$\mathcal{A}[Y_{\leq{\zeta}}]\supset\\{C_{\xi}:{\xi}<{\zeta}\\}$.

Assume that $B\in\mathcal{B}\sqcap M_{\zeta}$, i.e. $B\subset M_{\zeta}$ and
$B\in\mathcal{B}$. If $B$ is finite then $B\subset M_{\sigma}$ for some
${\sigma}<{\zeta}$. Thus $B\in\mathcal{B}\sqcap
M_{\sigma}\subset\mathcal{A}[Y_{\leq{\sigma}}]\subset\mathcal{A}[Y_{\leq{\zeta}}]$

So we can assume that $B$ is infinite. Since $M_{\zeta}=M_{<{\zeta}}$, there
is ${\xi}<{\zeta}$ such that $|B\cap M_{\xi}|\geq r$.

Next we show that $|B|\leq|M_{\eta}|$ for some ${\eta}<{\zeta}$. We know that
$|B|\leq|M_{\zeta}|$. If $|M_{\eta}|<|M_{\zeta}|$ for each ${\eta}<{\zeta}$,
then $|M_{\zeta}|={\mu}_{\zeta}={\nu}_{\alpha}$ for some limit ${\alpha}$, and
so $|M_{\zeta}|\notin S$, and so $|B|<|M_{\zeta}|$. Since
$M_{\zeta}=\bigcup_{{\eta}<{\zeta}}M_{\eta}$, there is ${\eta}<{\zeta}$ such
that $|B|\leq|M_{\eta}|$.

Let ${\sigma}=\max({\xi},{\eta})$.

Then $|B\cap M_{\sigma}|\geq r$ and $|B|\leq|M_{\sigma}|$ and so $B\subset
M_{\sigma}\subset M_{\zeta}$ by (2)σ. Thus (5)ζ holds.

(6)ζ, and (7)ζ are clear for limit ${\zeta}$ because
$Y_{\leq{\zeta}}=Y_{<{\zeta}}$ and $w_{\leq{\zeta}}=w_{<{\zeta}}$.

So for limit ${\zeta}$ we can carry out the inductive step.

Assume finally that ${\zeta}={\eta}+1.$

First we vertex cover $C_{\eta}$.

If $C_{\eta}\in\mathcal{C}[Y_{\leq\eta}]$, i.e. $C_{\eta}\cap
Y_{\leq{\eta}}\neq\emptyset$, let

$Y^{\prime}_{\zeta}=\\{\\}$ and $v^{\prime}_{\zeta}=\emptyset$.

Assume that $C_{\eta}\in\mathcal{C}[-Y_{\leq\eta}]$, i.e. $C_{\eta}\cap
Y_{\leq{\eta}}=\emptyset$. Write

$C^{\prime}_{\eta}=C_{\eta}\cap\bigcup((\mathcal{B}[-Y_{\leq{\eta}}])\cap{[{\kappa}]}^{\leq{{\mu}_{\zeta}}}).$

If $|C^{\prime}_{\eta}|\leq{\mu}_{\zeta}$, then
$C^{\prime\prime}_{\eta}=((C_{\eta}\setminus
C^{\prime}_{\eta})\setminus\bigcup_{{\xi}<{\eta}}C_{\xi})$ has cardinality
${\kappa}$, so we can put

$y_{\eta}=\min(C^{\prime\prime}_{\eta}\setminus M_{\eta}).$

In this case let

$Y^{\prime}_{\zeta}=\\{y_{\eta}\\}$ and $v^{\prime}_{\zeta}=\\{\left\langle
y_{\eta},C_{\eta}\right\rangle\\}$.

If $|C^{\prime}_{\zeta}|>{\mu}_{\zeta}$, then
$|(C^{\prime}_{\zeta}\setminus\bigcup_{{\xi}<{\eta}}C_{\xi})|>{\mu}_{\zeta}$
because $|(C_{\zeta}\cap\bigcup_{{\xi}<{\eta}}C_{\xi})|\leq r|{\eta}|\leq
r|{\zeta}|\leq{\mu}_{\zeta}$, so we can consider

$y_{\eta}=\min((C^{\prime}_{\zeta}\setminus\bigcup_{{\xi}<{\eta}}C_{\xi})\setminus
M_{\eta})),$

and we can pick $B_{\eta}$ with

$y_{\eta}\in
B_{\eta}\in\mathcal{B}[-Y_{\leq{\eta}}]\cap{[{\kappa}]}^{\leq{|M_{\zeta}|}}.$

In this case let

$Y^{\prime}_{\zeta}=\\{y_{\eta}\\}$ and $v^{\prime}_{\zeta}=\\{\left\langle
y_{\eta},B_{\eta}\right\rangle\\}$.

Next we want to define sets $M_{\zeta}$ and $Z_{\zeta}$, and a function
$v_{\zeta}$ such that $Y_{\zeta}=Y^{\prime}_{\zeta}\cup Z_{\zeta}$ and
$w_{\zeta}=v^{\prime}_{\zeta}\cup v_{\zeta}$ meet the requirements.

If $C_{\eta}\in\mathcal{C}[Y_{\leq\eta}]$, let $M_{\zeta}^{-}={\zeta}\cup
M_{\eta}$.

If $C_{\eta}\in\mathcal{C}[-Y_{\leq\eta}]$ and
$|C^{\prime}_{\eta}|\leq{\mu}_{\zeta}$ let $M_{\zeta}^{-}={\zeta}\cup
M_{\eta}\cup Y^{\prime}_{\eta}\cup C^{\prime}_{\eta}$.

If $C_{\eta}\in\mathcal{C}[-Y_{\leq\eta}]$ and
$|C^{\prime}_{\eta}|>{\mu}_{\zeta}$ let $M_{\zeta}^{-}={\zeta}\cup
M_{\eta}\cup Y^{\prime}_{\eta}\cup B_{\eta}$.

Since $M^{\prime}_{\zeta}\in{[{\kappa}]}^{{\mu}_{\zeta}}$, using standard
closing arguments, we can find a set
$M_{\zeta}\in{[{\kappa}]}^{{\mu}_{\zeta}}$ such that

  1. (a)

$M_{\zeta}\supset M_{\zeta}^{\prime}$,

  2. (b)

if $B\in\mathcal{B}$, $|B\cap M_{\zeta}|\geq r$ and $|B|\leq{\mu}_{\zeta}$,
then $B\subset M_{\zeta}$.

Write

$\mathcal{C}^{w}_{\leq\eta}=\bigcup(\operatorname{ran}w_{\leq{\eta}}\cap{[{\kappa}]}^{{\kappa}}).$

and let

$\mathcal{B}_{\zeta}=\big{(}(\mathcal{B}\sqcap M_{\zeta})[-(Y_{\leq{\eta}}\cup
Y^{\prime}_{\zeta})]\big{)}$

Consider the family

$\mathcal{B}_{\zeta}^{-}=\mathcal{B}_{\zeta}\restriction((M_{{\zeta}}\setminus
M_{\eta})\setminus(C_{\eta}\cup C^{w}_{\leq{\eta}})).$

Since $|\mathcal{B}^{-}_{\zeta}|\leq|{[M_{\zeta}]}^{r}|={\mu}_{\zeta}$, we can
apply the inductive assumption $\Delta({\mu}_{\xi})$ for
$\mathcal{B}_{\zeta}^{-}$ provided that we can show that
$\|\mathcal{B}_{\zeta}^{-}\|$ is nowhere stationary. The next lemma will
actually yield that
$\|\mathcal{B}_{\zeta}^{-}\|\subset\|\mathcal{B}\|\cup{\omega}$.

Claim. $|C^{w}_{\leq{\eta}}\cap B|<|B|$ for each
$B\in(\mathcal{B}[-Y_{\leq{\eta}}])\cap{[{\kappa}]}^{\leq{{\mu}_{\zeta}}}$.

###### Proof of the Claim.

Fix $B\in\mathcal{B}[-Y_{\leq{\eta}}]\cap{[{\kappa}]}^{\leq{{\mu}_{\zeta}}}$.

Let ${\beta}=\sup\\{{\gamma}:{\nu}_{\gamma}<|B|\\}$. Since
${\nu}_{\varepsilon}\notin S$ for limit ${\varepsilon}$, we have
${\nu}_{\beta}<|B|$.

Assume that $w_{{\xi}+1}(y)=C_{\xi}$ and $B\cap(C_{\xi}\setminus
M_{\eta})\neq\emptyset$. Assume that ${\mu}_{\xi+1}={\nu}_{\varepsilon}$.
Since the sequence $\left\langle{\nu}_{\alpha}:{\alpha}<{\rho}\right\rangle$
is continuous, by the definition of ${\mu}_{{\xi}+1}$, ${\varepsilon}$ can not
be a limit ordinal. So ${\mu}_{\xi+1}={\nu}_{\alpha+1}$ for some ${\alpha}$.

We know

$C_{\xi}\cap\bigcup((\mathcal{B}[-Y_{\leq{\xi}+1}])\cap{[{\kappa}]}^{\leq{\mu}_{{\xi}+1}})\subset
M_{{\xi}+1}.$

by (7)ξ+1, and so $|B|>{\mu}_{{\xi}+1}={\nu}_{{\alpha}+1}$.

Since ${\xi+1}\leq{\mu}_{\xi+1}$ by the definition of ${\mu}_{\xi+1}$, we have
${\xi}\in{\nu}_{{\alpha}+1}$.

Since ${\nu}_{{\alpha}+1}<|B|$, it follows that
${\nu}_{{\alpha}+1}\leq{\nu}_{\beta}$. So

$\\{{\xi}:C_{\xi}\in\operatorname{ran}w_{\leq{\eta}}\land
B\cap(C_{\xi}\setminus M_{\eta})\neq\emptyset\\}\subset{\nu}_{\beta}<|B|.$

So we proved the Claim. ∎

If $B\in\mathcal{B}_{\zeta}$, then $B\notin\mathcal{B}\sqcap M_{\eta}$, so
$|B\cap M_{\eta}|<r$ or $|B|>|M_{\eta}|$. Moreover $B\subset M_{\zeta}$, so
$|B\cap(M_{\zeta}\setminus M_{\eta})|=|B|$. Since $|B\cap
C^{w}_{\leq{\eta}}|<|B|$ by the Claim and $|B\cap C_{\eta}|<r$, we have
$|B|=|B\cap(M_{\zeta}\setminus M_{\eta})\setminus(C_{\eta}\cup
C^{w}_{\leq{\eta}})|$. Thus
$\|\mathcal{B}_{\zeta}^{-}\|\subset{\omega}\cup(K\cap{\kappa})$.

Since $\mathcal{B}^{-}_{\zeta}\subset\mathcal{P}(M_{\zeta})$ and
$|M_{\zeta}|={\mu}_{\zeta}$ and $\|\mathcal{B}^{-}_{\zeta}\|$ is nowhere
stationary, so we can apply the inductive assumption $\Delta({\mu}_{\zeta})$
for $\mathcal{B}_{\zeta}^{-}$ to obtain a set
$Z_{\zeta}\subset{\kappa}\cap(M_{{\zeta}}\setminus
M_{{\eta}})\setminus(C_{\eta}\cup C^{w}_{\leq{\eta}})$ which is a minimal
vertex cover for $\mathcal{B}^{\prime}_{\zeta}$, and so it is a a minimal
vertex cover for $\mathcal{B}_{\zeta}$, Fix a witnessing function
$v_{\zeta}:Z_{\zeta}\to\mathcal{B}_{\zeta}$ such that $v_{\zeta}(y)\cap
Z_{\zeta}=\\{y\\}$ for each $y\in Z_{\zeta}$.

Let

$Y_{\zeta}=\\{y_{\zeta}\\}\cup Y^{\prime}_{\zeta}\text{ and
}w_{\zeta}=v^{\prime}_{\zeta}\cup v_{\zeta}.$

Now we should check that (1)ζ-(7)ζ hold.

(1)ζ and (2)ζ hold by the choice of $M_{\zeta}$.

(3)ζ is void.

(4)ζ is clear from the construction.

Next we check (5)ζ. We have
$\mathcal{A}[Y^{\prime}_{\zeta}]\supset\mathcal{B}_{\zeta}$ and
$C_{\eta}\in\mathcal{A}[Y_{\leq{\eta}}\cup Y^{\prime}_{\eta}]$ by the
construction, and
$\mathcal{A}[Y_{\leq{\eta}}]\supset(\mathcal{B}\sqcap\mathcal{M}_{\eta})\cup\\{C_{\xi}:{\xi}<{\eta}\\}$
by the inductive assumption (5)η, so putting together we obtain

$\mathcal{A}[Y_{\leq{\zeta}}]\supset(\mathcal{B}\cap\mathcal{M}_{\zeta}\cap{[{\kappa}]}^{\leq|M_{\zeta}|})\cup\\{C_{\xi}:{\xi}<{\zeta}\\}.$

So (5)ζ holds.

Next we check (6)ζ. Since $Y_{\zeta}\subset M_{\zeta}\setminus
M_{<{\zeta}}\setminus C^{w}_{\leq{\eta}}$, and
$\bigcup\operatorname{ran}w_{\leq{\eta}}\subset M_{<{\zeta}}\cup
C^{w}_{\leq{\eta}}$, so (6)ζ holds for $y\in Y_{\leq{\eta}}$.

If $y_{\eta}$ is defined, then $C_{\eta}\cap Y_{\leq{\eta}}=\emptyset$, so
$w_{\zeta}(y)\cap Y_{\zeta}=\\{y_{\eta}\\}$ because $Z_{\zeta}\cap
C_{\eta}=\emptyset$.

If $y\in Z_{\zeta}$, then $w_{\zeta}(y)\in\mathcal{B}[-(Y_{\leq{\eta}}\cup
Y^{\prime}_{\zeta})]$, and $w_{\zeta}(y)\cap Z_{\zeta}=\\{y\\}$ so
$w_{\zeta}(y)\cap Y_{\leq{\zeta}}=\\{y\\}$.

Thus (6)ζ holds.

Observe that (7)ζ also holds: if $w_{\zeta}(y_{\eta})=C_{\eta}$, then
$|C^{\prime}_{\eta}|\leq|M_{\zeta}|$, and so $C^{\prime}_{\zeta}\subset
M^{-}_{\zeta}$ implies $C^{\prime}_{\zeta}\subset M_{\zeta}$.

Step 4. Conclusion.

After the inductive construction $Y=\bigcup_{{\zeta}<{\kappa}}Y_{\zeta}$ is a
minimal vertex cover of $\mathcal{A}$. The minimality is witnessed by the
function $w=\bigcup_{{\zeta}<{\kappa}}w_{\zeta}$. ∎

##  4\. Hypergraphs possessing property $\operatorname{C}(k,r)$ for $k\geq 3$

Instead of Theorem 1.4 we will prove the following stronger theorem:

######  Theorem 4.1.

$\mathbf{M}\mathbb{(}{\lambda},{{\omega}},r,k)\to\mathbf{MaxWO}$ provided
${\omega}\leq{\lambda}$ and $k,r\in{\omega}$

###### Proof of Theorem 4.1.

We want to apply Theorem 2.5(2) to obtain the result. So let

$\mathbb{A}=\\{\mathcal{A}:\exists{\lambda}\geq{\omega}_{2}\
(\mathcal{A}\subset{[{\lambda}]}^{{\omega}}\text{ has property
$\operatorname{C}(k,r)$})\\}.$

We should verify properties 2.5(a,b,c’).

(a) is trivial by definition.

(b) follows from the Lemma 4.2 below.

######  Lemma 4.2.

If ${\omega}\leq{\kappa}<{\lambda}$ are infinite cardinals, and
$\mathcal{A}\subset{[{\lambda}]}^{{\kappa}}$ has property
$\operatorname{C}(k,r)$ for some $k,r\in{\omega}$, then $\mathcal{A}$ has a
good cut.

###### Proof.

For $x\in{[{\lambda}]}^{r}$ let

$F(x)=\\{A\in\mathcal{A}:x\subset A\\}$

Since $\mathcal{A}$ is $\operatorname{C}(k,r)$, $|F(x)|\leq k-1$.

Let $\left\langle{\lambda}_{\alpha}:{\alpha}<{\omega}\cdot
cf({\lambda})\right\rangle$ be an increasing continuous cofinal sequence in
${\lambda}$ with ${\lambda}_{0}=0$. Define an increasing, continuous sequence
$\left\langle H_{\eta}:{\eta}<{\omega}\cdot cf({\lambda})\right\rangle$ such
that

  1. (1)

$H_{0}=\emptyset$

  2. (2)

$H_{{\eta}+1}=H_{\eta}\cup({\eta}+1)\cup\bigcup\\{F(x):x\in{[H_{\eta}]}^{r}\\}$.

Since $F(x)\leq k-1$, $|H_{\eta}|\leq|{\eta}|+{\omega}$.

Moreover $|A\cap H_{\eta}|\geq r$ implies $A\subset H_{{\eta}+1}$.

Let $G_{\alpha}=H_{{\omega}\cdot{\alpha}}$. Then $\left\langle
G_{\alpha}:{\alpha}<cf({\lambda})\right\rangle$ is a good cut of
$\mathcal{A}$. ∎

Property (c’) follows from the next lemma.

######  Lemma 4.3.

If $\mathcal{A}$ is a countable hypergraph which possesses property $P(k,r)$,
then $\mathcal{A}$ has a maximizing well-ordering $\prec$.

###### Proof of Lemma 4.3.

We prove it by induction on $k$. If $k=1$, then we have that for all
$n\in\omega$, $|A_{n}|\leq r-1$, so $A_{n}$ is a finite set. Choose any well-
ordering $\prec$ on $\bigcup_{n\in\omega}A_{n}$, then clearly all non-empty
finite sets have maximal element by $\prec$.

Now suppose the lemma is true for hypergraphs possessing property
$\operatorname{C}(k,r)$ and let $\mathcal{A}$ be a hypergraph with property
$\operatorname{C}(k+1,r)$, and write $\mathcal{A}=\\{A_{n}:n<\omega\\}$. For
$n<{\omega}$ let

$B_{n}=A_{n}\setminus\bigcup_{i<n}A_{i},$

the disjointification of $A_{n}$. Clearly $B_{n}\cap B_{m}=\emptyset$ if
$n\neq m$ and $\bigcup_{n\in\omega}B_{n}=\bigcup_{n\in\omega}A_{n}$, but
$B_{n}=\emptyset$ is possible even is $A_{n}\neq\emptyset$. Choose any $n$,
such that $B_{n}\neq\emptyset$.

We will show that the system $\\{A_{m}\cap B_{n}:m>n,A_{m}\neq A_{n}\\})$ is
$\operatorname{C}(k,r)$. Choose any $m_{1},\dots,m_{k}>n$, such that the sets
$A_{m_{i}}\cap B_{n}$ are pairwise different for $1\leq i\leq k$. The the sets
$A_{m_{i}}$ are also pairwise different. For the intersection

$(A_{m_{1}}\cap B_{n})\cap\dots\cap(A_{m_{k}}\cap
B_{n})=A_{m_{1}}\cap\dots\cap A_{m_{k}}\cap B_{n}\subseteq\\\
A_{m_{1}}\cap\dots\cap A_{m_{k}}\cap A_{n}$

and $A_{m_{1}},\dots,A_{m_{k}},A_{n}$ are pairwise different, so
$|(A_{m_{1}}\cap B_{n})\cap\dots\cap(A_{m_{k}}\cap
B_{n})|\leq|A_{m_{1}}\cap\dots\cap A_{m_{k}}\cap A_{n}|\leq r-1$, as
$\mathcal{A}$ has property $\operatorname{C}(k+1,r)$.

By the inductive assumption there is a well ordering $\prec^{\prime}_{n}$ on

$\bigcup{\\{A_{m}\cap B_{n}:m>n,A_{m}\neq A_{n}\\})},$

such that for all $m>n$, where $A_{m}\neq A_{n}$ and $A_{m}\cap
B_{n}\neq\emptyset$, then it has a maximal element. We can make a $\prec_{n}$
well-ordering from it on $B_{n}$, so that $B_{n}$ has a maximal element, and
for all $m>n$, if $A_{m}\cap B_{n}\neq\emptyset$, then it has a maximal
element. First if $B_{n}$ has elements that are not in any $A_{m}\cap B_{n}$,
where $m>n,A_{m}\neq B_{n}$, then we well-order them into the bottom of
$B_{n}$, so the well-ordering is defined on the whole $B_{n}$. If $B_{n}$ does
not have a maximal element by $\prec^{\prime}_{n}$, then we pick any $v\in
B_{n}$, and elevate it into the top of $B_{n}$, while remaining the order of
other elements. Doing this the order $\prec_{n}$ clearly remains a well-order.
Then $v$ will be the new maximum of $B_{n}$. For $m>n$ if $A_{m}\neq A_{n}$
and $A_{m}\cap B_{n}\neq\emptyset$, a maximal element by $\prec^{\prime}_{n}$.
If $v\not\in A_{m}\cap B_{n}$, then its order does not change, so it keeps its
maximal element. If $v\in A_{m}\cap B_{n}$, then it will be its new maximal
element, as it is even maximal in $B_{n}$. Finally if $A_{m}=A_{n}$, then
$A_{m}\cap B_{n}=A_{n}\cap B_{n}=B_{n}$, that have a maximal element.

Now we define the ordering $\prec$. For any
$u,v\in\bigcup_{n\in\omega}A_{n}=\bigcup_{n\in\omega}B_{n}$ there are
$i,j\in\omega$, such that $u\in B_{i},v\in B_{j}$. If $i<j$, then $u\prec v$,
if $j<i$, then $v\prec u$, and if $i=j$, then we order them by $\prec_{i}$ on
$B_{i}$. By other words we take the well orders $\prec_{n}$-s on the top of
each other, and then $\prec$ is also a well-order. Choose any $n\in\omega$,
that $A_{n}\neq\emptyset$. If $B_{n}\neq\emptyset$, then it has a maximal
element. Since all elements of $A_{n}$ are either in $B_{n}$ or in some
$B_{i}$, where $i<n$, we have $\max(A_{n})=\max(B_{n})$. If $B_{n}=\emptyset$,
then we have $\emptyset\neq A_{n}=\bigcup_{i<n}{B_{i}}$. Let $j<n$ be the
maximal, such that $A_{n}\cap B_{j}\neq\emptyset$. Then by the construction of
$\prec_{j}$, we have that $A_{n}\cap B_{j}$ has a maximal element. Since all
elements of $A_{n}$ are even in $A_{n}\cap B_{j}$ or in some $A_{n}\cap
B_{i}$, where $i<j$, it is also maximal in $A_{n}$. Then the well ordering
$\prec$ is good, so the induction step works from $k$ to $k+1$. ∎

So we can apply Theorem 2.5(2) to derive that every $\mathcal{A}\in\mathbb{A}$
has a maximizing well-order.

∎

######  Definition 4.4.

If $\mathcal{E}$ is a hypergraph, let $\min\mathcal{E}$ be the family of
$\subset$-minimal elements of $\mathcal{E}$.

Observe that if $\mathcal{E}$ is $\operatorname{C}(k,r)$, then for each
$E\in\mathcal{E}$ there is $E^{\prime}\in\min\mathcal{E}$ with
$E^{\prime}\subset E$. So a minimal vertex cover of $\min\mathcal{E}$ will be
a minimal vertex cover of $\mathcal{E}$.

###### Proof of Theorem 1.5.

We prove first that
$\mathbf{M}\mathbb{(}{\omega}_{1},{{\omega}_{1}},3,r)\to\mathbf{MinVC}$ for
$r<{\omega}$.

Let $\mathcal{D}\subset{[{\omega}_{1}]}^{{\omega}_{1}}$ be a hypergraph having
property $\operatorname{C}(3,r)$.

Write $\mathcal{D}=\\{D_{\alpha}:{\alpha}<{\omega}_{1}\\}$. For each
${\alpha}<{\omega}_{1}$ pick

$y_{\alpha}\in D_{\alpha}\setminus\\{D_{\xi}\cap
D_{\zeta}:{\xi}<{\zeta}<{\alpha}\\}.$

Let $Y=\\{y_{\alpha}:{\alpha}<{\omega}_{1}\\}$.

Then $\mathcal{D}[Y]=\mathcal{D}$.

Moreover, $\mathcal{D}\restriction Y$ is $\operatorname{C}(3,r)$ and
$\operatorname{C}(2,{\omega}_{1})$ because $y_{\alpha}\notin D_{\zeta}\cap
D_{\xi}$ for ${\alpha}>\max({\zeta},{\xi})$.

Let $\mathcal{A}=\min(\mathcal{D}\restriction Y)$.

Then a minimal vertex cover of $\mathcal{A}$ will be a minimal vertex cover of
$\mathcal{D}$.

So to find a minimal vertex cover of $\mathcal{D}$ it is enough to prove the
following lemma:

######  Lemma 4.5.

Assume that a hypergraph $\mathcal{A}\subset\mathcal{P}({\omega}_{1})$
possesses the following properties:

  1. (A)

$\operatorname{C}(k,r)$,

  2. (B)

$\operatorname{C}(2,{\omega}_{1})$,

  3. (C)

$A\setminus A^{\prime}\neq\emptyset$ for each
$\\{A,A^{\prime}\\}\in{[\mathcal{A}]}^{2}$.

Then $\mathcal{A}$ has a minimal vertex cover.

###### Proof of the Lemma 4.5.

Write $\mathcal{B}=\mathcal{A}\cap{[{\omega_{1}}]}^{\leq{\omega}}$ and
$\mathcal{C}=\mathcal{A}\cap{[{\omega_{1}}]}^{{\omega_{1}}}$. Adding pairwise
disjoint "dummy" sets to $\mathcal{A}$ we can assume that
$|\mathcal{C}|={\omega_{1}}$. Let $\left\langle
C_{\xi}:{\xi}<{\omega_{1}}\right\rangle$ be an enumeration of $\mathcal{C}$.

Step 1. The inductive construction.

By transfinite recursion on ${\zeta}<{\omega_{1}}$ we will define an
increasing, continuous sequence $\left\langle
M_{\zeta}:{\zeta}<{\omega_{1}}\right\rangle$ of subsets of ${\omega_{1}}$, a
sequence $\left\langle Y_{\zeta}:{\zeta}<{\omega}\right\rangle$ of pairwise
disjoint subsets of ${\omega_{1}}$, and a sequence $\left\langle
w_{\zeta}:{\zeta}<{\omega_{1}}\right\rangle$ of functions such that

  1. (1)ζ

${\zeta}\subset M_{\zeta}\in{[{\omega_{1}}]}^{{\omega}}$ for
$1\leq{\zeta}<{\omega}_{1}$, $M_{0}=\emptyset$,

  2. (2)ζ

if $B\in\mathcal{B}$ and $|B\cap M_{\zeta}|\geq r$ then $B\subset M_{\zeta}$,

  3. (3)ζ

If ${\zeta}=0$ or ${\zeta}$ is a limit ordinal, then $M_{\zeta}=M_{<{\zeta}}$
and $Y_{\zeta}=w_{\zeta}=\emptyset$,

  4. (4)ζ

if ${\zeta}={\eta}+1$, then $Y_{\zeta}\subset(M_{{\zeta}}\setminus
M_{\eta})\cap{\omega_{1}}$ and

$w_{\zeta}:Y_{\zeta}\to\big{(}(\mathcal{B}\sqcap
M_{\zeta})\setminus(\mathcal{B}\sqcap M_{\eta})\big{)}\cup\\{C_{\eta}\\},$

  5. (5)ζ

$\mathcal{A}[Y_{\leq{\zeta}}]\supset(\mathcal{B}\sqcap\mathcal{M}_{\zeta})\cup\\{C_{\xi}:{\xi}<{\zeta}\\}$,

  6. (6)ζ

$w_{\leq{\zeta}}(y)\cap Y_{\leq{\zeta}}=\\{y\\}$ for each $y\in
Y_{\leq{\zeta}}$,

  7. (7)ζ

if $C_{\eta}=w_{\zeta}(y)$ for some $y\in Y_{\zeta}$, then

$C_{\eta}\cap\bigcup(\mathcal{B}[-Y_{\leq{\eta}}])\subset M_{\zeta}.$

Step 2. The inductive step.

Assume that we have constructed $\left\langle
Y_{\xi}:{\xi}<{\zeta}\right\rangle$ and $\left\langle
w_{\xi}:{\xi}<{\zeta}\right\rangle$ such that (1)ξ–(7)ξ hold for
${\xi}<{\zeta}$.

If ${\zeta}=0$, then let $M_{\zeta}=Y_{\zeta}=w_{\zeta}=\emptyset$. All
requirements are trivial.

If ${\zeta}$ is a limit ordinal, put $M_{\zeta}=M_{<{\zeta}}$ and
$Y_{\zeta}=w_{\zeta}=\emptyset$.

Then (1)ζ is trivial.

To check (2)ζ, assume that $B\in\mathcal{B}$ and $|B\cap M_{\zeta}|\geq r$ .

Since $M_{\zeta}=M_{<{\zeta}}$, there is ${\xi}<{\zeta}$ such that $|B\cap
M_{\xi}|\geq r$. So $B\subset M_{\xi}\subset M_{\zeta}$ by (2)ξ. Thus (2)ζ
holds.

(3)ζ holds by the construction.

(4)ζ is void.

To check (5)ζ first observe that for each ${\eta}<{\xi}$,
$C_{\eta}\in\mathcal{A}[Y_{\leq{\eta}+1}]$ by (5)η+1, so
$\mathcal{A}[Y_{\leq{\zeta}}]\supset\\{C_{\xi}:{\xi}<{\zeta}\\}$.

Assume that $B\in\mathcal{B}\sqcap M_{\zeta}$, i.e. $B\subset M_{\zeta}$ and
$B\in\mathcal{B}$. If $B$ is finite then $B\subset M_{\sigma}$ for some
${\sigma}<{\zeta}$. Thus $B\in\mathcal{B}\sqcap
M_{\sigma}\subset\mathcal{A}[Y_{\leq{\sigma}}]\subset\mathcal{A}[Y_{\leq{\zeta}}]$

So we can assume that $B$ is infinite. Since $M_{\zeta}=M_{<{\zeta}}$, there
is ${\xi}<{\zeta}$ such that $|B\cap M_{\xi}|\geq r$.

Then $|B\cap M_{\xi}|\geq r$ so $B\subset M_{\xi}\subset M_{\zeta}$ by (2)ξ.
Thus (5)ζ holds.

(6)ζ, and (7)ζ are clear for limit ${\zeta}$ because
$Y_{\leq{\zeta}}=Y_{<{\zeta}}$ and $w_{\leq{\zeta}}=w_{<{\zeta}}$.

So for limit ${\zeta}$ we can carry out the inductive step.

Assume finally that ${\zeta}={\eta}+1.$

First we vertex cover $C_{\eta}$.

Case 1. $C_{\eta}\in\mathcal{C}[Y_{\leq\eta}]$, i.e. $C_{\eta}\cap
Y_{\leq{\eta}}\neq\emptyset$.

Let

$Y^{\prime}_{\zeta}=\\{\\}$ and $v^{\prime}_{\zeta}=\emptyset$

and

$M_{\zeta}^{-}={\zeta}\cup M_{\eta}.$

Case 2. Assume that $C_{\eta}\in\mathcal{C}[-Y_{\leq\eta}]$, i.e.
$C_{\eta}\cap Y_{\leq{\eta}}=\emptyset$.

Let

$\mathcal{B}^{\prime}_{\zeta}=\min(\mathcal{B}[-Y_{\leq{\eta}}]\restriction({\omega}_{1}\setminus
M_{\eta}))$

Observe that if $B\in\mathcal{B}[-Y_{\leq{\eta}}]$, then $B\setminus
M_{\eta}\neq\emptyset$ by (5)η . Write

$C^{\prime}_{\eta}=C_{\eta}\cap\bigcup\mathcal{B}_{\zeta}^{\prime}.$

Case 2.1. $C^{\prime}_{\eta}=\emptyset$.

Since $C^{\prime\prime}_{\eta}=C_{\eta}\setminus\bigcup_{{\xi}<{\eta}}C_{\xi}$
has cardinality ${\omega}_{1}$, so we can define

$y_{\eta}=\min(C^{\prime\prime}_{\eta}\setminus M_{\eta}).$

In this case let

$Y^{\prime}_{\zeta}=\\{y_{\eta}\\}$ and $v^{\prime}_{\zeta}=\\{\left\langle
y_{\eta},C_{\eta}\right\rangle\\}$

and

$M_{\zeta}^{-}={\zeta}\cup M_{\eta}\cup Y^{\prime}_{\zeta}.$

Case 2.2. $C^{\prime}_{\zeta}\neq\emptyset$.

Then put

$y_{\eta}=\min(C^{\prime}_{\zeta})\in{\omega}_{1}\setminus M_{\eta},$

and pick $B_{\eta}\in B[-Y_{\leq{\eta}}]$ with

$y_{\eta}\in(B_{\eta}\setminus M_{\eta})\in\mathcal{B}^{\prime}_{\zeta}.$

In this case let

$Y^{\prime}_{\zeta}=\\{y_{\eta}\\}$ and $v^{\prime}_{\zeta}=\\{\left\langle
y_{\eta},B_{\eta}\right\rangle\\}$

and

$M_{\zeta}^{-}={\zeta}\cup M_{\eta}\cup Y^{\prime}_{\zeta}\cup B_{\eta}.$

Next we want to define sets $M_{\zeta}$ and $Z_{\zeta}$, and a function
$v_{\zeta}$ such that $Y_{\zeta}=Y^{\prime}_{\zeta}\cup Z_{\zeta}$ and
$w_{\zeta}=w^{\prime}_{\zeta}\cup v_{\zeta}$ meet the requirements.

Using standard closing arguments we can find a set
$M_{\zeta}\in{[{\omega_{1}}]}^{\omega}$ such that

  1. (a)

$M_{\zeta}\supset M_{\zeta}^{\prime}$,

  2. (b)

if $B\in\mathcal{B}$ and $|B\cap M_{\zeta}|\geq r$ then $B\subset M_{\zeta}$.

If we are in Case 1 or in Case 2.1, then let

$\mathcal{B}_{\zeta}=(\mathcal{B}\sqcap
M_{\zeta})[-(Y_{\leq{\eta}})]\restriction\big{(}{\omega}_{1}\setminus
M_{\eta}\big{)}.$

Then $\emptyset\notin\mathcal{B}_{\zeta}\subset\mathcal{P}(M_{\zeta})$ and
$\mathcal{B}_{\zeta}$ possesses property $\operatorname{C}(3,k)$, so by
theorem Theorem 1.4 the hypergraph $\mathcal{B}_{\zeta}$ has a minimal vertex
cover $Z_{\zeta}$ and a witnessing function $v_{\zeta}$.

Assume that we are in Case 2.2.

Let

$\mathcal{B}_{\zeta}=\\{(B\setminus M_{\eta})\setminus
B_{\eta}:B\in(\mathcal{B}\sqcap M_{\zeta})[-(Y_{\leq{\eta}}\cup
Y^{\prime}_{\zeta}])\\}.$

Since $B_{\eta}\setminus M_{\eta}$ was a minimal element of
$\mathcal{B}[-Y_{\leq{\eta}}]\restriction({\omega}_{1}\setminus M_{\eta})$, it
follows that $\emptyset\notin\mathcal{B}_{\eta}$. So by theorem Theorem 1.4
the hypergraph $\mathcal{B}_{\zeta}$ has a minimal vertex cover $Z_{\zeta}$
and a witnessing function $v_{\zeta}$.

Let

$Y_{\zeta}=Y^{\prime}_{\zeta}\cup Z_{\zeta}\text{ and
}w_{\zeta}=v^{\prime}_{\zeta}\cup v_{\zeta}.$

Now we should check that (1)ζ-(7)ζ hold.

(1)ζ and (2)ζ hold by the choice of $M_{\zeta}$.

(3)ζ is void.

(4)ζ is clear from the construction.

Next we check (5)ζ. We have
$\mathcal{A}[Y^{\prime}_{\zeta}]\supset\mathcal{B}_{\zeta}$ and
$C_{\eta}\in\mathcal{A}[Y_{\leq{\eta}}\cup Y^{\prime}_{\eta}]$ by the
construction, and
$\mathcal{A}[Y_{\leq{\eta}}]\supset(\mathcal{B}\sqcap\mathcal{M}_{\eta})\cup\\{C_{\xi}:{\xi}<{\eta}\\}$
by the inductive assumption (5)η, so putting together we obtain
$\mathcal{A}[Y_{\leq{\zeta}}]\supset(\mathcal{B}\cap\mathcal{M}_{\zeta})\cup\\{C_{\xi}:{\xi}<{\zeta}\\}$.
So (5)ζ holds.

Next we check (6)ζ.

Write

$\mathcal{C}^{w}_{\leq\eta}=\bigcup(\operatorname{ran}w_{\leq{\eta}}\cap{[{\omega_{1}}]}^{{\omega_{1}}}),$

and observe that

$C^{w}_{\leq{\eta}}\cap B=\emptyset$ for each
$B\in\mathcal{B}[-Y_{\leq{\eta}}]$. (${\ddagger}$)

Since $Y_{\zeta}\subset M_{\zeta}\setminus M_{<{\zeta}}\setminus
C^{w}_{\leq{\eta}}$, and $\bigcup\operatorname{ran}w_{\leq{\eta}}\subset
M_{<{\zeta}}\cup C^{w}_{\leq{\eta}}$, so (6)ζ holds for $y\in Y_{\leq{\eta}}$.

If $y_{\eta}$ is defined, then $C_{\eta}\cap Y_{\leq{\eta}}=\emptyset$, so
$w_{\zeta}(y)\cap Y_{\zeta}=\\{y_{\eta}\\}$ because $Z_{\zeta}\cap
C_{\eta}=\emptyset$.

If $y\in Z_{\zeta}$, then $w_{\zeta}(y)\in\mathcal{B}[-(Y_{\leq{\eta}}\cup
Y^{\prime}_{\zeta})]$, and $w_{\zeta}(y)\cap Z_{\zeta}=\\{y\\}$ so
$w_{\zeta}(y)\cap Y_{\leq{\zeta}}=\\{y\\}$.

Thus (6)ζ holds.

Observe that (7)ζ also holds: if $w_{\zeta}(y_{\eta})=C_{\eta}$, then
$C^{\prime}_{\eta}=\emptyset$, which is just the statement of (7)ζ.

Step 4. Conclusion.

After the inductive construction $Y=\bigcup_{{\zeta}<{\kappa}}Y_{\zeta}$ is a
minimal vertex cover for $\mathcal{A}$. The minimality is witnessed by the
function $w=\bigcup_{{\zeta}<{\kappa}}w_{\zeta}$. ∎

We want to apply Theorem 2.5(1) to conclude the proof of Theorem 1.5. So let

$\mathbb{A}=\\{\mathcal{A}:\exists{\lambda}\geq{\omega}\
(\mathcal{A}\subset{[{\lambda}]}^{{\omega}_{1}}\text{ has property
$\operatorname{C}(3,r)$})\\}.$

Then 2.5(a) is trivial bt definition. 2.5(b) follows from Lemma 4.2. Finally
2.5(c) is just Lemma 4.5. ∎

##  5\. Problems

  1. (1)

Does $\mathbf{M}\mathbb{(}{\omega}_{1},{{\omega}_{1}},4,r)\to\mathbf{MinVC}$
hold?

  2. (2)

Does $\mathbf{M}\mathbb{(}{\omega}_{2},{{\omega}_{2}},3,r)\to\mathbf{MinVC}$
hold?

## References

  * [1] Banakh, Taras ; van der Zypen, Dominic, Minimal covers of infinite hypergraphs. Discrete Math. 342 (2019), no. 11, 3043–3046
  * [2] Erdős, P., Hajnal, A., On a property of families of sets, Acta Math. Acad. Sci. Hungar., 12, (1961), pp 87–123.
  * [3] Hajnal, A. Juhász, I. Soukup, L. Szentmiklóssy, Z. Conflict free colorings of (strongly) almost disjoint set-systems. Acta Math. Hungar. 131 (2011), no. 3, 230–274.
  * [4] Soukup, L. Essentially disjoint families, conflict free colorings and Shelah’s revised GCH. Acta Math. Hungar. 140 (2013), no. 3, 293–303.
  * [5] J. Klimó, On the minimal covering of infinite sets, Discrete Appl. Math. 45 (1993) 161–168.
  * [6] P. Komjáth: Minimal covering sets for infinite set systems, Disc. Math., 342(2019), 1849–1856.
  * [7] K. Kunen: Set Theory, North-Holland, New York, 1980.
  * [8] S. Shelah: The Generalized Continuum Hypothesis revisited, Israel J. Math., 116 (1998) pp 285-321.
  * [9] Dominic van der Zypen, Minimal covering sets in families of sets intersecting in at most 1 point, https://mathoverflow.net/questions/277856.


# Variational Neural Networks

Illia Oleksiienko∗, Dat Thanh Tran† and Alexandros Iosifidis∗ This work has
received funding from the European Union’s Horizon 2020 research and
innovation programme (grant agreement No 871449 (OpenDR)).I. Oleksiienko and
A. Iosifidis are with the Department of Electrical and Computer Engineering,
Aarhus University, Denmark (e-mail: {io,ai}@ece.au.dk). D. T. Tran is with the
Department of Computing Sciences, Tampere University, Finland (e-mail:
thanh.tran@tuni.fi).

###### Abstract

Bayesian Neural Networks (BNNs) provide a tool to estimate the uncertainty of
a neural network by considering a distribution over weights and sampling
different models for each input. In this paper, we propose a method for
uncertainty estimation in neural networks called Variational Neural Network
that, instead of considering a distribution over weights, generates parameters
for the output distribution of a layer by transforming its inputs with
learnable sub-layers. In uncertainty quality estimation experiments, we show
that VNNs achieve better uncertainty quality than Monte Carlo Dropout or Bayes
By Backpropagation methods.

###### Index Terms:

Bayesian Neural Networks, Bayesian Deep Learning, Uncertainty Estimation

##  I Introduction

The ability to estimate the uncertainty of prediction in neural networks
provides advantages in using high-performing models in real-world problems, as
it enables higher-level decision-making to consider such information in
further actions. To do so, one needs the neural network to accompany its
output with a measurement of its corresponding uncertainty for each input it
processes. Several approaches have been introduced to this end, with Bayesian
Neural Networks (BNNs) [1, 2, 3] providing an elegant framework for estimating
uncertainty of a neural network by introducing a probability distribution over
its weights and sampling different models that are meant to describe the input
from different points of view. This allows to determine inputs for which the
network predictions are different, leading to a measurement of the network
uncertainty in its outputs. Such an approach usually comes with an increased
computational cost, but may be valuable for tasks where prediction errors
result in high losses, such as autonomous driving, or medical image analysis,
or critical infrastructure control.

The choice of the prior weights probability distribution function influences
the statistical quality of the model and the computational resources needed to
use such neural networks, which creates a possibility to explore different
approaches to BNNs by using Gaussian [4], Bernoulli [5], Categorical [6] or
other distributions. Sampling from the posterior distribution can be
difficult, due to the complex nature of it. This leads to methods that avoid
direct computation of the posterior, such as Markov Chain Monte Carlo (MCMC)
[7], which constructs a Markov chain of samples $S_{i}$ that are distributed
following the desired posterior, or Variational Inference [8], which scales
better than MCMC and aims to estimate a parametrized distribution that should
be close to the exact posterior. How close the distributions are is computed
using the Kullback-Leibler (KL) divergence [9], but it still requires the
exact posterior. This is overcome by computing an Evidence Lower Bound (ELBO)
instead and optimizing it with Stochastic Variational Inference (SVI) [10].

We introduce Variational Neural Networks (VNNs) which do not consider a
distribution over weights, but define sub-layers to generate parameters for
the output distribution of the layer. To keep computational and memory
resource usage practical, we consider a Gaussian distribution with learnable
mean and variance. We provide a neural network formulation that describes both
related BNNs and the proposed VNNs in a unified manner, and show that VNNs,
while being in the same group, as Monte Carlo Dropout (MCD) [5] and Bayes By
Backprop (BBB) [4] from the Bayesian Model Averaging (BMA) perspective,
achieve better uncertainty quality and retain it with the increasing data
dimensionality.

##  II Bayesian Neural Networks

BNNs [1, 2, 3] consider a distribution over their weights $p(w|a)$ and a
distribution over their hyperparameters $p(a)$. A predictive distribution over
an output $y$ for a data point $x$ can be obtained by integrating over all
possible hyperparameters and model weights, i.e.:

$p(y|x)=\int\int p(y|x,w)\>p(w|a)\>p(a)\>da\>dw.$ (1)

Given a dataset $D=(X_{t},Y_{t})$, where $X_{t}$ and $Y_{t}$ are the sets of
inputs $\\{x\\}$ and targets $\\{y\\}$, the distribution of weights can be
derived from Bayes’ theorem as $p(w|D,a)=\frac{p(Y_{t}|X_{t},w)p(w|a)}{p(D)}$,
and the corresponding predictive distribution has a form

$p(y|x,D)=\int\int p(y|x,w)\>p(w|D,a)\>p(a)\>da\>dw.$ (2)

Classical neural networks can be viewed as BNNs with $p(a)=\delta(a-\hat{a})$
and $p(w|D,a)=\delta(w-\hat{w}_{a})$ [3], where $\hat{a}$ are the selected
model hyperparameters, $\hat{w_{a}}$ are the weights, optimized by training
the model, and $\delta(x)$ is the Dirac delta function which has values $0$
everywhere except at $x=0$ where it equals to 1. In this case, the predictive
distribution becomes

$\displaystyle\begin{split}p(y|x,D)&=\int\int
p(y|x,w)\>p(w|D,a)\>p(a)\>da\>dw,\\\ &=\int\int
p(y|x,w)\>\delta(w-\hat{w}_{a})\>\delta(a-\hat{a})\>da\>dw,\\\
&=p(y|x,\hat{w}_{\hat{a}}),\\\ \end{split}$ (3)

which is a distribution dictated by a loss of the network.

When training classical neural networks, hyperparameters are considered fixed
at point $\hat{a}$ and weights are optimized either by maximum likelihood
estimation (MLE), i.e.:

$\displaystyle\begin{split}w_{\mathrm{mle}}&=\underset{w}{\mathrm{argmax}}\Big{[}\log\,p(D|w,\hat{a})\Big{]}\\\
&=\underset{w}{\mathrm{argmax}}\left[\sum_{i}\log\,p(Y_{i}|X_{i},w,\hat{a})\right],\end{split}$
(4)

or by maximum a posteriori (MAP), i.e.:

$\displaystyle\begin{split}w_{\mathrm{map}}&=\underset{w}{\mathrm{argmax}}\Big{[}\log\,p(w|D,\hat{a})\Big{]}\\\
&=\underset{w}{\mathrm{argmax}}\Big{[}\log\,p(D|w,\hat{a})+\log\,p(w)\Big{]},\end{split}$
(5)

where $\log\,p(w)$ is a regularization term.

Due to the complexity of neural networks, direct computation of
$w_{\mathrm{mle}}$ or $w_{\mathrm{map}}$ cannot be achieved, and therefore
approximate methods are used to find these values. The most popular process to
estimate the weight values is the Backpropagation algorithm [11], where an
initial randomly selected $w$ is updated following the direction of negative
gradient of the loss function with respect to $w$.

##  III Related Works

The use of BNNs in real-world applications is limited due to the complex
nature of the possible prior and predictive distributions. Therefore,
simplified versions are used. Assumptions that are proposed in different
methods below aim to reduce memory, inference and training time, but they come
with the cost of reducing the statistical quality of the resulting models.
This problem is further discussed in Section VI.

MCD [5] considers a neural network with Dropout [12] added to each layer. The
Dropout layer effectively turns off random neurons of the layer by multiplying
connection weights with a random binary mask, sampled from a Bernoulli
distribution. This allows to avoid overfitting specific neurons. After
training, Dropout is replaced by an identity function and all neurons are used
for inference. Instead of replacing Dropout with identity, MCD uses it during
inference leading to a stochastic model. The model uncertainty for an input is
computed by performing inference multiple times and computing mean and
variance of predictions. BBB [4] samples model parameters from a Gaussian
distribution and trains it using regular Backpropagation. By doing so, the
family of models with different weights is sampled from the learned
distribution, and the uncertainty of the network is computed as the variation
in predictions of different samples.

Ensembles of neural networks [6] can also be used for uncertainty estimation.
Ensembles are trained in parallel for the same task, but with different random
seeds, which results in different weight initialization and training order.
Outputs from members of an ensemble will vary, and this can be used to improve
performance by taking an average of their predictions, or to estimate
uncertainty by computing the variance of their outputs. Such an approach can
be viewed as a BNN with a categorical distribution over weights that randomly
selects one of the trained model weights. Hypermodels [13] use an additional
model $\theta=g_{\nu}(\mathbf{z})$ to generate parameters for a base model
$f_{\theta}(x)$. Linear Hypermodels set
$g_{\nu}(\mathbf{z})=a+B\mathbf{z},\>\>\mathbf{z}\sim\mathcal{N}(0,I)$. Using
different samples of $\mathbf{z}$, one can sample different model parameters
and estimate uncertainty in the same way as for the aforementioned methods.

##  IV Variational Neural Networks

As introduced in Section II, a neural network is described by its weights $w$
and hyperparameters $\alpha$. Hyperparameters include the structure of the
network, i.e., the type and number of layers, their size and connections, etc.
Usually, we limit the hyperparameters by defining some of them in the
beginning, e.g., by selecting that we want to use a Convolutional Neural
Network (CNN). This is a reasonable approach, as it is not practical to
iterate through all possible types and structures of networks during training.
We are using the neural network formulation
$\mathrm{NN}(x):=F^{\Lambda}(x,w)$, where $\mathrm{NN}(x)$ is a neural network
applied to an input $x$, $w$ are the trained weights, $F$ is a neural network
function that incorporates structure and other hyperparameters inside it, and
$\Lambda$ is a set of layer implementations, which are used by $F$ to process
layer inputs.

In case of CNNs, $\Lambda=\\{\mathrm{Conv2D}(x,w),\mathrm{FC}(x,w)\\}$ results
in a regular CNN, where $\mathrm{Conv2D}(x,w)$ is a 2D convolutional layer
function and $\mathrm{FC}(x,w)$ is a fully connected layer function. If we
select
$\Lambda=\\{\mathrm{Conv2D}(x,w_{c}\sim\mathcal{N}(\mu_{c},\Sigma_{c})),\mathrm{FC}(x,w_{l}\sim\mathcal{N}(\mu_{l},\Sigma_{l}))\\}$
with layer weights sampled from a corresponding Gaussian distribution, then
the resulting network is a BBB CNN. Such neural network formulation allows to
accurately describe all the discussed uncertainty estimation methods, as well
as the proposed VNNs.

###  IV-A Variational Layer

We define a Variational Layer (VL) that takes an input $x$ and weights $w$ as

$\displaystyle\begin{split}&\mathrm{VL}(x,w)=\alpha_{\mathcal{N}}(f(x,w)),\\\
&f(x,w)\sim\mathcal{N}\Big{(}\alpha_{\mu}(L(x,\mu)),diag[(\alpha_{\sigma}(L(x,\sigma)))^{2}]\Big{)},\\\
&w=(\mu,\sigma),\end{split}$ (6)

where $L(x,w)$ is a regular neural network layer, such as fully connected,
convolutional or a recurrent layer. $L(x,\mu)$ and $L(x,\sigma)$ represent
instances of the same layer with different values of parameters and
corresponding activation functions $\alpha_{\mu}(\cdot)$ and
$\alpha_{\sigma}(\cdot)$. The activation function
$\alpha_{\mathcal{N}}(\cdot)$ can be used to apply nonlinearity to the
randomly sampled values $f(x,w)$. By selecting which of $\alpha_{\mu}(\cdot)$,
$\alpha_{\sigma}(\cdot)$, $\alpha_{\mathcal{N}}(\cdot)$ are set to identity
and which are set to actual activation functions (such as the Rectified Linear
Unit (ReLU)) one can create networks that are described by different
mathematical models. In the following, we show how different selections can
lead to specific types of uncertainties, i.e. epistemic and aleatoric
uncertainties [14].

###  IV-B Epistemic uncertainty

Fully connected and convolutional layers can be described as the operation
$L(x,\lambda)=W_{\lambda}x+b_{\lambda}$, where
$\lambda=(W_{\lambda},b_{\lambda})$, $W_{\lambda}$ and $b_{\lambda}$ are
weights and biases of the layer, and a corresponding activation function
$\alpha_{\lambda}(\cdot)$ can be applied to the output of $L(x,\lambda)$.

Applying this formulation of a layer to a Variational Layer, together with
selecting inner activations $\alpha_{\mu}(\cdot)$ and $\alpha_{\sigma}(\cdot)$
to be identity functions, i.e., $\alpha_{\mu}(L(x,\mu))=W_{\mu}x+b_{\mu}$ and
$\alpha_{\sigma}(L(x,\sigma))=W_{\sigma}x+b_{\sigma}$, the VL can be
reformulated as

$\displaystyle\begin{split}\mathrm{VL}(x,w)&=\alpha_{\mathcal{N}}(f(x,w)),\\\
f(x,w)&\sim\mathcal{N}(W_{\mu}x+b_{\mu},\textrm{diag}[(W_{\sigma}x+b_{\sigma})^{2}]),\\\
w&=(\mu,\sigma).\end{split}$ (7)

Using the reparametrization trick [15] we can write $f(x,w)$ as

$\displaystyle\begin{split}\epsilon&\sim\mathcal{N}(0,I),\\\
f(x,w)&=W_{\mu}x+b_{\mu}+diag[(W_{\sigma}x+b_{\sigma})^{2}]\>\epsilon,\\\
&=(W_{\mu}+diag[W^{2}_{\sigma}]\epsilon)x+(b_{\mu}+diag[b^{2}_{\sigma}]\epsilon),\\\
&=Wx+b,\\\ W&\sim\mathcal{N}(W_{\mu},diag[W^{2}_{\sigma}]),\\\
b&\sim\mathcal{N}(b_{\mu},diag[b^{2}_{\sigma}]).\\\
w&=(\mu,\sigma).\end{split}$ (8)

This means that a Variational Layer with inner activations ($\alpha_{\mu}$,
$\alpha_{\sigma}$) set to identity is identical to a regular layer with a
distribution over weights, which is a BBB [4] layer. However, in this case,
the distributions for $W$ and $b$ are not independent, as they both come from
the same draw of the random variable $\epsilon$, which makes such VNN a
statistically degraded version of BBB due to a stricter limit on the weight
distribution.

###  IV-C Aleatoric uncertainty

Consider a Variational Layer with
$L(x,\sigma)=\Sigma,\>\>\Sigma\in\mathbb{R}$, which can be directly achieved
by setting $W_{\sigma}=0,\>\>b_{\sigma}=\Sigma$ and setting the corresponding
activation function $\alpha_{\sigma}(\cdot)$ to identity. Using the same idea
as in (8), we can write $f(x)$ as

$\displaystyle\begin{split}\epsilon&\sim\mathcal{N}(0,I),\\\
f(x)&=\alpha_{\mu}(W_{\mu}x+b_{\mu})+\Sigma\epsilon=L(x,\mu)+\epsilon_{\sigma},\\\
\epsilon_{\sigma}&\sim\mathcal{N}(0,\Sigma I).\end{split}$ (9)

In this formulation, $\epsilon_{\sigma}$ represents aleatoric uncertainty.
Depending on the choice of weights and nonlinearities, the VL formulation can
be simplified to a one that is described by either epistemic uncertainty
(Section IV-B) or aleatoric uncertainty. This means, that without those
simplifications, each Variational Layer incorporates both uncertainties.

###  IV-D Relation between VNNs and BNNs

BNNs consider a distribution over hyperparameters and weights, but the
hyperparameters are usually set to a fixed point using a Dirac delta
distribution to simplify the model, and the distribution over the weights is
selected to be a relatively simple one, like the Bernoulli, Gaussian or
Categorical distributions. VNNs do not consider a distribution over weights or
hyperparameters (excluding the simplified VNN layers described in Section
IV-B) and, therefore, VNNs are as close to BNNs as classical neural networks,
which means that VNNs cannot be called Bayesian Neural Networks in a regular
meaning of it. However, both BNNs and VNNs can be used to estimate
uncertainties and can be formulated in a unified manner, which is shown in the
next Section.

##  V Output uncertainty estimation

Following [16], we consider a neural network $F(x,w)$ with a parametric
distribution over weights $q_{m}(w)$. We assume the choice of $q_{m}(w)$ in a
form

$w=Q(m,z),\>\>\>\>\>\>\>\>w\sim q_{m}(w),\>\>\>\>\>\>\>\>z\sim p(z),$ (10)

where $p(z)$ is a non-parametric distribution and $Q(\cdot)$ applies a
deterministic transformation, parametrized by $m$, to a non-parametric random
variable $z$. Such formulation is suitable for every uncertainty estimation
method described in Section III. For BBB models, $Q(\cdot)$ is defined as

$Q(m,z)=\mu+\sigma^{2}z,\>\>\>\>\>\>\>\>z\sim\mathcal{N}(0,I),\>\>\>\>\>\>\>\>m=(\mu,\sigma),$
(11)

where we break down a parametric Gaussian distribution $\mathcal{N}(\mu,\sigma
I)$ into two parts: a parametric deterministic transformation
$z\longrightarrow\mu+\sigma^{2}z$ and a non-parametric random variable
$z\sim\mathcal{N}(0,I)$.

Defining an epistemic index $z\sim p(z)$ [16], we can formulate a
deterministic neural network $F_{d}(\cdot)$ function that takes a draw of a
random non-parametric variable $z$, instead of using $F(\cdot)$ with a complex
distribution over $w$:

$F_{d}(x,m,z):=F(x,w),\>\>\>\>\>\>\>\>w=Q(m,z),\>\>\>\>\>\>\>\>z\sim p(z)$
(12)

With this formulation, a predictive distribution (2) for fixed hyperparameters
is defined as

$\displaystyle\begin{split}p(y|x,D)&=\int p(y|x,w)\>q_{m}(w|D)\>dw=\int
p(y|x,m,z)\>p(z)\>dz,\\\ \mathbb{E}[y]&=\int
y\,p(y|x,D)dy\approx\frac{1}{T}\sum^{T}_{i}F_{d}(x,m,z_{i}),\\\
\mathrm{Cov}[y]&=\int(y-E[y])(y-E[y])^{T}p(y|x,D)\>dy,\\\
&\approx\frac{1}{T}\sum^{T}_{i}(E[y]-F_{d}(x,m,z_{i}))(E[y]-F_{d}(x,m,z_{i}))^{T}.\end{split}$
(13)

Expectation and variance are computed using Monte Carlo integration, which can
be viewed as an approximation of $p(z)$ with
$\sum^{T}_{i=0}\frac{\delta(z-z_{i})}{T},\>\>z_{i}\sim
p(z),\>\>i\in{1,\dots,T}$ [2]. Variance of the outputs is computed by taking
main diagonal values of the $\mathrm{Cov}[y]$ representing the uncertainty of
the model.

VNNs, despite not having a direct distribution over weights, can also be
formulated as a deterministic function $F_{d}(x,w,z)$ with a variational index
$z\sim p(z)$. In case of identity inner activations transforms into an
epistemic index, and in case of constant $L(x,\sigma)$ transforms into an
aleatoric index. Otherwise, it is an index of a distribution that combines
both aleatoric and epistemic uncertainties. Predictive distribution,
expectation and variance for these cases are the same as in (13).

##  VI Uncertainty quality estimation experiments

A recently proposed framework called Epistemic Neural Networks [16] aims to
provide a possibility to rank BNNs based on their ability to accurately
estimate output uncertainty. This is done by first generating a synthetic
dataset $D_{T}=\\{(x,y)_{t}$ for $t\in[0,T-1]\\}$ for a simple regression task
$y=f(x)+\epsilon$, where y is an output scalar, $x$ is an input data point
with $D_{x}$ number of dimensions, $\epsilon$ is a random variable sampled
from a Gaussian distribution $\mathcal{N}(0,{\sigma}^{2})$ representing an
aleatoric uncertainty. The dataset size $T$ is computed as $T=D_{x}\lambda$,
meaning that with a higher dimensionality of $x$, the number of data points
also increases.

The dataset is used to train a Neural Network Gaussian Process (NNGP) [17] and
an uncertainty estimation model of interest. NNGP serves as an ideal
probabilistic model for this data and a predictive distribution of a selected
uncertainty estimation model should be as close as possible to the predictive
distribution of the NNGP model. An additional dataset is used to evaluate the
difference between those distributions by computing the KL-divergence between
the true posterior $\mathcal{N}(\mu_{\mathrm{GP}},k_{\mathrm{GP}})$ and a
model predictive distribution $\mathcal{N}(\mu_{B},k_{B})$. Lower values of
KL-divergence represent better uncertainty quality for a selected model, and
therefore can be used to rank different approaches for uncertainty estimation.

We implement VNNs inside the ENN’s JAX implementation [18] to reproduce
results for BBB [4], MCD [5], Ensemble [6], Hypermodel [13] and compare them
with VNN. We follow the original framework parameters and repeat experiments
with the following options: $D_{x}\in\\{10,100,1000\\}$,
$\lambda\in\\{1,10,100\\}$, and $\epsilon\in\\{0.01,0.1,1\\}$. Each model is
trained with 10 different random seeds, and the resulting KL value is the
average of individual runs. The average KL values across all experiment
parameters are given in Fig. 1(a) and for the highest input dimension value
$D_{x}=1000$ are given in Fig. 1(b).

(a) All parameters

(b) $D_{x}=1000$

Figure 1: Comparison of mean KL value with 1 STD range for each method
averaged across different experiment parameters.

VNN has better uncertainty quality than BBB and MCD, but it is outperformed by
Hypermodel and Ensemble. This can be explained by the difference in BMA for
Deep Ensembles and Variation Inference methods, as explained in [2]. The
weight probability distribution can be split into basins, where models sampled
from the same basin are too similar and will describe the problem from the
same point of view, resulting in multiple entries of actually identical model
in the prediction voting. Deep Ensembles and Hypermodels avoid this problem by
not having a single anchor point with small weight deviations, and therefore
having high chances of converging trained models into different basins. This
means that VNN has a higher chance than Ensemble to have its samples in a
single basin, placing it in the same group as BBB and MCD. Additionally, with
bigger data dimensionality $D_{x}$, MCD and BBB achieve worse results, while
VNN, Ensemble and Hypermodel perform better, as can be seen by comparing
results in Figs. 1(a) and 1(b).

##  VII Image classification experiments

We train the same methods, as in Section VI for image classification tasks on
MNIST [19] and CIFAR-10 [20] datasets. To show the influence of model
architecture on the performance, we use a set of architectures $\\{F_{i}\\}$
and train each method with the selected architecture $F$. We select a Base
architecture to have 3 convolutional and 1 fully connected layers for MNIST,
and 6 convolutional and 1 fully connected layers for CIFAR-10. Mini and Micro
Base architectures have the same layer structure as the Base one, but a lower
number of channels in each layer. MLP architecture consists of 3 fully
connected layers. We also use Resnet-18 [21] architecture for experiments on
CIFAR-10. For each method, we train models with different hyperparameter
values and select the best two models for comparison. The results of
classification experiments are given in Fig. 2 and are roughly following the
results of uncertainty quality estimation experiments.

Figure 2: Comparison of classification accuracy for each method on MNIST and
CIFAR-10 datasets with different model architectures. The best two models of
each method are shown in each subfigure.

##  VIII Conclusions

In this work, we proposed a method for neural network uncertainty estimation
called Variational Neural Networks and evaluated its quality within the
Epistemic Neural Networks framework. Experiments show that, despite having
similar properties of Bayesian Model Averaging as Monte Carlo Dropout and
Bayes By Backpropagation, where sampled models are close, compared to
Ensembles and Hypermodels, resulting in similar models’ points of view, VNNs
achieve better uncertainty quality, which is retained when data dimensionality
is increased, in contrast to Monte Carlo Dropout and Bayes By Backpropagation
methods.

## Acknowledgment

We thank Dr. Martin Magris for helpful discussions and feedback.

## References

  * [1] D. J. C. Mackay, “Probable networks and plausible predictions — a review of practical bayesian methods for supervised neural networks,” _Network: Computation in Neural Systems_ , vol. 6, no. 3, pp. 469–505, 1995.
  * [2] A. G. Wilson and P. Izmailov, “Bayesian Deep Learning and a Probabilistic Perspective of Generalization,” _arXiv:2002.08791_ , 2020.
  * [3] T. Charnock, L. Perreault-Levasseur, and F. Lanusse, “Bayesian neural networks,” _arXiv:2006.01490_ , 2020.
  * [4] C. Blundell, J. Cornebise, K. Kavukcuoglu, and D. Wierstra, “Weight Uncertainty in Neural Networks,” _arXiv:1505.05424_ , 2015.
  * [5] Y. Gal and Z. Ghahramani, “Dropout as a bayesian approximation: Representing model uncertainty in deep learning,” _arxiv:1506.02142_ , 2016.
  * [6] I. Osband, J. Aslanides, and A. Cassirer, “Randomized prior functions for deep reinforcement learning,” _arXiv:1806.03335_ , 2018.
  * [7] W. K. Hastings, “Monte Carlo sampling methods using Markov chains and their applications,” _Biometrika_ , vol. 57, no. 1, pp. 97–109, 1970.
  * [8] D. M. Blei, A. Kucukelbir, and J. D. McAuliffe, “Variational inference: A review for statisticians,” _Journal of the American Statistical Association_ , vol. 112, no. 518, pp. 859–877, 2017.
  * [9] S. Kullback and R. A. Leibler, “On Information and Sufficiency,” _The Annals of Mathematical Statistics_ , vol. 22, no. 1, pp. 79 – 86, 1951.
  * [10] M. Hoffman, D. M. Blei, C. Wang, and J. Paisley, “Stochastic variational inference,” _arxiv:1206.7051_ , 2012.
  * [11] H. J. Kelley, “Gradient theory of optimal flight paths,” _Ars Journal_ , vol. 30, no. 10, pp. 947–954, 1960.
  * [12] N. Srivastava, G. Hinton, A. Krizhevsky, I. Sutskever, and R. Salakhutdinov, “Dropout: A simple way to prevent neural networks from overfitting,” _Journal of Machine Learning Research_ , vol. 15, no. 56, pp. 1929–1958, 2014\.
  * [13] V. Dwaracherla, X. Lu, M. Ibrahimi, I. Osband, Z. Wen, and B. V. Roy, “Hypermodels for exploration,” _arXiv:2006.07464_ , 2020.
  * [14] A. Kendall and Y. Gal, “What uncertainties do we need in bayesian deep learning for computer vision?” in _Advances in Neural Information Processing Systems_ , vol. 30. Curran Associates, Inc., 2017.
  * [15] D. P. Kingma and M. Welling, “Auto-encoding variational bayes,” _arXiv:1312.6114_ , 2014.
  * [16] I. Osband, Z. Wen, M. Asghari, M. Ibrahimi, X. Lu, and B. V. Roy, “Epistemic Neural Networks,” _arXiv:2107.08924_ , 2021.
  * [17] J. Lee, Y. Bahri, R. Novak, S. S. Schoenholz, J. Pennington, and J. Sohl-Dickstein, “Deep neural networks as gaussian processes,” _arXiv:1711.00165_ , 2018.
  * [18] I. Osband, Z. Wen, M. Asghari, M. Ibrahimi, X. Lu, and B. V. Roy, “Github code for epistemic neural networks,” 2021.
  * [19] L. Deng, “The mnist database of handwritten digit images for machine learning research,” _IEEE Signal Processing Magazine_ , vol. 29, no. 6, pp. 141–142, 2012.
  * [20] A. Krizhevsky, “Learning multiple layers of features from tiny images,” Tech. Rep., 2009.
  * [21] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” _arXiv:1512.03385_ , 2015.