# Triangles and Vitali sets1112020 AMS subject classification 03E35, 14P99,
05C15.

Jindřich Zapletal
University of Florida
<EMAIL_ADDRESS>
###### Abstract

It is consistent relative to an inaccessible cardinal that ZF+DC holds, the
hypergraph of equilateral triangles in Euclidean plane has countable chromatic
number, while there is no Vitali set.

##  1 Introduction

Classification of analytic graphs and hypergraphs from various points of view
is a subject matter frequently discussed in descriptive set theory and
descriptive combinatorics. Geometric set theory adds its own angle:
independence results in ZF+DC choiceless set theory regarding the existence of
various structures (e.g., colorings or perfect matchings) related to analytic
(hyper)graphs. One can consider for example the following broad question:

######  Question 1.1.

For which analytic hypergraphs $\Gamma$ on Polish spaces is it consistent with
ZF+DC that $\Gamma$ has countable chromatic number and no Vitali set exists?

Note that existence of Vitali set is equivalent in ZF+DC to the countable
chromatic number of the Vitali equivalence relation on $\mathbb{R}$. [8,
Chapter 11] contains various results in this direction for locally countable
graphs and hypergraphs. Difficulties quickly mount when one steps out of the
locally countable realm. As one interesting and traditional class of cases,
the algebraic graphs and hypergraphs on Euclidean spaces are combinatorially
quite complex, but none of them seem to have any relationship with the Vitali
equivalence relation. In an encouraging development, the question has been
resolved in the affirmative for all algebraic graphs $\Gamma$ containing no
perfect clique [9]. In this paper, I resolve a quite special case in arity
three, which requires several additional ideas.

######  Definition 1.2.

Let $\langle X,\cdot\rangle$ be a standard Borel abelian group. A hypergraph
$\Gamma$ of arity three on $X$ is a _slim linear hypergraph_ if there are
Borel homomorphisms $g_{0},g_{1},g_{2}\colon X\to X$ such that

  1. 1.

all of $g_{0},g_{1},g_{2}$ and $g_{0}+g_{1}$, $g_{1}+g_{2}$, and $g_{0}+g_{2}$
are injections;

  2. 2.

$\Gamma$ is the set of all triples $\\{x_{0},x_{1},x_{2}\\}$ of pairwise
distinct points such that under suitable enumeration,
$g_{0}(x_{0})+g_{1}(x_{1})+g_{2}(x_{2})=0$.

In most interesting cases, the sum $g_{0}+g_{1}+g_{2}$ is equal to the zero
homomorphism, and then the hypergraph $\Gamma$ will be invariant under
translations. Slim linear hypergraphs carry geometric meaning:

######  Example 1.3.

Let $c\in\mathbb{C}$ be a non-real complex number, and consider the hypergraph
on $\mathbb{C}$ given by the arithmetic identity
$c\cdot(x_{1}-x_{0})=x_{2}-x_{0}$. It is the set of all triangles in the
complex plane directly similar to the triangle with vertices $0,1,c$.

######  Theorem 1.4.

Let $\langle X,+\rangle$ be a standard Borel abelian group, and let $\Gamma$
be a finite union of slim linear hypergraphs of arity three on $X$. Then in a
balanced forcing extension of the choiceless Solovay model, the following
items hold:

  1. 1.

ZF+DC holds and $\Gamma$ has countable chromatic number;

  2. 2.

there is no Vitali set;

  3. 3.

there is no complete countable section for the $\mathbb{E}_{1}$ equivalence
relation.

######  Corollary 1.5.

Relative to an inaccessible cardinal, it is consistent with ZF+DC that the
hypergraph of equilateral triangles in $\mathbb{R}^{2}$ has countable
chromatic number, yet there is no Vitali set.

The theorem understates the understanding of the resulting model. In
particular, I prove that a certain graph simpler than the Vitali equivalence
relation–the diagonal Hamming graph–has uncountable chromatic number in the
resulting model.

In a number of natural cases, I can show that it is not entirely easy to color
slim linear hypergraphs. No such coloring will appear in a compactly balanced
forcing extension of the choiceless Solovay model as per the following
theorem. The broad class of compactly balanced forcings was introduced in [6,
Section 9.3]; it includes in particular the poset for adding a Ramsey
ultrafilter, or the poset for adding a linear ordering of a quotient space of
any Borel equivalence relation.

######  Theorem 1.6.

Let $\langle X,+\rangle$ be a Polish abelian group, let $n\geq 3$ be a number,
and let $g_{i}\colon X\to X$ for $i\in n$ be continuous homomorphisms such
that

  1. 1.

$\Sigma_{i\in n}g_{i}=0$;

  2. 2.

every open neighborhood of $0$ in $X$ contains pairwise distinct nonzero
points $x_{i}$ for $i\in n$ such that $\Sigma_{i\in n}g_{i}(x_{i})=0$.

Then, in every compactly balanced extension of the choiceless Solovay model,
the hypergraph $\Gamma$ on $X$ consisting of all tuples $\\{x_{i}\colon i\in
n\\}$ of pairwise distinct elements of $X$ such that $\Sigma_{i\in
n}g_{i}(x_{i})=0$ has uncountable chromatic number.

######  Corollary 1.7.

Relative to an inaccessible cardinal, it is consistent with ZF+DC that there
is a non-principal ultrafilter on $\omega$, yet the hypergraph of equilateral
triangles in $\mathbb{R}^{2}$ has uncountable chromatic number.

There are many open questions left. Since the equilateral triangle hypergraph
in $\mathbb{R}^{3}$ is not linear, methods of this paper do not apply to it,
and it is the simplest algebraic hypergraph for which I do not know if its
countable chromatic number implies existence of a Vitali set in ZF+DC. I do
not know whether the chromatic number of the Kechris–Solecki–Todorcevic graph
$\mathbb{G}_{0}$ [5] is countable or uncountable in the resulting model.
Finally, one should be able to remove the inaccessible cardinal assumption
from the proof, but I have not done the footwork necessary for that.

The architecture of the paper is probably somewhat surprising to a reader who
is not familiar with the mysterious ways of geometric set theory [6]. In
Section 2, I define the central combinatorial tool of the paper: the remainder
graphs of a ternary hypergraph. This is an interesting object regardless of
any forcing considerations, and the main point of this paper is that in the
case of linear hypergraphs, the remainder graphs can be handled efficiently.
In Section 3, I define a couple of c.c.c. finite condition coloring posets for
various graphs and hypergraphs. A fine evaluation of their chain condition
situation is necessary to exclude the Vitali set in the model for Theorem 1.4.
This part of the paper is reminiscent of certain computations of Todorcevic
[7] regarding similar finite condition c.c.c. posets. In Section 4, I define a
$\sigma$-closed balanced poset $P$ adding a coloring of the hypergraph
$\Gamma$ of Theorem 1.4. The model for Theorem 1.4 is then a $P$-extension of
a choiceless Solovay model derived from an inaccessible cardinal. Section 5
then checks the properties of this model, using the remainder graphs and
c.c.c. coloring posets identified earlier. Finally, Section 6 shows that there
are natural algebraic hypergraphs for which in ZF countable chromatic number
has consequences contradicting the conclusion of Theorem 1.4.

The terminology of the paper follows the set theoretic standard of [3], in
matters of descriptive set theory that of [4], in matters of geometric set
theory that of [6]. $\mathbb{E}_{1}$ is the equivalence relation on the set
$\mathbb{R}^{\omega}$ connecting points $x,y$ if the set $\\{n\in\omega\colon
x(n)\neq y(n)\\}$ is finite. The _diagonal Hamming graph_
$\mathbb{H}_{<\omega}$ is the graph on the set of all functions
$x\in\omega^{\omega}$ such that $\forall n\ x(n)\leq n$, connecting points
$x,y$ if there is exactly one $n\in\omega$ such that $x(n)\neq y(n)$.
$\mathrm{HF}$ denotes the set of all hereditarily finite sets.

##  2 Remainder graphs

The consistency result depends on several combinatorial observations. The
first seems critical and irreplaceable in the argument, and its limitations
seem to be the main obstacle to natural generalizations of Theorem 1.4.
Consider the following definition.

######  Definition 2.1.

Let $\Gamma$ be a hypergraph on a Polish space $X$, and let $A\subset X$ be a
set. The _remainder graph_ is the graph $\Gamma_{A}$ on $X\setminus A$
connecting distinct points $x,y$ if there is $z\in A$ such that
$\\{x,y,z\\}\in\Gamma$ holds.

The most natural case of remainder graphs appears when $A$ is a suitably
algebraically closed subset of $X$, possibly uncountable. I will be interested
in the chromatic number of the remainder graphs. This looks like a completely
intractable issue, but some cases do allow for informative insight. Consider
the following examples.

######  Example 2.2.

Let $\Gamma$ be the hypergraph on $\mathbb{R}$ of all triples $\\{x,y,z\\}$ of
pairwise distinct elements which (in some ordering) satisfy the identity
$x-2y+z=0$. Let $A\subset\mathbb{R}$ be a subfield. Then the remainder graph
contains no circuits of odd length, and it contains an
$|A|\times|A|$-biclique.

###### Proof.

First, I will show that there are no circuits of odd length in the remainder
graph. For this, consider the group $G$ of all non-constant linear functions
from $\mathbb{R}$ to itself with the composition operation, acting on
$\mathbb{R}$ by application. For each such a function $g(u)=au+b$, call $a$
the _slope_ of the function. The slope function is obviously a homomorphism
from the group $G$ to the multiplicative group of nonzero real numbers. Each
element of $G$ except for the identity has at most one fixed point.

Now, let $n\in\omega$ be a number and $\langle x_{i}\colon i\leq n\rangle$ be
a path in the remainder graph with $x_{n}=x_{0}$; I must show that $n$ is
even. To this end, for each $i\in n$ find $z_{i}\in V$ such that
$\\{x_{i},x_{i+1},z_{i}\\}\in\Gamma$. There are three possible mutually
exclusive cases how this can occur:

  * •

$x_{i}-2x_{i+1}+z_{i}=0$. In this case, let $g_{i}\colon X\to X$ be the
function defined by $g_{i}(u)=(u+z_{i})/2$;

  * •

$x_{i}-2z_{i}+x_{i+1}=0$. In this case, let $g_{i}\colon X\to X$ be the
function defined by $g_{i}(u)=2z_{i}-u$;

  * •

$z_{i}-2x_{i}+x_{i+1}=0$. Here, let $g_{i}(u)=2u-z_{i}$.

All the functions $g_{i}$ for $i\in n$ are coded in $F_{0}$, and
$g_{i}(x_{i})=x_{i+1}$. The composition of all the elements $g_{i}\in G$ for
$i\in n$ is a linear function coded in $A$, and it has $x_{0}\notin A$ as a
fixed point, therefore it has to be the identity. Now consider the slopes of
the functions $g_{i}$: in the first case, it is $1/2$, in the second case, it
is $-1$, in the third case, it is $2$. The product has to give $1$, the slope
of the identity. Thus, the first and third case must be used equal number of
times, and the second case must be used even number of times. In conclusion,
$n$ is even as desired.

Now, to produce the required biclique in the remainder graph, let
$B_{0},B_{1}\subset A$ be disjoint sets of reals of cardinality $|A|$. Let
$\varepsilon>0$ be a real number in $\mathbb{R}\setminus A$. Consider the set
$C_{0}=B_{0}+\varepsilon$ and the set $C_{1}=(B_{1}+\varepsilon)/2$. These are
disjoint subsets of $\mathbb{R}\setminus A$, and they form an $|A|\times|A|$
bi-clique in the remainder graph. To see this, let $x_{0}\in B_{0}$ and
$x_{1}\in B_{1}$ be points. Then
$(x_{0}+\varepsilon)-(2(x_{1}+\varepsilon)/2)=x_{0}-x_{1}\in A$, so
$\\{x_{0}+\varepsilon,(x_{1}+\varepsilon)/2,x_{0}-x_{1}\\}\in\Gamma$ and
$x_{0}+\varepsilon,(x_{1}+\varepsilon)/2$ are connected in the remainder graph
as desired. ∎

######  Example 2.3.

Let $\Gamma$ be the hypergraph of equilateral triangles in $\mathbb{R}^{3}$.
Let $F$ be any real closed subfield of $\mathbb{R}$ properly smaller than
$\mathbb{R}$, and let $A=F^{3}$. Then in the remainder graph, one can find a
triangle. Just let $\varepsilon>0$ be a real number $\mathbb{R}\setminus F$,
let $z\in A$ be an arbitrary point, and find any regular tetrahedron with one
vertex equal to $z$ and length of all sides equal to $\varepsilon$. The other
three vertices cannot belong to $A$ since together with $z$ each of them
computes $\varepsilon$, and they form a triangle in the remainder graph.

