arXiv:1609.07694v1 [math.LO] 25 Sep 2016

INFINITELY MANY REDUCTS OF HOMOGENEOUS
STRUCTURES
BERTALAN BODOR, PETER J. CAMERON, AND CSABA SZABÓ
Abstract. It is shown that the countably infinite dimensional
pointed vector space (the vector space equipped with a constant)
over a finite field has infinitely many first order definable reducts.
This implies that the countable homogeneous Boolean-algebra has
infinitely many reducts. Our construction over the 2-element field
is related to the Reed–Muller codes.

1. Introduction
Simon Thomas’ conjecture says that every countable homogeneous
structure with a finite relational language has only finitely many inequivalent reducts [17]. A relational structure Γ is a reduct of the
structure ∆ iff they have the same domain and every relation of Γ has
a first-order definition in ∆. Two structures are called first-order equivalent if they are the reducts of each other. Thomas’ conjecture has been
verified for several well-known homogeneous structures, but there seems
to be no general progress towards proving it. In [7] the reducts of the
dense linear order, (Q, ≤) are determined. For the random graph and
random hypergraphs Thomas has determined their reducts [17], [18].
Both the random graph and the dense linear order have 5 reducts. In
[9] it is shown that the “pointed” linear order has 116 reducts. Thus
adding a constant to (Q, ≤), the number of reducts increases by far.
The Henson-graphs have no nontrivial reducts [17]. Later in [3] and [4]
a general technique was introduced to investigate first order definable
reducts of homogeneous structures on a finite language. Although the
strategy works only under very special conditions, the first few reducts
were possible to determine in several cases. Applying these techniques
several structures have been analyzed: the random poset [14], [13],
equality [1] and the random graph revisited [2]. They all have finitely
many reducts. For the pointed Henson-graphs (Hn , C) [15] it is shown
that for n = 2 there are 13 for n > 2 there are 16 reducts of (Hn , C).
The proof of this highly non-trivial result applies all existing tricks and
techniques. Similarly to [5], where the 42 proper reducts of the ordered
The research was supported by the Hungarian OTKA K109185 grant.
1

2

B. BODOR, P. J. CAMERON, AND CS. SZABÓ

random graph is determined on 42 pages. In [5] it is mentioned that
we do not even know how to show that the lattice of reducts has only
finitely many atoms, or no infinite ascending chains. In order to learn
more, it seems to be unavoidable to verify the conjecture for more of
the classical structures from model theory, independently from whether
or not we believe the conjecture. First order definable reducts are interesting for ω-categoricalstructures in general. A structure Γ1 is the
reduct of Γ2 if and only if Aut (Γ1 ) ≥ Aut (Γ2 ) [8]. Hence determining
the reduct of an ω-categorical structure is equivalent to find the closed
supergroups of its automorphism group in the symmetric group of its
domain.
The countable dimensional vector spaces and the countable atomless
Boolean algebra are ω-categorical. Although they are not homogeneous
on a finite relational language, they are of finite signature. The firstorder definable reducts of the countable vector space and the symplectic
space over F2 were determined in [6]. There are finitely many of them.
The proper reducts of the vector space are the affine space and the
stabilizer of 0 in the symmetric group. In addition the symplectic space,
the vector space endowed with a · symplectic form, has one additional
reduct, the vector space with the ternary relation a · b + a · c + b · c for
a, b, c linearly independent vectors.
In this paper we show that the statement of Thomas’ conjecture is
not true for homogeneous structures of finite signature. We present
infinitely many reducts of the pointed vector spaces over finite fields
and of the homogeneous Boolean algebra, as well.
Our construction for pointed vector spaces over finite fields can be
re-formulated in terms of infinite analogues of the Reed–Muller codes
[12, 16].