######  Example 2.4.

Let $\Gamma$ be the hypergraph of isosceles triangles on $\mathbb{R}^{2}$. Let
$F$ be any real closed subfield of $\mathbb{R}$ properly smaller than
$\mathbb{R}$, and let $A=F^{3}$. Then the remainder graph contains a perfect
clique. To see this, let $\varepsilon>0$ be a real number which is not in $F$,
and let $z\in A$ be an arbitrary point. Consider the set $C$ of all points in
$\mathbb{R}^{2}$ which are at a distance $\varepsilon$ from $z$. It is
immediate to see that $C$ contains no points from $A$ (since every point in
$C$ together with $z$ computes $\varepsilon$) and $C$ is a clique in the
remainder graph.

Finally, we get to the hypergraph of immediate interest to the present paper.

######  Definition 2.5.

Let $\langle X,+\rangle$ be a standard Borel abelian group. Let
$\Gamma=\bigcup_{i\in n}\Gamma_{i}$ be a finite or countable union of slim
linear hypergraphs of arity three, for $n\leq\omega$. Let $\Gamma_{i}$ be
generated by continuous homomorphisms $g_{j}^{i}$ for $j\in 3$. A set
$A\subset X$ is $\Gamma$-closed if it is a subgroup of $X$, it is closed under
each homomorphism $g_{j}^{i}$ and its inverse for $i\in n$ and $j\in 3$, and
also closed under the inverses of the homomorphisms $g_{j}^{i}+g_{k}^{i}$ for
$i\in\omega$ and $j,k$ distinct indices in $3$.

Note that all the homomorphisms mentioned in the above definitions are
injective per the definition of a slim linear hypergraphs, so their inverses
are well-defined partial functions. The definition of $\Gamma$-closed set
seems to depend on the choice of the decomposition of $\Gamma$ into slim
hypergraphs and their generating homomorphisms; I will keep such decomposition
and its generating homomorphisms always fixed. In this way, every infinite
subset of $X$ has a smallest $\Gamma$-closed superset which is of the same
cardinality, and an increasing union of $\Gamma$-closed sets is
$\Gamma$-closed.

######  Example 2.6.

Let $\langle X,+\rangle$ be a standard Borel abelian group. Let $\Gamma$ be a
finite (resp. countable) union of slim linear hypergraphs of arity three. Let
$A\subset X$ be a $\Gamma$-closed set. Then there is a homomorphism of the
remainder graph $\Gamma_{A}$ to a locally finite (resp. locally countable)
graph.

###### Proof.

et $\Gamma=\bigcup_{i\in n}\Gamma_{i}$ be a finite or countable union of slim
linear hypergraphs of arity three, for $n\leq\omega$. Let $\Gamma_{i}$ be
generated by continuous homomorphisms $g_{j}^{i}$ for $j\in 3$. Let $E$ be the
equivalence relation on $X\setminus A$ connecting distinct points
$x_{0},x_{1}$ if $x_{0}-x_{1}\in A$. Let $Y$ be the set of all $E$-classes,
and define the graph $\Theta$ on $Y$ which connects classes $c\neq d$ if there
are representatives $x\in c$ and $y\in d$ which are connected in the remainder
graph. I will show that that the graph $\Theta$ is locally finite (resp.
locally countable), and the map $f\colon X\to Y$, $f(x)=[x]_{E}$ is a
homomorphism of the remainder graph to $\Theta$.

To show that the map $f$ is a homomorphism, it is only necessary to show that
if distinct points $x_{0},x_{1}\in X\setminus A$ are connected in the
remainder graph, then they are not $E$-equivalent. Suppose towards a
contradiction that they are. Let $i\in n$ and $x_{2}\in A$ be such that
$g_{0}^{i}(x_{0})+g_{1}^{i}(x_{1})+g_{2}^{i}(x_{2})=0$, and let $y\in A$ be
such that $x_{0}+y=x_{1}$. Since $A$ is a subgroup of $X$ closed under the
homomorphisms, plugging in for $x_{1}$ it becomes clear that
$(g_{0}+g_{1})(x_{0})\in A$. Since $A$ is closed under the inverse of
$g_{0}+g_{1}$, it follows that $x_{0}\in A$, contradicting the initial choice
of $x_{0}$.

To show that the graph $\Theta$ is locally finite (resp. locally countable),
it will be enough to show that if $c,d,d^{\prime}$ are $E$-classes, $i\in n$
is an index, and there are points $x_{0},x^{\prime}_{0}\in c$, $x_{1}\in
d_{0}$, $x^{\prime}_{1}\in d^{\prime}$, and $x_{2},x^{\prime}_{2}\in A$ such
that $g^{i}_{0}(x_{0})+g_{1}^{i}(x_{1})+g_{2}^{i}(x_{2})=0$ and
$g^{i}_{0}(x^{\prime}_{0})+g_{1}^{i}(x^{\prime}_{1})+g_{2}^{i}(x^{\prime}_{2})=0$
both hold, then $d=d^{\prime}$. To see that, subtract the latter equality from
the former and get
$g^{i}_{0}(x_{0}-x^{\prime}_{0})+g^{i}_{1}(x_{1}-x^{\prime}_{1})\in A$. The
first summand here belongs to $A$ as $x_{0}\mathrel{E}x^{\prime}_{0}$ holds.
As $A$ is closed under the inverse of $g^{i}_{1}$, it follows that
$x_{1}-x^{\prime}_{1}\in A$ holds. Thus $d=d^{\prime}$ as desired. ∎

######  Corollary 2.7.

Let $\langle X,+\rangle$ be a standard Borel abelian group. Let $\Gamma$ be a
union of countably many slim linear hypergraphs of arity three on $X$.
Whenever $A\subset X$ is a $\Gamma$-closed set, the chromatic number of
$\Gamma(A)$ is countable.

One can use the chromatic number of remainder graphs to prove that the
chromatic number of $\Gamma$ itself is countable. In addition, the mechanics
of this proof will drive the consistency arguments in Section 5. For a
notational convenience, my (hyper)graph colorings of hypergraphs will often
have the countable set $\mathrm{HF}$ of hereditarily finite sets as a co-
domain.

######  Definition 2.8.

Let $\langle X,+\rangle$ be a Polish abelian group. Let $\Gamma$ be a
countable union of slim linear hypergraphs. A _coherent sequence of colorings_
is a tuple $\langle I,\leq,A_{i},c_{i},d_{i}\rangle$ where

  1. 1.

$\langle I,\leq\rangle$ be a linearly ordered set;

  2. 2.

$\langle A_{i}\colon i\in I\rangle$ is an inclusion-increasing sequence of
$\Gamma$-closed subsets of $X$;

  3. 3.

for every $x\in\bigcup_{i}A_{i}$, there is a smallest index $i\in I$ such that
$x\in A_{i}$;

  4. 4.

$c_{i}\colon A_{i}\to\mathrm{HF}$ is a $\Gamma$-coloring;

  5. 5.

if $i$ is the smallest element of $I$ then $d_{i}=0$; otherwise, write
$\Delta_{i}$ for the remainder graph $\Delta(\bigcup_{j<i}A_{j})$, and
$d_{i}\colon A_{i}\setminus\bigcup_{j<i}A_{j}\to\mathrm{HF}$ is a
$\Gamma_{\bigcup_{j<i}A_{j}}$-coloring.

Note that the linearly ordered set $I$ must have a smallest element, namely
the smallest $i$ such that $1\in F_{i}$. One way to satisfy item (3) is to
insist that $\leq$ is a well-ordering; however, I will have an opportunity to
use an ill-founded linear order as well.

######  Definition 2.9.

The _amalgamation_ of a coherent sequence $\langle
I,\leq,A_{i},c_{i},d_{i}\rangle$ of colorings is the function $e$ on
$\bigcup_{i}A_{i}$ defined as follows. For every $x\in\bigcup_{i}A_{i}$ find
the smallest $i\in I$ such that $x\in A_{i}$. If $i$ is the smallest element
of $I$, then let $e(x)=f_{i}(x)$; otherwise, let $e(x)=\langle
f_{i}(x),g_{i}(x)\rangle$.

Note that the amalgamation extends $f_{i}$ for the smallest element $i\in I$.

######  Proposition 2.10.

The amalgamation of a coherent sequence of colorings is a $\Gamma$-coloring.

###### Proof.

Let $\langle I,\leq,A_{i},c_{i},d_{i}\rangle$ be a coherent sequence of
colorings. Write $Y=\bigcup_{i}A_{i}$. For each $x\in X$ write $i(x)$ for the
least $i\in I$ such that $x\in A$. Let $e$ be the amalgamation of the
sequence. Let $a\subset X$ be a $\Gamma$-hyperedge and work to show that
$e\restriction a$ is not constant. Let $i$ be the $\leq$-largest element of
the finite set $\\{i(x)\colon x\in a\\}$. There are three configurations to
consider; their discussion completes the proof.

Case 1. There is exactly one point $x\in a$ such that $i(x)=i$. This is in
fact impossible, since the subgroup $\bigcup_{j<i}A_{j}$ is $\Gamma$-closed.

Case 2. There are exactly two points $x\in a$ such that $i(x)=i$. In this
case, these two points are $\Delta_{i}$-connected and they receive distinct
$d_{i}$-colors, as $d_{i}$ is a $\Delta_{i}$-coloring. In consequence, they
also receive distinct $e$-colors.

Case 3. All three points $x\in a$ have $i(x)=i$. In this case, $a$ is not
$c_{i}$-monochromatic, since $c_{i}$ is a $\Gamma$-coloring. As a result, $a$
is not $e$-monochromatic either. ∎

######  Corollary 2.11.

Let $\langle X,+\rangle$ be a Polish abelian group. Let $\Gamma$ be a
countable union of countably many slim linear hypergraphs of arity three on
$X$. The chromatic number of $\Gamma$ is countable.

###### Proof.

By induction on the cardinality of a $\Gamma$-closed set $A\subset X$ I will
argue that there is a $\Gamma$-coloring from $A$ to $\mathrm{HF}$. This is
clear if $|A|=\aleph_{0}$, since one can choose any injection as the coloring.
Suppose now that $\kappa$ is an uncountable cardinal, $|A|=\kappa$, and the
statement has been proved for all $\Gamma$-closed sets of cardinality smaller
than $\kappa$. Express $F=\bigcup_{\beta\in\alpha}F_{\beta}$ as an increasing
union of $\Gamma$-closed sets of cardinality smaller than $\kappa$. Use the
induction hypothesis to find a $\Gamma$-coloring $c_{\beta}\colon
A_{\beta}\to\mathrm{HF}$ and Example 2.6 to find a
$\Delta(\bigcup_{\gamma\in\beta}A_{\gamma})$-coloring $d_{\beta}\colon
A_{\beta}\setminus\bigcup_{\gamma\in\beta}A_{\gamma}\to\mathrm{HF}$, this for
every $\beta\in\alpha$. Let $c\colon A\to\mathrm{HF}$ be the amalgamation of
$\langle c_{\beta},d_{\beta}\colon\beta\in\alpha\rangle$. Proposition 2.10
confirms that this is a $\Gamma$-coloring, completing the induction step and
the proof. ∎

##  3 C.c.c. coloring posets

Another issue seemingly unrelated to the consistency result in question is the
possibility of forcing colorings of given (hyper)graphs by finite conditions.
If $\Gamma$ is a hypergraph on a set $X$ of countable chromatic number, there
may not be a coloring definable from $\Gamma$–this is the basic difficulty of
descriptive combinatorics. However, there still may be a definable poset
adding a coloring which has useful regularity properties. The poset I use in
this paper is the simplest one:

######  Definition 3.1.

Let $\Gamma$ be a hypergraph on a set $X$. The _finite approximation coloring
poset_ $R(\Gamma)$ is the poset of all partial finite colorings $p\colon
X\to\omega$, ordered by reverse inclusion.

The countable set used as the target of the colorings is of course immaterial;
I may use the set $\mathrm{HF}$ instead of $\omega$. The property of the
coloring posets critical for this paper is the following.

######  Definition 3.2.

Let $R$ be a poset.

  1. 1.

A set $A\subset R$ is _Ramsey-centered_ if for every $n\in\omega$ there is
$m\in\omega$ such that for every $m$-tuple $\langle r_{i}\colon i\in m\rangle$
of elements of $A$ there is a set $b\subset m$ of cardinality $n$ such that
the set $\\{r_{i}\colon i\in b\\}$ has a common lower bound in $R$.

  2. 2.

if $z$ is a set, then $R$ is $z$-_definably $\sigma$-Ramsey-centered_ if $R$
can be covered by an $\omega$-sequence of Ramsey-centered sets which is
defined from $z$

There are several situations in which I can show that the finite approximation
coloring poset is suitably definably Ramsey-centered. Some are exhibited in
[6, Section 11.6]. The cases I need in this paper are recorded in the
following two similar theorems with similar proofs.

######  Theorem 3.3.

Let $X$ be a set. Let $\Gamma$ be a hypergraph of arity three on $X$ such that
there is a number $d\in\omega$ such that for every $x_{0},x_{1}\in X$ the set
$\\{x_{2}\in X\colon\\{x_{0},x_{1},x_{2}\\}\in\Gamma\\}$ has cardinality at
most $d$. Then the finite approximation coloring poset for $\Gamma$ is
$X,\Gamma$-definably $\sigma$-Ramsey centered.

###### Proof.

Let $A_{kl}\subset R(\Gamma)$ be the set of all conditions whose domain has
cardinality $k\in\omega$ and the range is a subset of $l\in\omega$. It will be
enough to show that $A_{kl}$ is Ramsey-centered.

To this end, let $n\in\omega$ be a number. Increasing $n$ if necessary I may
assume that $n>d\cdot[2k]^{2}$ and $n>3l$. Let $m$ be a number such that
$m\to(n)^{3}_{9k+1}$. It will be enough to show that among any $m$ many
elements of $A_{i}$ one can find $n$ many with a common lower bound. To this
end, let $\\{p_{i}\colon i\in m\\}\subset A_{k}$ be a set. For each $i\in m$,
fix an enumeration $\\{x_{j}^{i}\colon j\in k\\}$ of its domain. Consider the
following map $f$ on $[m]^{3}$. If $u\in[m]^{3}$ is a set, let
$i_{0}<i_{1}<i_{2}$ be its elements in increasing order and define $f(u)$ by a
split into cases:

  * •

if there is an index $b\in 3$ and an index $j\in k$ such that $x_{j}^{i_{b}}$
belongs to at least one of $\mathrm{dom}(p_{i_{c}})$ for $c\neq b$ and it is
not equal to at least one $x_{j}^{i_{c}}$ for $c\neq b$, then the functional
value will be $f(u)=\langle 0,b,j\rangle$ for some such $b$ and $j$;

  * •

if the previous item fails and there are $b\in 3$ and $j\in k$ such that for
some $c\in 3$ distinct from $b$, $x_{j}^{i_{b}}=x_{j}^{i_{c}}$ and
$p_{i_{b}}(x_{j}^{i_{b}})\neq p_{i_{c}}(x_{j}^{i_{c}})$, then $f(u)=\langle
1,b,j\rangle$ for some such $b,j$;

  * •

if the previous items fail and there are $b\in 3$ and $j\in k$ such that there
is a hyperedge $e\in\Gamma$ which is contained in $\bigcup_{i\in
u}\mathrm{dom}(p_{i})$ and such that $x_{j}^{i_{b}}$ is the only element of
$e$ which is not in $\mathrm{dom}(p_{i_{c}})$ for any $c\neq b$, then let
$f(u)=\langle 2,b,j\rangle$ for some such $b,j$;

  * •

if all of the previous items fail then $f(u)=$OK.

By the Ramsey assumption on the number $m$, there is a set $a\subset m$ of
cardinality $n$ which is homogeneous for the coloring $f$. I will argue that
the homogeneous color is OK, the sets $\mathrm{dom}(p_{i})$ for $i\in a$ form
a $\Delta$-system, $\bigcup_{i\in a}p_{i}$ is a function, and every
$\Gamma$-edge in $\mathrm{dom}(\bigcup_{i\in a}p_{i})$ is a subset of
$\mathrm{dom}(p_{i})$ for some $i\in a$. That edge will not be monochromatic
since $p_{i}$ is a $\Gamma$-coloring. In conclusion, $\bigcup_{i\in a}p_{i}$
is a common lower bound in $R(\Gamma)$ of the conditions $p_{i}$ for $i\in a$.
This will conclude the proof of the theorem. I proceed in a sequence of
claims.

######  Claim 3.4.

The homogeneous color is not $\langle 0,b,j\rangle$ for any $b\in 3$ and $j\in
k$.

###### Proof.

Suppose towards a contradiction that this occurs; for definiteness, assume
that $b=2$. Then there are only $2k$ many options for $x_{j}^{i}$ for $i\in a$
(they all must come from the first two elements of the set $a$), so they must
repeat, and there must be a set $u\in[a]^{3}$ such that the value of
$x_{j}^{i}$ for $i\in u$ does not depend on $i$. This contradicts the
assumption that $f(u)=\langle 0,b,j\rangle$. ∎

It follows that writing $G=\\{j\in k\colon$ the value of $x_{j}^{i}$ does not
depend on $i\in a\\}$, the sets $\mathrm{dom}(p_{i})$ for $i\in a$ form a
$\Delta$-system with heart $H=\\{x_{j}^{i}\colon i\in a,j\in G\\}$. To see
this, note that if $i_{0}\neq i_{1}$ were two distinct elements of $a$ and
$j\in k$ were such that
$x_{j}^{i_{0}}\in\mathrm{dom}(p_{i_{1}})\setminus\\{x_{j}^{i_{1}}\\}$, then
this would trigger the first item above for any $u\in[a]^{3}$ containing both
elements $i_{0},i_{1}$, contradicting the claim.

######  Claim 3.5.

The homogeneous color is not $\langle 1,b,j\rangle$ for any $b\in 3$ and $j\in
k$.

###### Proof.

If it were, $j\in G$ would have to occur. There are only $l$ many colors
available for $p_{i}(x_{j}^{i})$ for $i\in a$, which means that one of them
has to repeat at least three times. Let $u\in[a]^{3}$ be such that
$p_{i}(x_{j}^{i})$ for $i\in u$ does not depend on $i$. Then $f(u)=\langle
1,b,j\rangle$ must fail, a contradiction. ∎

It follows that $\bigcup_{i\in a}p_{i}$ is a function. Any disagreement of
distinct conditions on the common part $H$ of their domain would trigger the
second item above for some set $u\in[a]^{3}$, contradicting the claim.

######  Claim 3.6.

The homogeneous color is not $\langle 2,b,j\rangle$ for any $b\in 3$ and $j\in
k$.

###### Proof.

Suppose towards a contradiction that this occurs; for definiteness, assume
that $b=2$. Then there are at most $d\cdot[2k]^{2}$ many options for the value
of $x_{j}^{i}$ as $i$ varies over all elements of $a$ by the assumption on the
hypergraph $\Gamma$. This means that these values have to repeat, and there
will be a set $u\in[a]^{3}$ such that $x_{j}^{i}$ is the same for all $i\in
u$. Such $u$ cannot have $f(u)=\langle 2,b,j\rangle$. ∎

Now, let $e$ be a $\Gamma$-hyperedge in $\mathrm{dom}(\bigcup_{i\in a}p_{i})$;
I need to argue that there is a single $i\in a$ such that
$e\subset\mathrm{dom}(p_{i})$. Otherwise, there would be $i\in a$ such that
$e\cap\mathrm{dom}(p_{i})\setminus H$ is a singleton, which would trigger the
third item for any set $u\in[a]^{3}$ containing $i$ and the other two indices
needed to reconstruct $e$, contradicting the claim. This completes the proof
of the theorem. ∎

######  Theorem 3.7.

Let $X$ be a set and let $\Gamma$ be a graph such that for every $x_{0}\in X$,
the set $\\{x_{1}\in X\colon\\{x_{0},x_{1}\\}\in\Gamma\\}$ is finite. Then
$R(\Gamma)$ is $X,\Gamma$-definably Ramsey-$\sigma$-centered.

###### Proof.

For each $k,l,d\in\omega$ let $A_{kld}=\\{p\in
R(\Gamma)\colon|\mathrm{dom}(p)|=k,\mathrm{rng}(p)\subset l$, and each point
in $\mathrm{dom}(p_{i})$ has at most $d$-many neighbors$\\}$. It will be
enough to show that each set $A_{kld}$ is Ramsey-centered.

To this end, let $k,l,d,n\in\omega$ be arbitrary. Increasing the number $n$ if
necessary, I may assume that $n>d+2,k+2$. Let $m\in\omega$ be a number such
that $m\to(n)^{2}_{6k+1}$. It will be enough to show that among any $m$ many
elements of $A_{kld}$ one can find $n$ many with a common lower bound, i.e.
such that their union is still a partial $\Gamma$-coloring.

To do that, let $\\{p_{i}\colon i\in m\\}\subset A_{kld}$ be any set. For each
$i\in m$, fix an enumeration $\langle x_{j}^{i}\colon i\in k\rangle$ of
$\mathrm{dom}(p_{i})$. Consider the following map $f$ on $[m]^{2}$. If
$u\in[m]^{2}$ is a set, let $i_{0}<i_{1}$ be its elements in increasing order
and define $f(u)$ by a split into cases:

  * •

if there is an index $b\in 2$ and an index $j\in k$ such that
$x_{j}^{i_{b}}\neq x_{j}^{i_{1-b}}$ yet $x_{j}^{i_{b}}\in v_{i_{1-b}}$, then
the functional value will be $f(u)=\langle 0,b,j\rangle$ for some such $b$ and
$j$;

  * •

if the previous item fails and there is $j\in k$ such that $x_{j}^{i}$ does
not depend on $i\in u$, yet the value $p_{i}(x_{j}^{i})$ is different for the
two numbers $i\in u$, then $f(u)=\langle 1,0,j\rangle$ for some such $j$;

  * •

if the previous items fail and there are $b\in 2$ and $j\in k$ such that the
point $x_{j}^{i_{b}}\notin\mathrm{dom}(p_{i_{1-b}})$ is $\Gamma$-connected
with some point in
$\mathrm{dom}(p_{i_{1-b}})\setminus\mathrm{dom}(p_{i_{b}})$, then let
$f(u)=\langle 2,b,j\rangle$ for some such $b,j$;

  * •

if all of the previous items fail then $f(u)=$OK.

Use the Ramsey property of $m$ to find a set $a\subset m$ of cardinality $n$
which is homogeneous for $f$. As in the proof of Theorem 3.3, one can argue
that the sets $\mathrm{dom}(p_{i})$ for $i\in a$ form a $\Delta$-system,
$\bigcup_{i\in a}p_{i}$ is a function, and every $\Gamma$-edge in
$\mathrm{dom}(\bigcup_{i\in a}p_{i})$ is a subset of $\mathrm{dom}(p_{i})$ for
some $i\in a$. That edge will not be monochromatic since $p_{i}$ is a
$\Gamma$-coloring. In conclusion, $\bigcup_{i\in a}p_{i}$ is a common lower
bound in $R(\Gamma)$ of the conditions $p_{i}$ for $i\in a$. ∎

##  4 A balanced coloring poset

Towards the proof of Theorem 1.4, I must find a balanced forcing which
generates the desired model of ZF+DC over the choiceless Solovay model. I use
this opportunity to isolate a rather general scheme for coloring ternary
hypergraphs of the following form:

######  Definition 4.1.

Let $\langle X,+\rangle$ be a standard Borel abelian group and $\Gamma$ a
finite union of slim linear ternary hypergraphs on $X$. Let
$C=\bigcup_{n}C_{n}$ be a countable set decomposed into infinitely many
infinite sets. The coloring poset $P$ consists of all $p$ such that there is a
countable $\Gamma$-closed set $\mathrm{dom}(p)\subset X$ such that
$p\colon\mathrm{dom}(p)\to C$ is a $\Gamma$-coloring. The ordering is defined
by $q\leq p$ if $p\subseteq q$ and for every $\mathrm{dom}(p)$-orbit
$a\subset\mathrm{dom}(q)$ there is a number $m\in\omega$ such that
$q^{\prime\prime}a\subset\bigcup_{n\in m}C_{m}$.

For the last condition in the definition, note that the group
$\mathrm{dom}(p)$ acts on $X\setminus\mathrm{dom}(p)$ by addition, and
$\mathrm{dom}(q)\setminus\mathrm{dom}(p)$ is a set invariant under this
action. The choice of sets $C_{n}$ for $n\in\omega$ is clearly immaterial; for
convenience, below I will set $C=\mathrm{HF}\setminus\\{0\\}$ and
$C_{n}=\\{c\in C\colon|c|=n+1\\}$.

######  Proposition 4.2.

$P$ is an analytic, transitive, $\sigma$-closed relation.

###### Proof.