2. The construction
Let V be a countably infinite dimensional vector space over the 2element field, F2 and 0 6= C ∈ V . Let us fix a 1-codimensional subspace
W < V not containing C. Then, V = hW, ci and V = {w, w + C | w ∈
W }. We shall investigate the pointed vector space (V, C) that is obtained by adding C as a constant to V . The automorphism group
of V is Aut (V ) = GL(V ) and the automorphism group of (V, C) is
the stabilizer of C in GL(V ) so Aut (V, C) = GL(V )C . For an element ϕ ∈ Aut (V, C) either W ϕ = W or codim(W ϕ ∩ W ) = 2. Let
Wϕ = W ϕ ∩ W . We have the following two cases: If W ϕ = W . Then
(w + C)ϕ = w ϕ + C for every w ∈ W . If W ϕ 6= W , let a ∈ W \ Wϕ .

INFINITELY MANY REDUCTS OF HOMOGENEOUS STRUCTURES

3

Then V = Wϕ ∪ (Wϕ + a) ∪ (Wϕ + C) ∪ (Wϕ + a + C). Let ϕ be defined
in the following way: if W ϕ = W then ϕ = ϕ. If W ϕ 6= W , then let
– v ϕ = v ϕ if v ϕ ∈ Wϕ ∪ (Wϕ + C) and
– v ϕ = v ϕ + C if v ϕ ∈ (Wϕ + a) ∪ (Wϕ + a + C).
The map ϕ clearly does not depend on the choice of a, and it is an
automorphism of (V, C) mapping W to W . The map ϕ is uniquely
determined by ϕ̃ = ϕ|W . For a σ ∈ Aut (W ) let σ V denote this
extension:
V
– v σ = v σ if v ∈ W and
V
– v σ = (v + C)σ + C if v ∈
/W
Now, let U < W such that codim U = 2 and σ ∈ Aut W . Then there
is a unique σU 6= σ V ∈ Aut (V, C) such that σ̃U = σ and Wσ̃U = U
that is obtained by
V
V
– v σU = v σ + C if v σ ∈ (W \ U) ∪ (W \ U + C).
V
– v σU = v σ otherwise.
Definition 1. Let S ⊆ W . Let hS ∈ Sym(V ) defined by v hS = v + C
for v ∈ S ∪ (S + C) and v hS = v else. If v ∈ S then we say that hS
flips v.
Set H = {hS | S ⊆ W }. Now, H is a subgroup of Sym(V ) and
isomorphic to Z2W . With the above notations σU = σ V ◦ hW \U . The
subgroup H is an elementary Abelian 2-group, in particular commutative and is normalized by Aut (W )V . So, there is a canonical embedding
Aut W ⋊ Z2W → hAut V, Hi given by (σ, h) → σ V ◦ h. Moreover, with
the above notations we have ϕ = ϕ ◦ hW \Wϕ for every ϕ ∈ Aut V .
Definition 2. For a vector space Fλ2 over F2 and Wn ≤ Fλ2 , where Wn
is an n-codimensional subspace of W and let Hn = hAut (Fλ2 ), hWn i.
Clearly, Hn does not depend on Wn , only on the codimension n.
Lemma 3 (Subspace calculus). Let V be a vector space over F2 and
let dim V = λ > n where λ is either finite or λ = ω
(dif) Let X, Y ⊆ Fλ2 . Then hX ◦ hY = hX∇Y , where ∇ denotes the
symmetric difference of subsets.
(gen) For everyQh ∈ Hn ∩ H there are Wi < Fλ2 (i = 1, 2, . . . , k) such
that h = hWi .
(aff) If W < Fλ2 , codim W = n and w ∈ Fλ2 , then hW +w ∈ Hn .
(trans) If hX ∈ Hn and w ∈ Fλ2 , then hX+w ∈ Hn .
(codim) If w ∈ W < Fλ2 and codim W < n, then hW , hW +w ∈ Hn .
(two) If a, b ∈ U < Fλ2 and dim U = n + 1, then there is an element
g ∈ Hn such that g|U = h{a,b} |U