The analyticity of $P$ is clear. For the transitivity, assume that $r\leq
q\leq p$ are conditions in $P$, and argue that $r\leq p$ must hold. For this,
suppose that $a\subset\mathrm{dom}(r)\setminus\mathrm{dom}(p)$ is a
$\mathrm{dom}(p)$-orbit; I must show that there is a number $m\in\omega$ such
that $q^{\prime\prime}a\subset\bigcup_{n\in m}C_{m}$. There are two cases.
Either, $a$ contains some element of $\mathrm{dom}(q)$. In this case,
$a\subset\mathrm{dom}(q)$ holds, and the existence of the number $m$ follows
from $q\leq p$. Or, $a\cap\mathrm{dom}(q)=0$. In this case, $a$ is a subset of
a single $\mathrm{dom}(q)$-orbit and the existence of the number $m$ follows
from $r\leq q$.

For the $\sigma$-closure, it is clear that if $\langle p_{n}\colon
n\in\omega\rangle$ is a descending sequence of conditions, then
$\bigcup_{n}p_{n}$ is its lower bound. ∎

######  Proposition 4.3.

For every $p\in P$ and every $x\in X$ there is $q\leq p$ such that
$x\in\mathrm{dom}(q)$.

###### Proof.

First, choose $\mathrm{dom}(q)$ to be an arbitrary countable $\Gamma$-closed
set containing $\mathrm{dom}(p)$ as a subset and $x$ as an element. Let
$q\colon\mathrm{dom}(q)\to C$ be a function such that
$q\restriction\mathrm{dom}(p)=p$ and
$q\restriction\mathrm{dom}(q)\setminus\mathrm{dom}(p)$ is an injection whose
range is a subset of $C_{0}$. Then $q$ is a $\Gamma$-coloring: any hyperedge
$e\subset\mathrm{dom}(q)$ is either contained in $\mathrm{dom}(p)$ and not
monochromatic as $p\in P$, or it contains more than one element of
$\mathrm{dom}(q)\setminus\mathrm{dom}(p)$ by the $\Gamma$-closure of
$\mathrm{dom}(p)$, and it is not monochromatic as $q\setminus p$ is an
injection. Since $q\leq p$ holds, the proposition follows. ∎

######  Proposition 4.4.

Let $\bar{p}\colon X\to C$ be a total $\Gamma$-coloring. Let $V[G_{0}]$ and
$V[G_{1}]$ be generic extensions such that $V[G_{0}]\cap V[G_{1}]=V$. Let
$p_{0}\in P\cap V[G_{0}]$ and $p_{1}\in P\cap V[G_{1}]$ be conditions such
that $p_{0}\leq\bar{p}$ and $p_{1}\leq\bar{p}$. Then the conditions
$p_{0},p_{1}$ are compatible in $P$.

Note that the analytic poset $P$ is reinterpreted in every transitive model of
set theory; in particular, the conditions $p_{0},p_{1}$ are compatible in the
poset $P$ as reinterpreted in $V[G_{0},G_{1}]$ or any larger model.

###### Proof.

Work in the model $V[G_{0},G_{1}]$.

######  Claim 4.5.

$p_{0}\cup p_{1}$ is a function.

###### Proof.

This follows from the assumption that $V[G_{0}]\cap V[G_{1}]=V$: it then must
be the case that $\mathrm{dom}(p_{0})\cap\mathrm{dom}(p_{1})\subset V$. The
functions $p_{0}\restriction V$ and $p_{1}\restriction V$ are both the same,
equal to $\bar{p}$. The claim follows. ∎

Of course, this does not end the proof; I have to find a countable
$\Gamma$-closed set $\mathrm{dom}(q)\subset X$ which contains
$\mathrm{dom}(p_{0}\cup p_{1})$ and a condition $q\in P$ with this domain such
that $q\leq p_{0},p_{1}$ holds. To this end, for every $x\in
X\setminus\mathrm{dom}(p_{0}\cup p_{1})$ let
$a_{0}(x)=\\{x_{0}\in\mathrm{dom}(p_{0})\setminus V\colon\exists
x_{1}\in\mathrm{dom}(p_{1})\setminus V\ \\{x_{0},x_{1},x\\}\in\Gamma\\}$ and
$a_{1}(x)=\\{x_{1}\in\mathrm{dom}(p_{1})\setminus V\colon\exists
x_{0}\in\mathrm{dom}(p_{0})\setminus V\ \\{x_{0},x_{1},x\\}\in\Gamma\\}$.

######  Claim 4.6.

Let $x\in X\setminus\mathrm{dom}(p_{0}\cup p_{1})$ be a point. Each of the
sets $a_{0}(x),a_{1}(x)$ is a subset of a finite union of $X\cap V$-orbits. In
addition,

  1. 1.

if $b$ is a $\mathrm{dom}(p_{0})$-orbit, then $\bigcup_{x\in
b\setminus\mathrm{dom}(p_{1})}a_{1}(x)$ is a subset of a finite union of
$X\cap V$-orbits;

  2. 2.

same with subscripts $0,1$ interchanged.

###### Proof.

Let $g_{0},g_{1},g_{2}$ be linear homomorphisms defining one of the slim
linear components of the hypergraph $\Gamma$. For the first sentence of the
claim, it will be enough to show that if
$x_{0},x^{\prime}_{0}\in\mathrm{dom}(p_{0})\setminus V$ and
$x_{1},x^{\prime}_{1}\in\mathrm{dom}(p_{1})\setminus V$ are points such that
$g_{0}(x_{0})+g_{1}(x_{1})+g_{2}(x)=0$ and
$g_{0}(x^{\prime}_{0})+g_{1}(x^{\prime}_{1})+g_{2}(x)=0$, then
$x_{0},x^{\prime}_{0}$ are in the same $X\cap V$-orbit, and so are
$x_{1},x^{\prime}_{1}$. To see this, subtract the latter equation from the
former, and get $g_{0}(x_{0}-x^{\prime}_{0})=-g_{1}(x_{1}-x^{\prime}_{1})$.
The left-hand side is in $V[G_{0}]$, the right-hand side is in $V[G_{1}]$, and
since $V[G_{0}]\cap V[G_{1}]=V$, both are in $V$. Since $V$ is closed under
inverses of $g_{0}$ and $g_{1}$, $x_{0}=x^{\prime}_{0}\in X\cap V$ and
$x_{1}-x^{\prime}_{1}\in V$ as desired.

For (1) it will be enough to show that if
$x_{0},x^{\prime}_{0}\in\mathrm{dom}(p_{0})\setminus V$ and
$x_{1},x^{\prime}_{1}\in\mathrm{dom}(p_{1})\setminus V$ and $x,x^{\prime}\in
b$ are points such that $g_{0}(x_{0})+g_{1}(x_{1})+g_{2}(x)=0$ and
$g_{0}(x^{\prime}_{0})+g_{1}(x^{\prime}_{1})+g_{2}(x^{\prime})=0$, then
$x_{1},x^{\prime}_{1}$ are in the same $X\cap V$-orbit. Again, subtract the
latter equation from the former, getting
$g_{0}(x_{0}-x^{\prime}_{0})-g_{2}(x_{2}-x^{\prime}_{2})=-g_{1}(x_{1}-x^{\prime}_{1})$.
The left hand side is in $V[G_{0}]$ since $x_{2}-x^{\prime}_{2}$ is; the right
hand side is in $V[G_{1}]$. As before, this means that
$-g_{1}(x_{1}-x^{\prime}_{1})\in V$ and $x_{1}-x^{\prime}_{1}\in V$ as
desired. The proof of (2) is symmetric. ∎

Now, for each $x\in X\setminus\mathrm{dom}(p_{0}\cup p_{1})$ let $n_{x}$ be
the smallest number $n\in\omega$ such that there are no points
$x_{0}\in\mathrm{dom}(p_{0})\setminus V$ and
$x_{1}\in\mathrm{dom}(p_{1})\setminus V$ such that $p_{0}(x_{0})\in C_{n}$,
$p_{1}(x_{1})\in C_{n}$, and $\\{x_{0},x_{1},x\\}\in\Gamma$. The claim
(together with $p_{0},p_{1}\leq\bar{p}$) shows that $n_{x}$ is well-defined
and in addition, for every $\mathrm{dom}(p_{0})$-orbit $b$, the numbers
$n_{x}$ for $x\in b$ are bounded, and for every $\mathrm{dom}(p_{1})$-orbit
$c$, the numbers $n_{x}$ for $x\in c$ are bounded. Now, let
$\mathrm{dom}(q)\subset X$ be any countable $\Gamma$-closed set containing
$\mathrm{dom}(p\cup p_{1})$, write
$d=\mathrm{dom}(q)\setminus\mathrm{dom}(p_{0}\cup p_{1})$, and let
$q\colon\mathrm{dom}(q)\to C$ be any function such that $p_{0}\cup
p_{1}\subset q$, for every $x\in d$ $q(x)\in C_{n_{x}}$, and $q\restriction d$
is an injection. Such a function clearly exists since the sets $C_{n}$ for
every $n\in\omega$ are infinite. It will be enough to show that $q\in P$ and
$q$ is a common lower bound of $p_{0},p_{1}$.

First, I must argue that $q$ is a $\Gamma$-coloring. Let
$e\subset\mathrm{dom}(q)$ be a $\Gamma$-hyperedge; I must argue that $e$ is
not monochromatic. The discussion splits into several possible configurations.

Case 1. $e\subset\mathrm{dom}(p_{0}\cup p_{1})$. In this case, a counting
argument shows that there is $i\in 2$ such that $\mathrm{dom}(p_{i})$ contains
two points of $e$, and the $\Gamma$-closure of $\mathrm{dom}(p_{i})$ shows
that $\mathrm{dom}(p_{i})$ contains all points of $e$. Then $e$ cannot be
monochromatic since $p_{i}$ is a $\Gamma$-coloring.

Case 2. $e$ contains exactly one point, say $x$, in the set $d$. In this case,
the closure properties of the sets $\mathrm{dom}(p_{0})$ and
$\mathrm{dom}(p_{1})$ show that there must be a point
$x_{0}\in\mathrm{dom}(p_{0})\setminus V$ and a point
$x_{1}\in\mathrm{dom}(p_{1})\setminus V$ such that $e=\\{x_{0},x_{1},x\\}$.
Then, $e$ is not monochromatic by the choice of the number $n_{x}$ and the
fact that $q(x)\in C_{n_{x}}$.

Case 3. $e$ contains more than one point in the set $d$. In this case, $e$ is
not monochromatic since $q\restriction d$ is an injection.

Finally, I must show that $q\leq p_{0}$; the proof of $q\leq p_{1}$ is
symmetric. To this end, suppose that
$b\subset\mathrm{dom}(q)\setminus\mathrm{dom}(p_{0})$ is a
$\mathrm{dom}(p_{0})$-orbit; I must show that $q^{\prime\prime}b$ is a subset
of the union of finitely many sets $C_{n}$ for $n\in\omega$. Write
$b_{0}=b\cap\mathrm{dom}(p_{1})$ and $b_{1}=b\setminus\mathrm{dom}(p_{1})$.

The first observation is that $b_{0}$ is a $\mathrm{dom}(\bar{p})$-orbit: if
$x,x^{\prime}\in b_{0}$ then $x-x^{\prime}\in V[G_{1}]$ as $x,x^{\prime}\in
V[G_{1}]$, and $x-x^{\prime}\in V[G_{0}]$ as $b_{0}$ is a subset of
$\mathrm{dom}(p_{0})$-orbit. Since $V[G_{0}]\cap V[G_{1}]=V$, it follows that
$x-x^{\prime}\in V$; as $x,x^{\prime}\in b_{0}$ were arbitrary, it follows
that $b_{0}$ is a $\mathrm{dom}(\bar{p})$-orbit. Since $p_{1}\leq\bar{p}$ is
assumed, it follows that $q^{\prime\prime}b_{0}$ is a subset of the union of
finitely many sets $C_{n}$ for $n\in\omega$.

The second observation is that the set $c=\bigcup_{x\in
b_{1}}a_{1}(x)\subset\mathrm{dom}(p_{1})$ is a subset of a finite union of
$\bar{p}$-orbits, and since $p_{1}\leq\bar{p}$ is assumed, the set
$q^{\prime\prime}c$ is covered by a finite union of the sets $C_{n}$ for
$n\in\omega$. Let $m\in\omega$ be some number such that $C_{m}\cap
q^{\prime\prime}c=0$. It follows from the definitions that $n_{x}\leq m$ holds
for every $x\in b_{1}$, therefore $q^{\prime\prime}b_{1}\subset\bigcup_{n\leq
m}C_{n}$ holds.

The two observations taken together show that $q^{\prime\prime}b$ is a subset
of the union of finitely many sets $C_{n}$ for $n\in\omega$ as desired. ∎

######  Corollary 4.7.

The poset $P$ is balanced, and in fact placid in the sense of [6, Definition
9.3.1].

###### Proof.

It will be enough, for every condition $p\in P$, to find a total coloring
$\bar{p}\colon X\to\mathrm{HF}$ such that the range of $\bar{p}\setminus p$
consists of sets of cardinality at most two. For then, in any generic
extension collapsing the cardinality of the ground model continuum to
$\aleph_{0}$, it will be the case that $\bar{p}\in P$ and $\bar{p}\leq p$
holds. In addition, Proposition 4.4 then shows that $\bar{p}$ will be exactly
the balanced (or placid) virtual condition required in the definition of
balance (or placidity).

Now, to obtain the extension of $p$ to $\bar{p}$, use Corollary 2.11 to find a
$\Gamma$-coloring $c\colon X\to\mathrm{HF}$ and use Corollary 2.7 to find a
$\Delta(\mathrm{dom}(p))$-coloring
$d\colon\mathbb{R}^{2}\setminus\mathrm{dom}(p)\to\mathrm{HF}$. Define the
function $\bar{p}$ by setting $\bar{p}(x)=p(x)$ if $x\in\mathrm{dom}(p)$, and
$\bar{p}(x)=\langle c(x),d(x)\rangle$ if $x\notin\mathrm{dom}(p)$. This is
literally an amalgamation of $p$ with $c$ and $d$ in the sense of Definition
2.9, so Proposition 2.10 shows that $\bar{p}$ is a $\Gamma$-coloring. By its
definition, the range of $\bar{p}\setminus p$ consists of sets of cardinality
at most two. This completes the proof. ∎

##  5 The independence proofs

Finally, I am in the position to provide the proof of Theorem 1.4. Let
$\kappa$ be an inaccessible cardinal and let $W$ be the choiceless Solovay
model derived from $\kappa$. Let $G\subset P$ be a filter generic over $W$; I
will show that $W[G]$ is a model witnessing Theorem 1.4. There are several
components of that proof.

######  Proposition 5.1.

In the model $W[G]$, there is no Vitali set.

###### Proof.

It will be enough to show that the poset $P$ has Ramsey control as in [6,
Section 11.6]. This means that in ZFC, for a condition $p\in P$ there is a
triple $\langle R,\leq,\mathcal{C},\bar{p}\rangle$ such that

  1. 1.

$R,\leq,\bar{p}$ are all definable from ordinal parameters and $p$;

  2. 2.

$\mathcal{C}$ is a collection consisting of Ramsey centered subsets of $R$,
each of which is definable from ordinal parameters and $p$, and
$R=\bigcup\mathcal{C}$;
tem $\bar{p}$ is an $R$-name for a total $\Gamma$-coloring such that
$R\Vdash\mathrm{Coll}(\mathbb{R},\aleph_{0})\Vdash\bar{p}\leq\check{p}$.