4

B. BODOR, P. J. CAMERON, AND CS. SZABÓ

(even) If S ⊆ U < Fλ2 , where |S| is divisible by 2 and dim U = n + 1,
then there is an element g ∈ Hn such that g|U = hS |U
(one) If a ∈ U < Fλ2 and dim U = n, then there is an element g ∈ Hn
such that g|U = h{a} |U
(odd) If S ⊆ U < Fλ2 and dim U = n, then there is an element g ∈ Hn
such that g|U = hS |U .
Proof. If we compose the two group elements, the elements of the intersection of X and Y are flipped twice, hence are fixed by the composition. The elements of X \ Y and Y \ X are flipped once. This gives
(dif).
Item (gen) is obvious from the definition of Hn and the fact that the
group H is normalized by Aut (V ).
For (aff) if w ∈ W then hW +w = hW and we are done. If w ∈
/ W,
then let W = hW1 , ai, where a ∈
/ W1 . Then hW1 , wi and hW1 , a + wi
are n-codimensional subspaces of V . Thus hhW1 ,wi and hhW1 ,a+wi ∈ Hn .
Now, hhW1 ,wi ◦ hhW1 ,a+wi = hW +v .
For m > n every n-codimensional subspace is the disjoint union of
m-codimensional affine subspaces. Hence (codim) follows from (aff)
and (dif).
Q
By (gen)
let
h
=
hWi . Then by item (aff) hWi +w ∈ Hn and
X
Q
hX+x = hWi +x thus (trans) follows.
For (two) let U be an n-codimensional subspace of V such that U ∩
W = {0, a + b}. Then hU +a satisfies the conditions.
Item (even) easily follows from (two).
For (one) let U be an n-codimensional subspace of V such that U ∩
W = {0}. Then hU +a satisfies the
Q conditions.
For (odd) let S ⊂ U and g =
hU +a , where U is the subspace from
a∈S

g

hS

(odd). Then U = U .

Definition 4. Let V be a countably infinite dimensional vector space
over the 2-element field, C ∈ V and let W < V be a 1-codimensional
subspace, as above, not containing C. Let Rn denote the relation
(x1 , x2 , . . . , x2n ), where {xi , xi + C | 1 ≤ i ≤ 2n } is an affine subspace
of V and |{xi | 1 ≤ i ≤ 2n } ∩ W | is even.
Proposition 5. Let n ≥ 1. Then Hn preserves Rm if and only if
m≥n+1
Proof. Assume that m ≤ n. Let Wn be an n-codimensional subspace
and Um be an m dimensional subspace such that Wn ∩ Um = {0}.
Such a pair of subspaces exists by the conditions on the dimensions.

INFINITELY MANY REDUCTS OF HOMOGENEOUS STRUCTURES

5

Let (x1 , . . . , x2m ) be an enumeration of the elements of Um . Clearly,
(x1 , . . . , x2m ) ∈ Rm . Let g = hWn . Now, g ∈ Hn and v g = v + C
holds only for 0 from Um and for 0 6= v ∈ Um we have v h = v. That
is (xg1 , . . . , xg2m ) contains 2m − 1, in particular odd many elements from
W and so g does not preserve Rm .
For the other direction suppose m ≥ n + 1. Let ϕ ∈ Aut (V, C)
and consider the canonical form ϕ = ϕ ◦ hW \Wϕ . The map ϕ preserves
W , hence preserves Rk , as well, for arbitrary k. By item (codim) of
Theorem 3 we have hW \Wϕ ∈ Hn , hence it is enough to show that HW1
preserves Rm for every n-codimensional subspace W1 .
So suppose (x1 , . . . , x2m ) ∈ Rm , and let S = {x1 , . . . , x2m }. Then S ∪
(S +C) is an affine subspace of V and either xi ∈ W or xi +C ∈ W . Let
SC = {xi | xi ∈
/ W }. Now, U = (SC + C) ∪ (S \ SC ) is an n-dimensional
subspace of W and S = U hSC , that is S is obtained from the affine
subspace U by applying hSC . Also, by definition of Rm we have that
|S ∩U| = |S ∩W | is even. Now, let W1 be an arbitrary n-codimensional
subspace of W and h = hW1 . Then dim(W1 ∩ U) > 1, hence |W1 ∩ U| is
even. Moreover, S h = U hSC h so by item (dif) of Theorem 3 we have that
|S h ∩W | = |S h ∩U| = |U hSC h ∩U| = |U hSC ∇(W1 ∩U)| = |S∇(W1 ∩U)|
is even. We have {xi , xi +C} = {xhi , xhi +C}, hence (xh1 , . . . , xh2m ) ∈ Rm .
Thus hW1 preserves Rm and by item (gen) of Lemma 3 Hn preserves
Rm , as well.