The poset $R$ is the finite support iteration of length $\omega_{1}$ in which
the $\alpha$-th iterand (in the model $\mathbb{R}^{2}\cap
V[G_{\beta}\colon\beta\in\alpha]$) is the poset $R_{\alpha 0}\times R_{\alpha
1}$ where $R_{\alpha 0}$ is the finite condition poset coloring the hypergraph
$\Gamma$ from Theorem 3.3. To specify $R_{\alpha 1}$, use Example 2.6 to find
a homomorphism $h_{\alpha}\colon X_{\alpha}\to Y_{\alpha}$, where
$X_{\alpha}=X\setminus\bigcup_{\beta\in\alpha}\\{V[G_{\gamma}\colon\gamma\in\beta\\}$
(if $\alpha=0$) or $X\setminus\mathrm{dom}(p)$ if $\alpha=0$ and $h_{\alpha}$
is a homomorphism of the remainder graph $\Gamma_{X\setminus X_{\alpha}}$ to
some locally finite graph $\Delta_{\alpha}$. Note that Example 2.6 provides
$h_{\alpha},Y_{\alpha},\Delta_{\alpha}$ which are definable from $p$ (if
$\gamma=0$) or from the sequence of intermediate generic extensions (if
$\gamma>0$). $R_{\alpha 1}$ will then be the finite condition poset adding a
coloring of the graph $\Delta_{\alpha}$.

Each of these posets is suitably definably $\sigma$-Ramsey-centered, and
c.c.c. This means that the finite support iteration $R$ is c.c.c. and it is a
union of Ramsey-centered pieces, each of which is definable from $p$ and some
ordinal parameters. This is proved as in [6, Proposition 11.6.3], noting that
the Suslinity of the posets can be replaced with ordinal definability from the
sequence of generic extensions.

At each stage of the iteration, $R_{\alpha+1}$ adds a $\Gamma$-coloring
$\dot{c}_{\alpha}$ and $R_{\alpha 1}$ adds a coloring $\dot{d}_{\alpha}$ of
the remainder graph which is the pullback of the generic
$\Delta_{\alpha}$-coloring by the homomorphism $h_{\alpha}$. In the end, let
$\bar{p}$ be the name for the amalgamation of the coherent sequence $\langle
p,\dot{c}_{\alpha},\dot{d}_{\alpha}\colon\alpha\in\omega_{1}\rangle$ of
colorings as in Definition 2.9. This will be a total $\Gamma$-coloring
extending $p$ by Proposition 2.10;
$R\Vdash\mathrm{Coll}(\mathbb{R},\aleph_{0})\Vdash\bar{p}\leq\check{p}$
follows from the definitions.

The proof of the proposition is now completed by a reference to [6, Theorem
11.6.5] applied to the Vitali equivalence relation viewed as a Borel graph. ∎

######  Proposition 5.2.

In the model $W[G]$, the equivalence relation $E_{1}$ does not have a complete
countable section.

###### Proof.

I will in fact show that the poset $P$ is nested balanced [6, Definition
9.4.2]. Then, by [6, Theorem 9.4.4], in the $P$-extension of the Solovay
model, the cardinality of the $\mathbb{E}_{1}$-quotient space is not smaller
than the cardinality of the orbit space of any Polish group action. In
particular, there is no complete $\mathbb{E}_{1}$ section
$S\subset(2^{\omega})^{\omega}$, since then the map sending any
$\mathbb{E}_{1}$-class to its intersection with $S$ would be an injection of
the $\mathbb{E}_{1}$-quotient space to the $\mathbb{F}_{2}$-quotient space,
which is an orbits space of an action of the full permutation group
$S_{\infty}$.

To recall what nested balance means, a sequence $\langle M_{i}\colon
i\in\omega\rangle$ of transitive models of ZFC is _coherent_ [6, Section 4.2]
if $M_{0}\supseteq M_{1}\supseteq\dots$ and for every ordinal $\alpha$ and
every number $i\in\omega$, the sequence $\langle M_{j}\cap V_{\alpha}\colon
j>i\rangle$ belongs to the model $M_{i}$. The sequence is _choice-coherent_
[6, Section 4.3] if for every ordinal $\alpha$ there is a well-ordering
$\prec$ of $V_{\alpha}$ such that for every $i\in\omega$, $\prec\restriction
M_{i}\in M_{i}$ holds. For a choice coherent sequence $\langle M_{i}\colon
i\in\omega\rangle$, write $M_{\omega}$ for the intersection model
$\bigcap_{i}M_{i}$. It is a transitive model of ZFC.

To show that the poset $P$ is nested balanced, it is enough, for a given
choice-coherent sequence $\langle M_{i}\colon i\in\omega\rangle$ of transitive
models of ZFC, to build a descending sequence of suitably balanced conditions.
In the context of the poset $P$, it means building a total coloring
$\bar{p}\in M_{0}$ such that for each $i\in\omega+1$, the function
$\bar{p}_{i}=\bar{p}_{0}\restriction M_{i}$ belongs to the model $M_{i}$, and
for $i\leq j\leq\omega$, $\bar{p}_{i}\leq\bar{p}_{j}\leq p$ holds in any
forcing extension which collapses $|M_{0}\cap\mathbb{R}|$ to $\aleph_{0}$.

To this end, let $\prec$ be a well-ordering of the set of all partial maps
from $\mathbb{R}^{2}$ to $\mathrm{HF}$ such that for each $i\leq\omega$,
$\prec\restriction M_{i}\in M_{i}$ holds. Let $I=\omega+2$, and let $\leq$ be
the reverse of the usual ordinal ordering on $I$. For each $i\in I$, define
the real closed field $F_{i}$: if $i\leq\omega$ then $F_{i}=\mathbb{R}\cap
M_{i}$, and $F_{\omega+1}=\mathrm{supp}(p)$. For each $i\in I$, define the
colorings $c_{i}$ and $d_{i}$: if $i\in\omega+1$, then $c_{i}\colon
F_{i}^{2}\to\mathrm{HF}$ is the $\prec$-least $\Gamma$-coloring in the model
$M_{i}$, and $d_{i}\colon F_{i}^{2}\setminus F_{i+1}^{2}\to\mathrm{HF}$ is the
$\prec$-least $\Delta_{i}$-coloring in the model $M_{i}$, where $\Delta_{i}$
is the remainder graph $\Delta(F_{i}^{2},F_{i+1}^{2})$. Also, $c_{\omega+1}=p$
and $d_{\omega+1}=0$. It is not difficult to see that $\langle
I,\leq,F_{i},c_{i},d_{i}\colon i\in I\rangle$ is a coherent sequence of
colorings as in Definition 2.8. Let $\bar{p}$ be the amalgamation of these
colorings as in Definition 2.9. I claim that $\bar{p}$ is as required.

First of all, $\bar{p}$ is a $\Gamma$-coloring by Proposition 2.10. The
definition of amalgamation, and the coherent choices of the colorings $c_{i}$
and $d_{i}$, immediately imply that for each $i\in\omega+1$,
$\bar{p}_{i}=\bar{p}\restriction M_{i}$ belongs to the model $M_{i}$. Finally,
$\bar{p}$ extends $p$, and by the definition of amalgamation, the range of
$\bar{p}\setminus p$ consists of ordered pairs, i.e. of sets of cardinality at
most two. It follows that for each $i\in j\in\omega+1$,
$\bar{p}_{i}\leq\bar{p}_{j}\leq p$ holds in any forcing extension in which
$|F_{i}|=\aleph_{0}$. The proof is complete. ∎

The proof of Theorem 1.6 is quite different. It closely follows [6, Section
11.8]. It uses an auxiliary hypergraph and a simple proper forcing notion of
independent interest.

######  Definition 5.3.

Let $n\geq 2$ be a number. $\Delta_{n}$ is the $F_{\sigma}$ $n$-ary hypergraph
on the space $Y_{n}=n^{\omega}$, where a $\Delta_{n}$-hyperedge is a set
$e\in[Y]^{n}$ such that there is a finite set $a\subset\omega$ and $z\in
n^{\omega\setminus a}$ such that $e=\\{y\in Y_{n}\colon
y\restriction\omega\setminus a=z$ and $y\restriction a$ is constant$\\}$.

The hypergraph $\Delta_{n}$ is unfortunately not actionable in the sense of
[6, Definition 11.8.1], so the results of [6, Section 11.8] are not applicable
verbatim and a restatement of the proof is necessary. There is a forcing
notion associated with $\Delta_{n}$. Using the Hales–Jewett theorem
repeatedly, produce a sequence of consecutive nonempty finite intervals
$I_{m}$ of natural numbers for $m\in\omega$ such that for every partition of
$n^{I_{m}}$ into $m$ pieces, one of the pieces contains a combinatorial line.
Let $\phi_{m}$ be the submeasure on $n^{I_{m}}$ defined by $\phi_{m}(m)=$the
smallest number of subsets of $n^{I_{m}}$, neither of which contains a
combinatorial line, and together they cover $b$. Thus,
$\phi_{m}(n^{I_{m}})\geq m$ the poset $R_{n}$ consists of sequences $r=\langle
b_{m}\colon m\in\omega\rangle$ such that $b_{m}\subset n^{I^{m}}$ is a
nonempty set and $\limsup_{m}\phi_{m}(b_{m})=\infty$. The ordering on $R_{n}$
is that of coordinatewise inclusion. The generic point of $n^{\omega}$ added
by the poset $R_{m}$ is the concatenation of the coordinatewise intersection
of all conditions in the generic filter. The relevant properties of $R_{n}$
are verified as in [6, Claim 11.8.4]:

######  Proposition 5.4.

The poset $R_{n}$ is proper, bounding, and adds no independent reals. In
addition, for every condition $r\in R_{n}$, in the $R_{n}$-extension below $r$
there is a $\Delta_{n}$-hyperedge whose elements are all $R_{n}$-generic and
meet the condition $r$.

The argument of [6, Section 11.8] can then be repeated to yield

######  Proposition 5.5.

In every compactly balanced extension of the choiceless Solovay model, the
chromatic number of $\Delta_{n}$ is uncountable.

Finally, I return to abelian groups and linear equations. Let $\langle
X,+\rangle$ be a Polish abelian group, let $n\geq 3$ be a number, and let
$g_{i}\colon X\to X$ for $i\in n$ be continuous homomorphisms such that
$\Sigma_{i\in n}g_{i}=0$. Write $\Gamma$ for the hypergraph of arity $n$
containing a tuple $\langle x_{i}\colon n\rangle$ of pairwise distinct points
if $\Sigma_{i\in n}g_{i}(x_{i})=0$. Suppose that open neighborhood of $0$ in
$X$ contains a $\Gamma$-hyperedge consisting of nonzero points.

Let $d$ be a left-invariant compatible metric on $X$. Since $X$ is abelian,
$d$ is both-sided invariant, so complete. By recursion on $m\in\omega$, select
nonzero pairwise distinct points $x_{i}(m)\in X$ for $i\in n$ so that

  * •

$\Sigma_{i}g_{i}(x_{i}(m))=0$;

  * •

$d(0,x_{i}(m))<2^{-m}$ times the minimum $d$-distance between distinct points
of the form $x_{j}(k)$ for $k\in m$ and $j\in n$.

In addition, define the map $\pi_{n}\colon Y_{n}\to X$ by setting
$\pi_{n}(y)=\Sigma_{m}x_{y_{m}}(m)$. The completeness an invariance of the
metric $d$ implies that the map $\pi_{n}$ is well-defined and continuous. In
addition, the continuity of the homomorphisms $g_{i}$ for $i\in n$ show that
if $\langle y_{i}\colon i\in n\rangle$ is a $\Delta_{n}$-hyperedge, then
$\langle\pi_{n}(y_{i})\colon i\in n\rangle$ is a $\Gamma$-hyperedge; the map
$\pi_{n}$ is a homomorphism of $\Delta_{n}$ to $\Gamma$. In conjunction with
Proposition 5.5 this concludes the proof of Theorem 1.6.

##  6 Problematic hypergraphs

There are algebraic hypergraphs for which the existence of colorings yields
remarkable consequences in ZF+DC.

######  Definition 6.1.

$\Gamma_{R}$ is the hypergraph of arity four on $\mathbb{R}^{2}$ consisting of
all sets of the form $a\times b$ where both $a,b\subset\mathbb{R}^{2}$ are
sets of cardinality two.

To tie this hypergraph in with the previous sections, note that it is a
subgraph of the linear hypergraph on $\mathbb{R}^{2}$ given by the equation
$x_{0}-x_{1}+x_{2}-x_{3}=0$. In ZFC, it is a well-known result (a conjunction
of [1] and [2, Theorem 2]) that existence of countable $\Gamma_{R}$-coloring
is equivalent to the Continuum Hypothesis. In ZF, the situation is more
nuanced.

######  Theorem 6.2.

(ZF) Suppose that $\Gamma_{R}$ has countable chromatic number. Then

  1. 1.

if there is an $\omega_{1}$-sequence of pairwise distinct reals, then there is
such a sequence enumerating all reals;

  2. 2.

there is a complete countable section for the $\mathbb{E}_{1}$ equivalence
relation.

The second item is the opposite of Theorem 1.4(3). While I do not know if the
existence of a Vitali set follows from the countable chromatic number of
$\Gamma_{R}$, the first item shows that any negative consistency result in
this direction must use an inaccessible cardinal. It also shows that the
results of [10, 11] require the inaccessible cardinal assumption as well.

###### Proof.

Let $c\colon\mathbb{R}^{2}\to\omega$ be a total $\Gamma_{R}$-coloring.

For (1), suppose that $s=\langle r_{\alpha}\colon\alpha\in\omega_{1}\rangle$
be a sequence of pairwise distinct reals.

######  Claim 6.3.

The model $HOD_{s,c}$ contains all reals.

###### Proof.

Suppose towards a contradiction that it does not. Let $r\in\mathbb{R}\setminus
HOD_{s,c}$ be any real. Use a counting argument to find distinct countable
ordinals $\alpha,\beta$ such that the points $\langle
r,r_{\alpha}\rangle,\langle r,r_{\beta}\rangle\in\mathbb{R}^{2}$ receive the
same color in $c$, say $n\in\omega$. The real $r$ cannot be unique with this
property, since in such a case it would be definable and therefore an element
of $HOD_{s,c}$. If $r^{\prime}$ is a different real with this property, then
te set $\\{r,r^{\prime}\\}\times\\{r_{\alpha},r_{\beta}\\}$ is a monochromatic
$\Gamma_{R}$-hyperedge with color $n$, a contradiction. ∎

Now, work in the model $HOD_{s,c}$ and argue that the Continuum Hypothesis
holds there as ZFC+countable chromatic number of $\Gamma_{R}$ implies CH; this
will conclude the proof. This is in fact a known result [2, Theorem 2]; for
completeness, let me include it. Work in ZFC, suppose that
$d\colon\mathbb{R}^{2}\to\omega$ is a $\Gamma_{R}$-coloring, and assume
towards a contradiction that the Continuum Hypothesis fails. Let $M$ be an
elementary submodel of cardinality $\aleph_{1}$ of a large structure
containing the coloring $d$. Let $r_{0}\in\mathbb{R}\setminus M$ be any point.
By a counting argument, there must be a number $n\in\omega$ and distinct reals
$s_{0},s_{1}\in\mathbb{R}\cap M$ such that $d(s_{0},r_{0})=d(s_{1},r_{0})=n$.
By elementarity of the model $M$, there has to be a point
$r_{1}\in\mathbb{R}\cap M$ satisfying the latter equation with $r_{0}$
replaced with $r_{1}$. Then the set $\\{s_{0},s_{1}\\}\times\\{r_{0},r_{1}\\}$
is a $\Gamma_{R}$-hyperedge monochromatic in color $n$, contradicting the
choice of the coloring $d$.

For (2), suppose that $x\in\mathbb{R}^{\omega}$ be a point, and for each
$n\in\omega$ let $M_{nx}$ be the class of all sets hereditarily ordinally
definable from $c$ and $x\restriction M_{nx}$. These models clearly form a
sequence decreasing with respect to inclusion. Thus, the ordinals
$(\omega_{1})^{M_{nx}}$ form a non-increasing sequence, which has to stabilize
at some number $m\in\omega$. The same proof in (1) shows that the sets
$\mathbb{R}\cap M_{nx}$ stabilize at that same number $m\in\omega$. If this
stabilized set is uncountable, then there is a bijection bewteen $\omega_{1}$
and $\mathbb{R}$ by (1), and the proof is complete.

Suppose then that for every sequence $x\in\mathbb{R}^{\omega}$, the sets
$\mathbb{R}\cap M_{nx}$ for $n\in\omega$ stabilize to some countable set.
Then, even the sets $[x]_{\mathbb{E}_{1}}\cap M_{nx}$ stabilize in some
countable set, call it $a(x)$. Note that the set $a(x)$ depends only on the
$\mathbb{E}_{1}$-class of $x$. Thus, the set $\bigcup\\{a(x)\colon
x\in\mathbb{R}^{\omega}\\}$ is a complete countable section for
$\mathbb{E}_{1}$. ∎

######  Definition 6.4.

$\Gamma_{T}$ is the hypergraph of arity three on $\mathbb{R}^{2}$ consisting
of those sets for which adding a single point results in a
$\Gamma_{R}$-hyperedge.

Clearly, any $\Gamma_{T}$-coloring is a $\Gamma_{R}$-coloring; so, it is more
difficult to find a $\Gamma_{T}$-coloring. Again, in ZFC, it is a well-known
result ??? that existence of countable $\Gamma_{T}$-coloring is equivalent to
the Continuum Hypothesis. Thus, in ZFC, hypergraphs $\Gamma_{R}$ and
$\Gamma_{T}$ are conflated in this way, even though the construction of
$\Gamma_{T}$-coloring is much more difficult. In ZF, the distinction between
the two hypergraphs becomes immediately apparent:

######  Theorem 6.5.

(ZF) If $\Gamma_{T}$ has countable chromatic number, then there is a total
countable-to-one map from $\mathbb{R}$ to $\omega_{1}$.

In particular, in ZF, if $\Gamma_{T}$ has countable chromatic number, then
every equivalence relation on a Polish space has countable complete section. I
do not know if a Vitali set must exist. However, balanced forcing cannot be
applied to obtain any consistency result in this direction, since countable-
to-one maps from $\mathbb{R}$ to $\omega_{1}$ do not exist in balanced
extensions of the choiceless Solovay model.

###### Proof.

Let $c\colon\mathbb{R}^{2}\to\omega$ be a $\Gamma_{T}$ coloring. For
$x\in\mathbb{R}$ write $M_{x}$ for the model of all sets hereditarily
ordinally definable from $x$ and $c$. Note that $c\restriction M_{x}\in M_{x}$
holds. The argument divides into two cases.

Case 1. There is a real $x$ such that $\mathbb{R}\cap M_{x}$ is uncountable.
In this case, apply Theorem 6.2(1) to show that there is even a total
injection from $\mathbb{R}$ to $\omega_{1}$.

Case 2. Case 1 fails. Let $\pi\colon\mathbb{R}\to\omega_{1}$ be the map
defined by $\pi(x)=\omega_{1}^{M_{x}}$. The case assumption shows that the
range of this map is indeed a subset of $\omega_{1}$. We will show that $\pi$
is in fact countable-to-one. Suppose towards contradiction that it is not, and
let $\alpha\in\omega_{1}$ be an ordinal such that the set
$\\{x\in\mathbb{R}\colon\pi(x)=\alpha\\}$ is uncountable. By the case
assumption, there have to be points $x_{0},x_{1}$ in this set such that
$x_{1}\notin M_{x_{0}}$. We will reach a contradiction by a split into
subcases.

Case 1a. Suppose first that $x_{0}\notin M_{x_{1}}$. Let $L_{0}$ be the line
in $\mathbb{R}^{2}$ consisting of points whose $0$-th coordinate is equal to
$x_{0}$ and let $L_{1}$ be the line in $\mathbb{R}^{2}$ consisting of points
whose $1$-st coordinate is equal to $x_{1}$. Let $n=c(x_{0},x_{1})$. Then
$\langle x_{0},x_{1}\rangle$ is not the only point on $L_{0}$ which gets color
$n$–otherwise $x_{1}$ would be definable from $x_{0}$. Let $\langle
x_{0},x_{2}\rangle\in L_{0}$ be a different point which gets color $n$. By the
same argument, $\langle x_{0},x_{1}\rangle$ is not the only point on $L_{1}$
which gets color $n$–otherwise $x_{0}$ would be definable from $x_{1}$. Let
$\langle x_{3},x_{1}\rangle\in L_{1}$ be a different point which gets color
$n$. Then $\\{\langle x_{0},x_{1}\rangle,\langle x_{0},x_{2}\rangle,\langle
x_{3},x_{1}\rangle\\}$ is a monochromatic $\Gamma_{T}$-hyperedge of color $n$.
A contradiction.

Case 1b. Assume now that $x_{0}\in M_{x_{1}}$. The set $\mathbb{R}\cap
M_{x_{0}}$ then belongs to $M_{x_{1}}$ and must be uncountable there because
the two models have the same $\omega_{1}$. By a counting argument in
$M_{x_{1}}$, there must be distinct points $y_{0},y_{1}\in\mathbb{R}\cap
M_{x_{0}}$ such that $\langle y_{0},x_{1}\rangle$ and $\langle
y_{1},x_{1}\rangle$ get the same $c$-color, say $n$. Now, $x_{1}$ cannot be
the only point such that $\langle y_{1},x_{1}\rangle$ gets the color
$n$–otherwise $x_{1}$ would be definable from $y_{1}$ and then also from
$x_{0}$. So, pick a point $z\in\mathbb{R}$ such that $c(y_{1},z)=n$ and note
that the set $\\{\langle y_{0},x_{1}\rangle,\langle y_{1},x_{1}\rangle,\langle
y_{1},z\rangle\\}$ is a $c$-monochromatic $\Gamma_{T}$-hyperedge of color $n$.
This is a final contradiction. ∎

## References

  * [1] P. Erdős and S. Kakutani.  On non-denumerable graphs.  Bulletin of the American Mathematical Society, 49:457–461, 1943\.
  * [2] Paul Erdős and Péter Komjáth.  Countable decompositions of $\mathbb{R}^{2}$ and $\mathbb{R}^{3}$.  Discrete and Computational Geometry, 5:325–331, 1990.
  * [3] Thomas Jech.  Set Theory.  Springer Verlag, New York, 2002.
  * [4] Alexander S. Kechris.  Classical Descriptive Set Theory.  Springer Verlag, New York, 1994.
  * [5] Alexander S. Kechris, Slawomir Solecki, and Stevo Todorcevic.  Borel chromatic numbers.  Advances in Mathematics, 141:1–44, 1999.
  * [6] Paul Larson and Jindřich Zapletal.  Geometric set theory.  AMS Surveys and Monographs. American Mathematical Society, Providence, 2020.
  * [7] Stevo Todorcevic.  Two examples of Borel partially ordered sets with the countable chain condition.  Proceedings of the American Mathematical Society, 112:1125–1128, 1991.
  * [8] Jindrich Zapletal.  Coloring redundant algebraic hypergraphs.  2021\.  in preparation.
  * [9] Jindrich Zapletal.  Coloring closed noetherian graphs.  Journal of Mathematical Logic, 2023.  in print.
  * [10] Jindrich Zapletal.  Coloring triangles and rectangles.  Comment. Math. Univ. Carolin., 64:83–96, 2023.
  * [11] Jindrich Zapletal.  Krull dimension in set theory.  Ann. Pure Appl. Logic, 174, 2023.  Paper No. 103299, 16 pp.


obeypunctuation=true]Technical University of Munich
Bolzmannstr. 3 85748 Garching, Germany obeypunctuation=true]Technical
University of Munich
Bolzmannstr. 3 85748 Garching, Germany

# A Model for Using Physiological Conditions for Proactive Tourist
Recommendations

Rinita Roy  [<EMAIL_ADDRESS>and  Linus W. Dietz
orcid.org/0000-0001-6747-3898 [<EMAIL_ADDRESS>
###### Abstract.

Mobile proactive tourist recommender systems can support tourists by
recommending the best choice depending on different contexts related to
herself and the environment. In this paper, we propose to utilize wearable
sensors to gather health information about a tourist and use them for
recommending tourist activities. We discuss a range of wearable devices,
sensors to infer physiological conditions of the users, and exemplify the
feasibility using a popular self-quantification mobile app. Our main
contribution then comprises a data model to derive relations between the
parameters measured by the wearable sensors, such as heart rate, body
temperature, blood pressure, and use them to infer the physiological condition
of a user. This model can then be used to derive classes of tourist activities
that determine which items should be recommended.

wearable devices, user modeling, proactive recommender systems, context
modeling, machine learning

††copyright: none

##  1\. Introduction

Suggesting points of interest or activities to tourists within a city is a
popular and challenging recommender systems research problem. To provide
interesting recommendation at the right time, context-awareness is very
advantageous (Woerndl and Groh,, 2007). Currently, mobile phones are commonly
used for eliciting its user’s context. However, in some situations tourists
might be uncomfortable pulling out their smart phones due to the fear of them
being stolen, or for social reasons as it might be inappropriate to check
phones all the time when fellow-travellers are around. This gives rise to
wearable devices, such as smart watches for context modeling. Wearable devices
have embedded sensor technologies and can be used to collect various
information about the wearer and the surrounding environment. Wallace and
Press (Wallace and Press,, 2003) showed new perspectives of looking at
wearable objects by involving computer technologies into them. However,
wearable devices of the last ten years such as the Fitbit
Zip111https://fitbit.com/au/Zip, Google
Glass222https://developers.google.com/glass/develop/gdk/location-sensors,
Apple Watch333https://apple.com/lae/watch/, and the Microsoft
HoloLens444https://microsoft.com/en-IE/hololens had mixed success on the
market and the smart phone is still the most prevalent mobile device.

As a tourist, it is useful to get personalized recommendations about where to
visit, what to do next throughout a trip, given that the recommender has
sufficient system information about the context of the tourist. Unlike
classical recommender systems, mobile recommendations can also be proactive,
meaning that the recommendations are pushed to the user without explicit
request (Woerndl et al.,, 2011). This introduces the additional challenge to
determine the appropriate timing of the recommendations. Wearable sensor
devices help to gather various data about and around the wearer. This data can
be used to acquire contextual information, and with further processing, the
proper conditions can be derived to recommend tourist activities to the
wearer. Our approach was thus guided by the following research questions:

  1. RQ1:

How can different physiological conditions be inferred using wearable sensors?

  2. RQ2:

How can these conditions be used to derive preferences for activities?

In the following section, we survey related work on tourist recommender
systems based on context awareness, wearable devices, and sensor data. We
present our data model in section 3, which shows how to select tourist
activities based on data from typical sensors found in wearable devices.
Finally, we draw the conclusion and present future work in section 4.

##  2\. Foundations

We argue that to improve mobile, context-aware, and proactive recommender
systems, sensors in wearable devices can be useful by inferring the
physiological conditions of a user. If the sensor data can be interpreted
accurately in the context modeling step, the overall recommendation accuracy
of a mobile recommender system can be improved with recommendations that fit
well to the context and condition of the user.

###  2.1. Context-Aware Recommender Systems

Throughout this paper, we follow Dey’s definition of context: _“Context is any
information that can be used to characterise the situation of an entity. An
entity is a person, place, or object that is considered relevant to the
interaction between a user and an application, including the user and
applications themselves(Dey,, 2001).”_ It is generally believed that if the
contextual information of a person, e.g., physical or emotional states, or her
surroundings, e.g., location and time, is available, the accuracy of the
recommendations increases. Adomavicius et al. (Adomavicius et al.,, 2011)
presented a way how context can be used to develop intelligent recommender
systems. Ashley-Dejo et al. (Ashley-Dejo et al.,, 2016) proposed a context-
aware proactive recommender system for tourists and determined the accuracy of
the recommendations comparing the benefits of using various different
contextual information, such as location, weather, or time as opposed to not
considering context at all. In their evaluation the traditional multi-criteria
collaborative filtering approach, where no context information was used had
the least performance, while the recommendations where all context information
was used performed best.

For the recommendation of customized destinations and routes to travelers, the
current location is one of the most prevalent context factors. Meehan et al.
(Meehan et al.,, 2013) highlight the importance of considering more contextual
information other than location, such as, weather, time, sentiment, and user
preferences. But not all context factors are equally important as Baltrunas et
al. (Baltrunas et al.,, 2012) found when they investigated the importance of a
context factors for different activities. For example, TourRec, a recommender
system for city trips (Laß et al.,, 2017) only uses time of the day, weather
and previously visited points of interest. In the model proposed in our paper,
we showcase the possibility of using physiological conditions for proactively
recommending personalized tourist activities.

###  2.2. Wearable Devices

Wearable devices can support humans with the overload of information in
communication and computation in appropriate contexts (Billinghurst and
Starner,, 1999). A survey of commercially available wearables, research
prototypes, and their classification was done by Seneviratne et al.
(Seneviratne et al.,, 2017), and Godfrey et al. (Godfrey et al.,, 2018)
provide an A-Z guide of the key terms required for understanding current
wearable technology developments in health care.

Wearable devices are useful for measuring various physiological and
biochemical parameters (Islam and Mukhopadhayay,, 2017), which can further be
processed to benefit the healthcare domain. For example, a sensor-equipped
ring has been used to provide physiological data of patients and further
analyzing it with their profiles by using assistant systems showed that it can
help to resolve wrong diagnoses by doctors (Shehab et al.,, 2017). Clothing or
textiles are good collectors of body information as they stay in close contact
with the skin (Stoppa and Chiolerio,, 2014). Smart textiles are also widely
used to noninvasively gather health information (Coyle et al.,, 2010) and
physical monitoring (Pandian et al.,, 2008). Kamisalic et al. (Kamišalić et
al.,, 2018) surveyed how various physiological parameters and activities can
be noninvasively measured by sensors incorporated into wrist-worn devices. For
this reason these type of sensors are also useful to monitor athletes’
training and health (Düking et al.,, 2016).

Despite its potential, wearable devices have not yet become that predominant
in the tourism sector. Tussyadiah (Tussyadiah,, 2013) identified personal
motivations to use wearable devices for travel and tourism. Atembe (Atembe,,
2015) compiled the limited use of wearable devices in tourism by presenting
some use cases and providing the usage of wearable devices there. One early
work in this area is the one of Vlahakis et al. (Vlahakis et al.,, 2002), who
designed a system that provides interactive, personalized, augmented reality
tours in archaeological sites using mobile and wearable computers.

We work towards the usage of wearable devices in the tourism domain by showing
a way to derive contextual information by using the data collected by wearable
sensors and then utilizing the context to proactively recommend relevant
activities during a trip suitable to her physiological conditions.

###  2.3. Data Ecosystems

The basic assumption is that sensors in wearable devices are capable of
measuring different health parameters, such as the heart rate or blood
pressure, and report this to a centralized application. Through constant
monitoring, the sensor data can be used to determine different physiological
conditions, e.g., to find out how active, tired, or hungry the user is. In a
second step a recommender system can then utilize these conditions as context
factors to make recommendations.

Figure 1. Apple Health Mobile Application

The feasibility of our approach is, thus, highly dependent on the real-time
availability of accurate sensor data. Fortunately, there are commercial data
ecosystems in place, such as Apple Health555https://apple.com/lae/ios/health/
or Samsung Health666https://www.samsung.com/global/galaxy/apps/samsung-
health/. Using these apps on the mobile phone, a user can organize various
health data at a single place, which can be visualized and analyzed. Figure 1
shows three screenshots of Apple Health. The first is the overview page, which
mentions broad categories like _‘Activity’_ , _‘Mindfulness’,_ _‘Nutrition’_ ,
and _‘Sleep’_ , but also includes further points like heath-related data and
even _‘Reproducible Health’_ , which is aimed exclusively for women to keep
track of their menstrual cycle. The second screenshots depicts an aggregation
of the activities recorded by the iPhone, while the third screenshot shows
which heart-related data can be tracked. It can be seen as a manifestation of
the _‘Quantified Self’_ movement, where the users continuously record their
own body data to analyze them with the motif of self improvement (Swan,,
2013). The data is collected via connected wearable devices, entered manually,
or by granting read and write access to third party applications on the iPhone
as can be seen in the third screenshot. This constitutes a data ecosystem,
which can be used to develop novel applications leveraging this data given the
user consents. Another example is the work of Pandian et al. (Pandian et al.,,
2008), a wearable sensor monitoring system that can measure and transmit
physiological parameters to a remote monitoring station along with the geo-
location of the wearer.

###  2.4. Inferring Physiological Conditions

Figure 2. Model of Deriving Physiological Conditions from Sensors and
Recommending Tourist Activities

Health parameters collected by the wrist-wearable devices have already been
studied and used to deduce relevant physiological conditions from them
(Kamišalić et al.,, 2018). For example, Alfeo et al. (Alfeo et al.,, 2018)
collected information about heart rate and arm motion using wearable devices
to assess per-night sleep quality of the wearer. Zhang et al. (Zhang et al.,,
2018) used wrist-worn wearable sensors to detect gestures and showed a
correlation between the feeding gesture counts and caloric intake more of
which lead to overeating. A wrist-worn sensing system was developed by
Sugimoto et al. (Sugimoto et al.,, 2005) for calculating energy expenditure,
by estimating oxygen uptake from correlation between heart rate and oxygen
uptake. Defining some thresholds, we can find out if a person is active,
relaxed or tired. We chose the following conditions that can be detected using
wearable sensor data and are also relevant for travelers.

  * •

Active (Sugimoto et al.,, 2005; Kamišalić et al.,, 2018)

  * •

Relaxed (Sugimoto et al.,, 2005; Kamišalić et al.,, 2018)

  * •

Tired (Sugimoto et al.,, 2005; Kamišalić et al.,, 2018; Alfeo et al.,, 2018)

  * •

Drunk (Selvam et al.,, 2016)

  * •

Hungry (Zhang et al.,, 2018; Sugimoto et al.,, 2005)

  * •

Stressed (Gjoreski et al.,, 2017; Sandulescu et al.,, 2015; Kamišalić et al.,,
2018)

##  3\. Deriving Activities from Physiological Conditions

The physiological condition of a tourist influences the suitability of the
recommended activities. Literature lists various activity taxonomies
(Mehmetoglu,, 2007), however, in this research we fall back to a subset of
Foursquare’s venue
categories777https://developer.foursquare.com/docs/resources/categories, as
tourist activities for our data model. The main advantage is that they cover
most touristic activities and provide a direct mapping to concrete items,
which is useful for the final recommendation step. The five categories are
(1) Outdoors & Recreation,  (2) Arts & Entertainment,  (3) Food,  (4)
Residence, and  (5) Nightlife.

Which activity should be suggested to the tourist depends on her current
contextual and physiological conditions. For example:

  * •

If the tourist is very active, she can be suggested to do sports or
adventurous outdoor activities like horse-riding.

  * •

If a traveler has not slept for a long time or is stressed, recommending a
relaxing activity might be fitting.

  * •

Contrary, if she is relaxed, we would suggest her an intellectual activity.

  * •

Finally, if someone has been very active over a prolonged time without taking
a break, we would recommend to refresh herself with food or drinks.

The above examples describe assumptions of one might expect tourists to behave
in general under their particular physiological conditions. In reality, people
might not follow that and act more peculiarly. Therefore, a context-aware
recommender system need to learn the weights between the physiological
conditions derived from wearable sensors and the respective activities. For
this, a machine learning algorithm shall be employed to observe the behavior
of the tourists given their physiological conditions. The upper part of Figure
2, depicts selected positive and negative influences from physiological
conditions to tourist activities. Green arrows imply a positive correlation,
i.e., if the condition has a higher value, the activity at the end of the
arrow is recommended. If the arrow is orange, the score of corresponding
activity is decreased. In our proposed model, the user model comprises a
normalized value of each physiological conditions.

The associations between the sensor values and the physiological conditions in
the lower part of Figure 2 can be derived as discussed in Section 2.4. Then,
we can form a 1X6 physiological condition vector, $PC$ (see Equation 1), that
denotes the current status of a tourist’s physiological conditions, each
column having a value, $c_{a},c_{r},c_{t},c_{d},c_{h},c_{s}$ for each of the
six physiological conditions: active, relaxed, tired, drunk, hungry and
stressed.

(1)
$\begin{array}[]{l@{{}={}}c}\text{PC}&\left(\begin{array}[]{@{}cccccc@{}}c_{a},&c_{r},&c_{t},&c_{d},&c_{h},&c_{s}\\\
\end{array}\right)\end{array}$

Next, we use the previously learned associative weights of our activity
variables, $or$ (outdoors & recreation), $ae$ (arts & entertainment), $fd$
(food), $rs$ (residence), and $nl$ (nightlife) to compute the fitting
activity. This is done by forming a $6X5$ weight matrix, $W$, as shown in
Equation 2. Each column holds the values yielded from the machine learning for
each activity, under each of the physiological condition in each row. For
example, $w_{(or/a)}$ denotes the weight value of opting for activities from
the group ‘outdoor and recreation’ having an ‘active’ physiological condition.

(2)
$\begin{array}[]{l@{{}={}}c}\text{W}&\left(\begin{array}[]{@{}cccccc@{}}w_{(or|a)}&w_{(ae|a)}&w_{(fd|a)}&w_{(rs|a)}&w_{(nl|a)}\\\
w_{(or|r)}&w_{(ae|r)}&w_{(fd|r)}&w_{(rs|r)}&w_{(n|r)}\\\
w_{(or|t)}&w_{(ae|t)}&w_{(fd|t)}&w_{(rs|t)}&w_{(nl|t)}\\\
w_{(or|d)}&w_{(ae|d)}&w_{(fd|d)}&w_{(rs|d)}&w_{(nl|d)}\\\
w_{(or|h)}&w_{(ae|h)}&w_{(fd|h)}&w_{(rs|h)}&w_{(nl|h)}\\\
w_{(or|s)}&w_{(ae|s)}&w_{(fd|s)}&w_{(rs|s)}&w_{(n|s)}\\\
\end{array}\right)\end{array}$

$PC.W$ results in the $1X5$ Activity Recommendation Index (ARI) vector as
shown in Equation 3.

(3) $\begin{array}[]{l@{{}={}}c}\text{ARI = PC .
W}&\left(\begin{array}[]{@{}ccccc@{}}a_{or},&a_{ae},&a_{fd},&a_{rs},&a_{nl}\\\
\end{array}\right)\end{array}$

The tourist activity to be recommended is the one with the highest ARI value.
Now the recommender system will choose the an item from this category based on
the user preferences.

##  4\. Conclusions and Future Work

This paper discusses a method to use wearable devices for deriving the
physiological context of a tourist and by this to improve proactive
recommendations of activities during a trip. The sensors equipped in the
wearables monitor various physiological parameters of a tourist, and by
further processing this data, it is possible to derive the physiological
context of a traveler such as being hungry or stressed. The main contribution
is a model to facilitate the already available data from health-related
application such as Apple Health to recommend tourist activities.

In future, we plan to implement and evaluate the model in a mobile tourist
recommender system. The challenge is to convince users to make their health-
related data available for the recommender for potentially more fitting
recommendations. Since data ecosystems like Apple Health make it easy to share
it, we are optimistic that this is possible in general. We hope that the
users’ trust can be achieved by open-sourcing the application and keeping the
data on the device of the user.

## References

  * Adomavicius et al., (2011) Adomavicius, G., Mobasher, B., Ricci, F., and Tuzhilin, A. (2011).  Context-aware recommender systems.  AI Magazine, 32(3):67–80.
  * Alfeo et al., (2018) Alfeo, A. L., Barsocchi, P., Cimino, M. G. C. A., Rosa, D. L., Palumbo, F., and Vaglini, G. (2018).  Sleep behavior assessment via smartwatch and stigmergic receptive fields.  Personal and Ubiquitous Computing, 22(2):227–243.
  * Ashley-Dejo et al., (2016) Ashley-Dejo, E., Ngwira, S. M., and Zuva, T. (2016).  A context-aware proactive recommender system for tourist.  International Conference on Advances in Computing and Communication Engineering, pages 271–275.
  * Atembe, (2015) Atembe, R. (2015).  The use of smart technology in tourism: Evidence from wearable devices.  Journal of Tourism and Hospitality Management, 3(6):224–234.
  * Baltrunas et al., (2012) Baltrunas, L., Ludwig, B., Peer, S., and Ricci, F. (2012).  Context relevance assessment and exploitation in mobile recommender systems.  Personal and Ubiquitous Computing, 16(5):507–526.
  * Billinghurst and Starner, (1999) Billinghurst, M. and Starner, T. (1999).  Wearable devices: New ways to manage information.  Computer, 32(1):57–64.
  * Coyle et al., (2010) Coyle, S., Lau, K. T., Moyna, N., O’Gorman, D., Diamond, D., Francesco, F. D., Costanzo, D., Salvo, P., Trivella, M. G., Rossi, D. D., Taccini, N., Paradiso, R., Porchet, J.-A., Ridolfi, A., Luprano, J., Chuzel, C., Lanier, T., Revol-Cavalier, F., Schoumacker, S., Mourier, V., Chartier, I., Convert, R., De-Moncuit, H., and Bini, C. (2010).  Biotex—biosensing textiles for personalised healthcare management.  IEEE Transactions on Information Technology in Biomedicine, 14:364–370.
  * Dey, (2001) Dey, A. K. (2001).  Understanding and using context.  Personal and Ubiquitous Computing, 5(1):4–7.
  * Düking et al., (2016) Düking, P., Hotho, A., Fuss, F. K., Holmberg, H.-C., and Sperlich, B. (2016).  Comparison of non-invasive individual monitoring of the training and health of athletes with commercially available wearable technologies.  Frontiers in Physiology, 7(71).
  * Gjoreski et al., (2017) Gjoreski, M., Lustrek, M., Gams, M., and Gjoreski, H. (2017).  Monitoring stress with a wrist device using context.  Journal of Biomedical Informatics, 73:159–170.
  * Godfrey et al., (2018) Godfrey, A., Hetherington, V., Shum, H., Bonato, P., Lovell, N. H., and Stuart, S. (2018).  From A to Z: Wearable technology explained.  Maturitas, 113(April):40–47.
  * Islam and Mukhopadhayay, (2017) Islam, T. and Mukhopadhayay, S. C. (2017).  Wearable sensors for physiological parameters measurement: physics, characteristics, design and applications.  In Wearable Sensors, 2053-2563, pages 1–31. IOP Publishing.
  * Kamišalić et al., (2018) Kamišalić, A., Fister, I., Turkanović, M., and Karakatič, S. (2018).  Sensors and functionalities of non-invasive wrist-wearable devices: A review.  Sensors, 18(6).
  * Laß et al., (2017) Laß, C., Herzog, D., and Wörndl, W. (2017).  Context-aware tourist trip recommendations.  In Proceedings of the 2nd RecSys Workshop on Recommenders in Tourism, pages 18–25.
  * Meehan et al., (2013) Meehan, K., Lunney, T., Curran, K., and McCaughey, A. (2013).  Context-aware intelligent recommendation system for tourism.  In International Conference on Pervasive Computing and Communications Workshops, pages 328–331. IEEE.
  * Mehmetoglu, (2007) Mehmetoglu, M. (2007).  Nature-based tourists: The relationship between their trip expenditures and activities.  Journal of Sustainable Tourism, 15(2):200–215.
  * Pandian et al., (2008) Pandian, P. S., Mohanavelu, K., Safeer, K. P., Kotresh, T. M., Shakunthala, D. T. I., Gopal, P., and Padaki, V. C. (2008).  Smart vest: wearable multi-parameter remote physiological monitoring system.  Medical Engineering & Physics, 30 4:466–77.
  * Sandulescu et al., (2015) Sandulescu, V., Andrews, S., Ellis, D., Bellotto, N., and Mozos, O. M. (2015).  Stress detection using wearable physiological sensors.  In Ferrández Vicente, J. M., Álvarez-Sánchez, J. R., de la Paz López, F., Toledo-Moreo, F. J., and Adeli, H., editors, Artificial Computation in Biology and Medicine, pages 526–532, Cham. Springer.
  * Selvam et al., (2016) Selvam, A. P., Muthukumar, S., Kamakoti, V., and Prasad, S. (2016).  A wearable biochemical sensor for monitoring alcohol consumption lifestyle through ethyl glucuronide (EtG) detection in human sweat.  Scientific Reports, 6(1).
  * Seneviratne et al., (2017) Seneviratne, S., Hu, Y., Nguyen, T., Lan, G., Khalifa, S., Thilakarathna, K., Hassan, M., and Seneviratne, A. (2017).  A survey of wearable devices and challenges.  IEEE Communications Surveys and Tutorials, 19(4):2573–2620.
  * Shehab et al., (2017) Shehab, A., Ismail, A., Osman, L., Elhoseny, M., and El-Henawy, I. M. (2017).  Quantified self using IoT wearable devices.  In Hassanien, A. E., Shaalan, K. F., Gaber, T., and Tolba, M. F., editors, Proceedings of the International Conference on Advanced Intelligent Systems and Informatics 2017, volume 639, pages 820–831. Springer.
  * Stoppa and Chiolerio, (2014) Stoppa, M. and Chiolerio, A. (2014).  Wearable electronics and smart textiles: A critical review.  Sensors, 14(7):11957–11992.
  * Sugimoto et al., (2005) Sugimoto, C., Ariesanto, H., Hosaka, H., Sasaki, K., Yamauchi, N., and Itao, K. (2005).  Development of a wrist-worn calorie monitoring system using bluetooth.  Microsystem Technologies, 11(8-10):1028–1033.
  * Swan, (2013) Swan, M. (2013).  The quantified self: Fundamental disruption in big data science and biological discovery.  Big Data, 1(2):85–99.
  * Tussyadiah, (2013) Tussyadiah, I. (2013).  Expectation of travel experiences with wearable computing devices.  In Information and Communication Technologies in Tourism, pages 539–552. Springer.
  * Vlahakis et al., (2002) Vlahakis, V., Karigiannis, J., Tsotros, M., Ioannidis, N., and Stricker, D. (2002).  Personalized augmented reality touring of archaeological sites with wearable and mobile computers.  In Proceedings of the Sixth International Symposium on Wearable Computers, pages 15–22. IEEE.
  * Wallace and Press, (2003) Wallace, J. and Press, M. (2003).  Craft knowledge for the digital age.  In Proceedings of the Sixth Asian Design Conference, pages 14–17.
  * Woerndl and Groh, (2007) Woerndl, W. and Groh, G. (2007).  Utilizing physical and social context to improve recommender systems.  In Proceedings of the 2007 IEEE/WIC/ACM International Conferences on Web Intelligence and Intelligent Agent Technology - Workshops, WI-IATW ’07, pages 123–128, Washington, DC, USA. IEEE Computer Society.
  * Woerndl et al., (2011) Woerndl, W., Huebner, J., Bader, R., and Gallego-Vico, D. (2011).  A model for proactivity in mobile, context-aware recommender systems.  In Proceedings of the Fifth ACM Conference on Recommender Systems, RecSys ’11, pages 273–276, New York, NY, USA. ACM.
  * Zhang et al., (2018) Zhang, S., Stogin, W., and Alshurafa, N. (2018).  I sense overeating: Motif-based machine learning framework to detect overeating using wrist-worn sensing.  Information Fusion, 41:37–47.