Proposition 6. For the closure of the subgroups Hi we have H 1
H2 · · · Hn . . .
Proof. By item (dim) of Lemma 3 if U < V and m = dim U ≥ n then
hU ∈ Hn . By item (gen) of Lemma 3 these elements generate Hm .
Thus Hm ≤ Hn and so H m ≤ H n holds. By Theorem 5 the group
Hn preserves the relations Rn+1 and so does its closure, H n . On the
other hand Hn+1 does not preserve Rn+1 , hence H n+1 does not preserve
Rn+1 , either. Thus Hn 6= Hn+1 and the statement holds.

Remark 7. By using the observation that each automorphism ϕ of
(V, C) can be written as ϕ = ϕ ◦ hW \Wϕ , it is easy to see that H1 =
H0 = Aut (V, C) ∪ Aut (V, C)hW . In particular Aut (V, C) is a normal
subgroup of index 2 in H1 .
Theorem 8. The lattice of first-order definable reducts of the pointed
homogeneous vector space (Fω2 , C) contains an infinite ascending chain.
In particular (Fω2 , C) has infinitely many first-order definable reducts.

6

B. BODOR, P. J. CAMERON, AND CS. SZABÓ

Proof. The first-order definable reducts of a homogeneous structure
are in a one-to-one correspondence with the closed supergroups of its
automorphism groups. Proposition 6 implies the statement.

Finally, we give the relational description of the groups Hn
Theorem 9. Let π ∈ Sym(V, C). Then π ∈ H n if and only if π
preserves Rn+1 .
Proof. The group Hn preserves Rn+1 by Proposition 5. Now, let π be
a permutation preserving Rn+1 and U ≤ V be a finite dimensional
vector space of V . As automorphisms preserve Rm , we may assume
that π = hS for some S ⊆ W . It is enough to show that there is an
h ∈ Hn such that h|U = π|U. Clearly we can assume that C ∈ U. Let
U1 = U ∩ W . If dim U1 ≤ n then item (odd) of Lemma 3 proves the
statement, Hn |U1 = Z2U1 . If dim U1 = n + 1 then the statement holds
by item (even) of Lemma 3. Now, let dim U1 = m, where m ≥ n + 2.
We proceed by induction on n + m.
At first, let us assume that n = 1. We claim that in this case both S
and W \ S is an affine subspace of W . This is enough since this implies
that codim S = 1, hence π = hS ∈ H1 . At first suppose u, v, w ∈ S.
Since π preserve R2 it follows that |S ∩ {u, v, w, u + v + w}| is even.
Hence u+v+w ∈ S. Similarly if u, v, w ∈ W \S, then u+v+w ∈ W \S.
Now, assume that n ≥ 2, m ≥ n + 2, and the statement holds for
n + m − 1 and n + m − 2. Let dim U1 = m. As automorphisms preserve Rm , we may assume that π|U1 = hS |U1 for some S ⊆ W . Let
U2 ≤ U1 ∩ W such that dim U2 = m − 1, and let w ∈ U1 \ U2 . By
the induction hypothesis there is an hT ∈ Hn such that hT |U1 = π|U1 .
The permutation πh−1
T = hS∇T fixes U2 elementwise, and it preserves
Rn+1 . Let k = h(S∇T )+w . Then k preserves Rn+1 by the definition
of Rn+1 , and it fixes U1 \ U2 elementwise. By using item (trans) of
Lemma 3 it is enough to show that there is an element h ∈ Hn such
that h|U1 = k|U1 . Let W2 be a 1-codimensional subspace of W containing U2 , but not containing U1 . We would like to apply the induction
hypothesis for the vector space V2 = hW2 , Ci, the subspace hU2 , Ci, the
relation Rn and the permutation k. For this it is enough to show that k
preserves Rn restricted to hU2 , Ci. So suppose x1 , x2 . . . , x2n ∈ hU2 , Ci
and (x1 , . . . , x2n ) ∈ Rn and let X = {x1 , . . . , x2n }. We have to show
that |X ∩ X k | is even. Let Y = X ∪ (X + w). Then |Y ∩ Y k | is
even since k preserves Rn+1 . We know that k|U1 \U2 = idU1 \U2 , hence
Y ∩ Y k = (X ∩ X k ) ∪ ((X + w) ∩ (X + w)k )) = (X ∩ Xk ) ∪ (X + w),
therefore |X ∩ X k | = |Y ∩ Y k | − |X + w| = |Y ∩ Y k | − 2n , which is even.
So we can apply the induction hypothesis for the vector space V2 , the

INFINITELY MANY REDUCTS OF HOMOGENEOUS STRUCTURES

7

subspace hU2 , Ci, the relation Rn and the permutation k. It implies
that there areQ
n − 1-codimensional subspaces Y1 , Y2 , . . . , Yt of W2 such
that for h =
hYi we have that h|U2 = k|U2 . The subspaces Yi are
n-codimensional subspaces of V , hence h ∈ Hn . Moreover h fixes all
elements of U1 \ U2 ⊂ W \ W2 , hence h|U1 = k|U1 , and this is what we
wanted to show.

3. Reed–Muller codes
Our construction can be re-formulated in terms of infinite analogues
of Reed–Muller codes [12, 16].
Our description of the Reed–Muller codes follows van Lint [10].
A binary linear code of length N is a vector subspace of FN
2 . Vectors
in this space can be regarded as functions from an N-set to F2 . For
this application we take N = 2n , and identify the set of coordinates
with V = Fn2 .
The Reed–Muller code RM(r, n) can be described in two different
ways:
– it consists of all the functions from V to F2 which can be represented by polynomials of degree at most r in the coordinates;
– it is spanned by the characteristic functions of subspaces of
codimension r in V .
We summarise a few properties of these codes.

P
– RM(r, n) has dimension ri=0 ni and minimum weight 2n−r ;
– RM(r, n)⊥ = RM(n − r − 1, n), where orthogonality is with
respect to the standard inner product.
Now we return to our reducts. We have seen that the automorphism
groups of the pointed vector space (Fλ2 , C) is a semidirect product of the
space of linear functions V → F2 by the general linear group GL(V ),
where V = Fλ2 /hCi. Thus, any closed GL(V )-invariant subspace W of
the space of functions λ → F2 that contains all linear functions will
define a closed subgroup W ⋊ GL(V ) containing all automorphisms,
and hence a reduct.
Let Wk be the closure of the vector space of functions f : V → F2
given by polynomials of degree at most k in the coordinates (these are
“infinite RM codes”). Note that, since x2 and x are equal as functions,
we have W1 ≤ W2 ≤ · · · ; these subspaces are closed and GL(V )invariant. The inclusions are strict since, for example, the polynomial
of degree k which is the product of k distinct indeterminates cannot
be written as a polynomial of smaller degree. (See also the following

8

B. BODOR, P. J. CAMERON, AND CS. SZABÓ

paragraph). So we have an ascending chain of reducts. Note that
non-zero vectors in these subspaces all have infinite support.
While there is no inner product defined on the vector space of all
functions from V to F2 , we can define the “standard inner product” u·w
whenever u is a vector with finite support. Now a function belongs to
Wk if and only if it is orthogonal to the characteristic function of every
(k+1)-dimensional subspace of V . This holds for polynomials of degree
k by the same argument as in the finite case. Then, as a convergent
sequence of polynomials (in the topology of pointwise convergence) is
ultimately constant on any (k + 1)-dimensional subspace, its limit is
also orthogonal to every such subspace. We also see the strict inclusion
of the subspaces Wk from this argument: for the product of k distinct
indeterminates meets some k-dimensional subspace in a single point,
and so fails to be orthogonal to all such subspaces, and cannot lie in
Wk−1 .
So Wk ⋊ GL(V ) is a closed subgroup of the symmetric group containing all automorphisms, and hence a reduct of the pointed vector
space.
This argument also verifies the relational definition of the reducts
given earlier.
We remark that the two definitions of the finite-dimensional RM
codes are no longer equivalent in the infinite case: the space spanned
by the characteristic functions of k-dimensional subspaces contains elements of finite support and is not closed.
4. Corollaries
There are two obvious ways to generalize the result of Theorem 8.
One is to find a similar construction for vector spaces over finite fields
of odd characteristic and the other one is to find structures that have
(V, C) as a first-order definable reduct. We start with the latter one.
Let BA = (B, ∧, ∨, 0, 1, ¬) denote the countable atomless Boolean algebra. It is known that this structure is ω-categorical. For a, b ∈ BA
let a + b denote the symmetric difference of a and b.
Theorem 10. The lattice of first-order definable reducts of the homogeneous Boolean algebra contains an infinite ascending chain. In
particular it has infinitely many first-order definable reducts.
Proof. The vector space (Fω2 , C) is isomorphic to (B, +, 0, 1), hence it
is a reduct of the homogeneous Boolean algebra. Being a first-order
definable reduct is transitive, so Theorem 8 implies the statement. 

INFINITELY MANY REDUCTS OF HOMOGENEOUS STRUCTURES

9

For the case of odd fields the construction is analogous. Let V be
a countably infinite dimensional vector space over the p-element field,
Fp and 0 6= C ∈ V . Let us fix a 1-codimensional subspace W <
V not containing C. Then, V = hW, ci and V = {w, w + λC | w ∈
W, λ ∈ Fp }. The automorphism group of V is Aut (V ) = GL(V )
and the automorphism group of (V, C), the pointed vector space is
the stabilizer of C in GL(V ) so Aut (V, C) = GL(V )C . Let S ⊆ W .
Let hS ∈ Sym(V ) defined by v hS = v + C for v ∈ S and v hS =
v else. For a subspace Wn ≤ V , where Wn is an n-codimensional
subspace and let Hn = hAut (V, C), hWn i. Again, Hn does not depend
on the choice of Wn . Let Rn denote the relation (x1 , x2 , . . . , x
pn ), where
P
{xi , xi + λC | 1 ≤ i ≤ pn , λ ∈ Fp } is a subspace of V and
xi ∈ W .
As in the case of characteristic 2, for the closure of the subgroups Hi
we have H 1 H 2 · · · H n . . . . Also, for any π ∈ Sym(V, C) we
have that π ∈ H n if and only if π preserves Rn+1 . We arrived to the
conclusion:
Theorem 11. The lattice of first-order definable reducts of the pointed
homogeneous vector space (Fωp , C) contains an infinite ascending chain.
In particular (Fωp , C) has infinitely many first-order definable reducts.
Corollary 12. The lattice of first-order definable reducts of the pointed
homogeneous vector space over a finite field Fq contains an infinite
ascending chain. In particular (Fωq , C) has infinitely many first-order
definable reducts.
Proof. Let p be the characteristic of the field Fq . The structure (Fωq , C, +),
where we consider only the addition as an operation is isomorphic to
the vector space (Fωp , C). The statement follows from Theorem 8 and
Theorem 11.

References
[1] M. Bodirsky, H. Chen and M. Pinsker, The reducts of equality up to primitive
positive interdefinability, Journal of Symbolic Logic, 75(4) (2010) 1249-1292.
[2] M. Bodirsky and M. Pinsker, Minimal functions on the random graph, (2010)
Israel Journal of Mathematics, to appear
[3] M. Bodirsky, M. Pinsker and T. Tsankov, Decidability of definability, Journal
of Symbolic Logic, 78, 1036-1054.
[4] M. Bodirsky and M. Pinsker, Reducts of Ramsey structures, Model Theoretic
Methods in Finite Combinatorics, 558, Contemporary Mathematics. American
Mathematical Society (2011) 489-519.
[5] M. Bodirsky, M. Pinsker and A Pongrácz, The 42 reducts of the random ordered
graph, Proceedings of the LMS 111 (3), 591-632, 2015

10

B. BODOR, P. J. CAMERON, AND CS. SZABÓ

[6] B. Bodor, K. Kende and Cs. Szabó, Permutation groups containing infinite
symplectic linear groups and reducts of linear spaces over the two element filed
Communications in Algebra, to appear
[7] P. J. Cameron, Transitivity of permutation groups on unordered sets, Mathematische Zeitschrift, 148 (1976) 127-139.
[8] W. Hodges, Model theory, Cambridge University Press, Cambridge, 1993.
[9] M. Junker and M. Ziegler, The 116 reducts of (Q; <; a), Journal of Symbolic
Logic, 74(3) (2008) 861-884.
[10] J. H. van Lint, Introduction to Coding Theory, Graduate Texts in
Mathematics 86, Springer, Berlin, 1992.
[11] D. Macpherson, A survey of homogeneous structures, Discrete Mathematics,
311(15) (2011) 1599-1634.
[12] D. E. Muller, Application of Boolean algebra to switching circuit design and
to error detection, IRE Trans. Electronic Computers 3 (1954), 6–12.
[13] P. P. Pach, M. Pinsker, A. Pongrácz and Cs. Szabó, A new transformation of
partially ordered sets, J. Comb. Theory A 120:7 (2013) 1450-1462
[14] P. P. Pach, M. Pinsker, G. Pluhár, A. Pongrácz and Cs. Szabó, Reducts of the
random partial order, Advances in Mathematics, 67 (2014), 94–120.
[15] A. Pongrácz, Reducts of the Henson graphs with a constant, Annals of Pure
and Applied Logic (2013), to appear
[16] I. S. Reed. A class of multiple-error-correcting codes and the decoding scheme,
Trans. IRE Professional Group on Information Theory, 4 (1954),38–49.
[17] S. Thomas, Reducts of the random graph, Journal of Symbolic Logic 56(1)
(1991) 176-181.
[18] S. Thomas, Reducts of random hypergraphs, Annals of Pure and Applied Logic,
80(2) (1996) 165-193.
Eötvös Loránd University, Department of Algebra and Number
Theory, 1117 Budapest, Pázmány Péter sétány 1/c, Hungary
E-mail address: bodorb@cs.elte.hu
School of Mathematics and Statistics, University of St Andrews,
North Haugh, St Andrews, Fife KY16 9SS, UK
E-mail address: pjc20@st-andrews.ac.uk
Eötvös Loránd University, Department of Algebra and Number
Theory, 1117 Budapest, Pázmány Péter sétány 1/c, Hungary
E-mail address: csaba@cs.elte.hu

