### by Convex Structures on a Plane Weak Carousel rule

### Madina Bolat

### Supervisor: Dr. Kira Adaricheva Second reader: Dr. Rustem Takhanov

### A thesis presented for MATH 499 Capstone Project

## School of Science and Technology Nazarbayev University

## Astana Kazakhstan

## May 2016

Abstract

Convex geometries are closure systems satisfying anti-exchange axiom with combinatorial properties. Every convex geometry is represented by a convex geometry of points in n-dimensional space with a special closure operator.

Some convex geometries are represented by circles on a plane. This paper proves that not all convex geometries are represented by circles on a plane by providing a counterexample. We introduce Weak n-Carousel rule and prove that it holds for configurations of circles on a plane.

1. Introduction

Convex geometries were studied from different perspectives and un- der different names since 1930. In particular, the theory of convex geometries was brought to attention by Edelman and Jamison’s sur- vey paper in 1985 ([7]). Convex geometries are interesting combinato- rial objects which generalize a notion of convexity on Euclidean plane.

There are many structures which share their properties. Some of them include convex objects in Euclidean space, convex sets in posets, sub- semilattices in a semilattice, path-closed subgraphs of a graph ([7]). It is crucial to understand the driving example well and find structural connections between the general example and other convex geometries.

The concept of convex geometries was generated by a geometrical ex- ample: a set of points on a plane with a special closure operator. This convex geometry is called affine convex geometry. It was proved in [8]

that every convex geometry is a sub-geometry of some affine convex ge-
ometry inR^{n}. This result answers a representation problem of convex
geometries and proves an existence of some dimension of a space for a
representation. Representation problem of convex geometries ([3]):

Problem 1.1. To find a universal class C of finite convex geometries s.t. every convex geometry is a sub-geometry of some geometry in C

We are interested in finding the smallest dimension of a space for a representation. Adaricheva in [1] proved that there is a property, namely n-Carousel rule, which restricts convex geometries not satis- fying it from being embedded in a space of a particular dimension.

Carousel rule was introduced in [4]. Using the result from [1], we know that for a particular dimension of a space, there are convex geometries that could not be represented by points in this space. Czedli in [5]

modifies a construction and uses circles on a plane for a representation.

It was shown in [5] that every convex geometry of convex dimension cdim=2 could be represented by circles on a plane. Convex dimension is a parameter associated with a convex geometry, a minimal number of chains needed to realize an alignment for a convex geometry (see [7]

for more details about convex dimension). There is a natural question following from this result concerning whether every convex geometry could be represented by circles on a plane ([6]). This paper disproves this conjecture by providing an example of convex geometry which is not represented by circles.

We are introducing Weak n-Carousel rule (2.9) which is a weakening of existing n-Carousel rule. We prove that a geometry of circles on a plane satisfies 2-Weak Carousel rule. We borrow example from [1]

which fails not only 2-Carousel rule but Weak 2-Carousel rule as well.

Therefore, it is not represented by circles.

To prove that a geometry of circles satisfies 2-Weak Carousel rule, we start with proving Weak Carousel property for triangles, which is a slight simplification of Weak 2-Carousel rule. We consider two circles inside a triangle and model their location by their projections on sides of a triangle. Thus, we transform a problem from considering positions of circles to looking at configurations of segments. We find that there are 216 possible configurations of segments which we reduce to 38 cases up to isomorphism. We dismiss some of these cases by proving that a location of circles with these projections is not realizable. For this, we prove a number of lemmas. We show that all other cases are possible for realization and in all these cases the property holds.

Section 2 contains main concepts and definitions. Section 3 describes existing representations of convex geometries. Example of affine con- vex geometry that fails Weak 2-Carousel rule is described in Section 4.

Weak Carousel property for triangles is proved in Section 5. The proof of Weak Carousel property for triangles requires a number of geometri- cal results which are stated and proved in Section 6. Weak 2-Carousel rule for circles is proved in Section 7.

2. Main concepts and definitions

Definition 2.1. Given any setX, a closure operator onXis a mapping
ϕ: 2^{X} →2^{X} with the following properties:

1)Y ⊆ϕ(Y) for every Y ⊆X;

2) If Y ⊆Z, then ϕ(Y)⊆ϕ(Z) forY, Z ⊆X;

3)ϕ(ϕ(Y)) =ϕ(Y) forY ⊆X.

Definition 2.2. Pair (X, ϕ) is called a convex geometry ifϕis a closure operator on X with additional properties:

1)ϕ(∅) =∅;

2) if Y = ϕ(Y) and x, z /∈ Y, then z ∈ ϕ(Y ∪ x) implies that x /∈ ϕ(Y ∪z) (Anti-exchange property).

We could alternatively associate convex geometries with an alignment- a special family of subsets of a base set.

Definition 2.3. Given any (finite) set X, an alignment on X is a family F of subsets of X which satisfies two properties:

1)X ∈ F;

2) If Y, Z ∈ F, then Y ∩Z ∈ F

The following relationships between a closure operator and an align- ment could be easily checked ([7]):

Proposition 2.4. If ϕis a closure operator on a set X, thenF ={Y : ϕ(Y) = Y, Y ⊆X} is an alignment on X.

Proposition 2.5. Let F be an alignment on a set X. Define ϕ(Y) =

∩{Z ∈ F, Y ⊆Z} for every Y ⊆X. Then, ϕ is a closure operator on X.

Convex geometries could be defined equivalently through an align- ment:

Definition 2.6. Pair (X,F) is called a convex geometry if F is an alignment on X with additional properties:

1)∅ ∈ F;

2) if Y ∈ F and Y 6=X, then ∃a∈X\Y s.t. Y ∪ {a} ∈ F

Definition 2.7. Convex geometry G_{1} = (X,F_{1}) is a sub-geometry of
G_{2} = (Y,F_{2}) if there is a one-to-one map f :F_{1} → F_{2} s.t.

1)f(A∧B) = f(A)∧f(B),A, B ⊆X;

2)f(A∨B) = f(A)∨f(B),A, B ⊆X.

Definition 2.8. A convex geometry (A, ϕ) satisfies n-Carousel rule if
x, y ∈ϕ(S), S ⊆A, implies x∈ϕ{y, a_{1}...a_{n}} for some a_{1}, ...a_{n}∈S.

Definition 2.9. A convex geometry (A, ϕ) satisfies Weak n-Carousel
rule if x, y ∈ ϕ(S), S ⊆ A, implies either x ∈ ϕ{y, a_{1}...a_{n}} or y ∈
ϕ{x, a_{1}...a_{n}} for some a_{1}, ...a_{n}∈S.

Definition 2.10. Consider F = (X, chc), whereX is a set of circles in
R^{2} and ch_{c} is defined as follows: ch_{c}(Y) ={z ∈X : ˜z ⊆ CH(∪˜y), y ∈
Y} for Y ⊆ X, where CH is a usual convex hull operator and ˜y is a
set of points in y (˜z is a set of points in z, respectively). We call F a
geometry of circles on a plane.

Weak n-Carousel rule defined in 2.9, now could be reformulated for a convex geometry of circles on a plane.

Definition 2.11. Consider F = (A, chc) a convex geometry of cir-
cles on a plane with A = {a, b, c, x, y}. Then F satisfies Weak 2-
Carousel rule if x, y ⊆ ch_{c}({a, b, c}) implies either x ∈ ch_{c}(y, i, j) or
y∈ch_{c}(x, i, j), where i, j ∈S

To prove Weak 2-Carousel rule for circles, we simplify the rule and consider two circles and three points. We slightly modify the rule to have a geometrical formulation.

Definition 2.12. A configuration of two circles x and y and a set S of distinct points A, B, C is said to satisfy Weak Carousel Property for Triangles if x, y is in a triangle 4ABC implies either

x is in a convex hull of y and any two points from S, or y is in a convex hull of x and any two points from S.

3. Known representations of convex geometries We say that a convex geometry is represented by another convex geometry when it is a sub-geometry of the second one, i.e. there exists a one-to-one mapping from alignment of the first geometry to alignment of the second geometry preserving operations of meet (∧) and join (∨) (See Definition 2.7).

There are two types of representation. First, there is so calledWeak Representation. If we want to represent a convex geometry by a par- ticular class of convex geometries, we want to find a mapping from that convex geometry into some representative of the given class that is one-to-one and preserves closure operator (i.e. satisfies the condi- tion in ??). Second, there is Strong Representation. In this type of representation, a mapping must additionally be onto mapping.

The first universal class for a weak representation of convex geome-
tries was presented in [3] by Adaricheva et al in 2003. The model for
a representation was a class of infinite convex geometries defined on a
Boolean structure of all subsets of some set X. Convex geometries from
a universal class were of the form (2^{X}, ϕ), where ϕ corresponds to an
alignment comprising all algebraic subsets of 2^{X}. It was proved that
every finite convex geometry could be represented by an infinite con-
vex geometry in the form of a lattice of algebraic subsets of algebraic
lattices. It is a nontrivial construction which appears in many fun-
damental concepts. However, structures from the representation class
must be infinite. Although the result provides a representation for all
convex geometries, the representation could not be done only for finite
X. Therefore, the question of finding representation by a class of finite
convex geometries was raised. Problem 1.1 asks whether it is possible

to find a universal class of finite convex geometries for a representation of convex geometries.

In 2005 Kashiwabara et al. proved that every finite convex geometry could be represented as a sub-geometry of a finite convex geometry ([8]). Universal class for this weak representation was in the form of affine convex geometries.

Definition 3.1. Affine convex geometry is a convex geometry

C_{0}(R^{n}, X) = (X, ch), whereX is a set of points inR^{n} andchis defined
as follows: for Y ⊆ X, ch(Y) = CH(Y)∩X, where CH is a usual
convex hull operator.

Every finite convex geometry could be embedded in some affine con-
vex geometry in C0(R^{n}, X). Nevertheless, this representation may re-
quire a high dimension of a space. Therefore, it is worth investigating
the smallest possible dimension for a representation.

Adaricheva in [2] showed that some special convex geometries have this type of representation but with a lower dimension of a space. Refer to [2] for details.

Apart from finding the smallest dimension of a space for a weak rep-
resentation, a question of strong representation is also of a great interest
in representations of convex geometries. A question of which convex
geometries could have a strong representation by affine convex geome-
tries in R^{n} was raised by Edelman and Jamison in 1985 (See Problem
1 in [7]). The authors in [7] noted that such characterization prob-
lem is considerably difficult. There is a partial result by Adaricheva
and Wild in 2010 for a strong representation of convex geometries by
affine convex geometries in R^{2} ([4]). Edelman and Jamison provide a
representation of convex geometries by compatible orderings (See [7]

for details). There is a recent result by Richter and Rogers in 2015 that provides a nice geometrical visualization of the representation by orderings ([9]). It was proved that every convex geometry could be represented by a special location of polygons on a plane ([9]). It was shown in [9] that every finite convex geometry with a convex dimension cdim=k (a minimal number of chains needed to realize an alignment for a convex geometry) could be represented as k-gons on a plane. A geometry of k-gons with a special location and a closure operator was proved to be a convex geometry (See [9] for more details). Although this representation is a nice illustration of a strong representation, polygons may be non-convex, while we are interested in preserving the nature of convexity.

Czedli in 2014 generalizes a construction and instead of geometry of points defines a geometry of circles (2.10) and considers this geometry

for a representation ([5]). It was proved in [5], that geometry of circles on a plane is a convex geometry. By working with a geometry of circles, Czedli relaxes the construction of a geometry on a set of points because geometry of circles is not atomistic.

Definition 3.2. A convex geometry G = (X, ϕ) is called atomistic if ϕ({x}) = {x}for every x∈X

Affine convex geometries are atomistic since for any affine convex
geometry G= (X, ch), any x∈X is just a point in R^{n} and ch({x}) =
{x}. Geometry of circles on a plane is not in general atomistic. For a
convex geometry of circlesG= (X, chc), it is possible thatchc({x}) =
{x, y} for x, y ∈ X that describes a case when a circle y is inside a
circle x.

If we consider affine convex geometries as a class for a representation of convex geometries, then we could strongly represent only atomistic convex geometries. But since convex geometries are not in general atomistic, we do not have a strong representation by affine convex geometries for all convex geometries. Therefore, a construction of a convex geometry by circles on a plane in [5] could be investigated for a possibility of strong representation.

The main result of [5] shows that every convex geometry of convex dimension cdim = 2 could be strongly represented by a geometry of circles on a plane. With a relaxed construction, now there is a natural question whether any convex geometry has a strong representation by a geometry of circles on a plane.

In this paper, we disprove this conjecture by showing an example of convex geometry that is not represented by a convex geometry of circles on a plane. We show that all convex geometries of circles on a plane must satisfy Weak 2-Carousel Rule. We demonstrate an example of convex geometry that fails Weak 2-Carousel Rule. Therefore, this convex geometry could not be represented by a geometry of circles on a plane.

We prove that a strong representation of convex geometries by ge- ometries of circles on a plane is not possible in general. Therefore, it is necessary to consider higher dimensions of a space. This leads to the following problem which was formulated by Adaricheva in [6]:

Problem 3.3. Is every finite convex geometry could be represented by
a convex geometry of balls in R^{n}

4. Example of convex geometry that is not representable by circles

We borrow examples of convex geometries in this section from [1].

Consider an example of affine convex geometryG^{0} = (X,F^{0}), where
X = {a_{0}, a_{1}, a_{2}, x, y} is a set of points on a plane as shown in Figure
1. Then, F^{0} =P(X)\{a0a1a2, a0a2x, a0a1y, a0a1a2x, a0a1a2y}.

Figure 1

Consider G= (X,F), whereF =P(X)\{a_{0}a_{1}a_{2}, a_{0}a_{1}a_{2}x, a_{0}a_{1}a_{2}y},
which we get by adding {a_{0}a_{2}x} and {a_{0}a_{1}y} to the alignment F^{0} of
affine convex geometry G^{0}.

It could be directly checked that F for G satisfies the properties of
alignments from Definition 2.3. Initial alignment F^{0} satisfies the re-
quired properties since G^{0} is affine convex geometry. We add {a_{0}a_{2}x}

and {a_{0}a_{1}y} to F^{0}. All subsets of added sets are in F and their inter-
section is also in F. So, Gis indeed a convex geometry ([1]).

From [1],G= (X,F) does not satisfy 2-Carousel rule. It was shown
in [1] that convex geometries failing n-Carousel rule could not be weakly
represented by affine convex geometries in R^{n}. So, G could not be
weakly represented by affine convex geometries in R^{2}. Now, we show
that G does not also satisfy Weak 2-Carousel rule.

Letϕ:X →X be a corresponding closure operator to the alignment F of G.

Then, x∈ϕ(a_{0}a_{1}a_{2}) since ϕ(a_{0}a_{1}a_{2}) =X.

ϕ(a_{i}a_{j}x) = {a_{i}a_{j}x}, fori, j = 0,1,2
ϕ(a_{i}a_{j}y) ={a_{i}a_{j}y}, for i, j = 0,1,2

Hence, G does not satisfy Weak 2-Carousel rule since x and y are
in a closure of {a_{0}, a_{1}, a_{2}} but x is not in a closure of any two from
{a_{0}, a_{1}, a_{2}} and y. Moreover, y is not in a closure of any two from
{a0, a1, a2}and x.

We prove in Section 7 that a geometry of circles satisfies Weak 2- Carousel rule (Theorem 7.1). SinceGdoes not satisfy Weak 2-Carousel rule, G could not be represented by circles on a plane.

5. Weak Carousel Property for Triangles

Theorem 5.1. Every configuration of two circles and a set of three
distinct points in R^{2} satisfies Weak Carousel Property for Triangles.

Proof. Consider two circles x and y in a triangle 4ABC. Circles x
and y are projected on segments on sides of 4ABC. In the example
in Figure 1, we are using notation, say, x^{BC}_{B} and x^{BC}_{C} , for edges of a
projection of a circlexonBCwhich are closest toBandCrespectively.

Figure 2

There are six possible configurations of projections of x and y on each side of a triangle. We assign a numberi, that takes integer values from 1 to 6, to each configuration of segments on one side of 4ABC.

We illustrate configurations corresponding to values of i in Figure 18
in Appendix A. We assume that x_{1} and y_{1} in Figure 18 are first in
ordersx_{1}x_{2} and iny_{1}y_{2}respectively in a clockwise walk around4ABC,
assuming that ABC is in a clockwise order.

We denote a configuration of projections of two circles inside a4ABC
by C_{jkl}, where j, k, l are integer numbers that take values of i and
denote a configuration of segments on sides AB, BC, AC respectively.

Say, example from Figure 2 isC_{546}.

Six possible configurations for each side produce 216 possible con-
figurations of projections of x and y for 4ABC. We reduce 216 con-
figurations to 38 classes up to isomorphism. Say, C_{241} and C_{124} are
isomorphic cases since they represent the same triangle with sides ro-
tated clockwise. For every class Sn,where n is an number that takes
integer values from 1 to 38, we associate configurations Cjkl out of 216
configurations that are isomorphic. Refer to Appendix B) for a full list
of grouping 216 configurations in 38 classes.

Definition 5.2. We say a projection is later (earlier) than another, if in a clockwise walk around 4ABC (assuming that ABC is a clockwise order of vertexes) it is second (first) in order on a side of 4ABC.

In the example in Figure 1, x^{BC}_{B} is later than y_{B}^{BC} and x^{AC}_{C} is earlier
than y^{AC}_{A} . It is clear that, say, for x to be in a convex hull of y and
B, C, x^{AC}_{A} must be earlier than y^{AC}_{A} and x^{AB}_{A} must be later thany_{A}^{AB}.
On the other hand, x is not in a convex hull ofA,B and y, since both
x^{BC}_{C} and x^{AC}_{C} are earlier than y_{C}^{BC} and y_{C}^{AC} respectively.

In the proofs below, we will not distinguish whhether these projec- tions are disjoint or overlapping.

1) Consider a class S_{2} when in a clockwise walk around 4ABC,
projections of circlesx and y are in the same order, say, projections of
y are ”strictly later” than projections of x (for example, y^{AC}_{A} is later
than x^{AC}_{A} , and y_{C}^{AC} is later than x^{AC}_{C} on AC). Figure 4 illustrates a
configuration C_{222} as an example from a class S_{2}. Take tangent lines
to x, connecting the first edge point of each x-projection, which we
meet when we walk around4ABC clockwise, with the opposite vertex
of 4ABC (See Figure 3). Then circle x is inscribed into 4A^{0}B^{0}C^{0}
formed by these three lines. It follows from assumption thatyis inside
4A^{0}B^{0}C^{0}. Moreover, y should have points in each of three disjoint
areas of4A^{0}B^{0}C^{0}, whose union is4ABC\x. Then due to Lemma 6.4,
the case is dismissed as impossible for realization.

Figure 3

Figure 4

Configurations from classes S_{9}, S_{25}, S_{38} are dismissed using similar
argument.

2) Consider a classS_{13} when a segment of a projection of y is inside
a segment of a projection of x on one side of 4ABC but a projec-
tion of x is inside a projection of y on another side of 4ABC. Say,
y^{BC}_{B} y^{BC}_{C} is insidex^{BC}_{B} x^{BC}_{C} and x^{AC}_{A} x^{AC}_{C} is insidey_{A}^{AC}y_{C}^{AC}. Figure 6 illus-
trates a configurationC_{234} as an example from classS_{13}. Take tangent
lines to x, connecting A with x^{BC}_{B} and x^{BC}_{C} (See Figure 5). It fol-
lows from assumption thaty is inside4Ax^{BC}_{B} x^{BC}_{C} . Moreover,yshould
have points in each of two disjoint areas of 4Ax^{BC}_{B} x^{BC}_{C} , whose union
is 4Ax^{BC}_{B} x^{BC}_{C} \x. Then due to Lemma 6.5, the case is dismissed as
impossible for realization.

Figure 5

Figure 6

Configurations from classes S_{5}, S_{12}, S_{28}, S_{31}, S_{32} are dismissed using
similar argument.

3) Consider a class S_{15}. Figure 8 illustrates a configuration C_{135}
as an example from class S_{15}. Take tangent lines to x, connecting A
with x^{BC}_{B} and x^{BC}_{C} (See Figure 7). It follows from assumption that y
should have points in 4x^{AC}_{C} BC and 4Ax^{AB}_{A} C. Moreover, y is inside
4Ax^{BC}_{B} x^{BC}_{C} . So, y should have points in each of two disjoint areas of
4Ax^{BC}_{B} x^{BC}_{C} , whose union is 4Ax^{BC}_{B} x^{BC}_{C} \x. Then due to Lemma 6.5,
the case is dismissed as impossible for realization.

Figure 7

Figure 8

Configurations from classes S_{17}, S_{21}, S_{22}, S_{34}, S_{35} are dismissed using
similar argument.

4) Consider a class S10. Figure 10 illustrates a configurationC225 as
an example from class S10. Take tangent lines tox, connecting B with
x^{AC}_{A} and x^{AC}_{A} , A with x^{BC}_{C} , C with x^{AB}_{B} (See Figure 9). Let Ax^{BC}_{C} and
Cx^{AB}_{B} intersect in a pointO. It follows from assumption thaty should
be in4COx^{BC}_{B} . Moreover,yshould have a point in4x^{AC}_{A} Bx^{AC}_{C} . Then,
since O is not in 4x^{AC}_{A} Bx^{AC}_{C} , due to Lemma 6.6 the case is dismissed
as impossible for realization.

Figure 9

Figure 10

Configurations from a classS_{6} is dismissed using similar argument.

All other configurations satisfy Weak Carousel property. We il-
lustrate realizations of non-dismissed configurations by representative
from each of classes S1, S3, S7, S11, S16, S19, S23, S27, S29, S33, S37 in Ap-
pendix C. Configurations from classesS_{7} andS_{8} are symmetric , so we
could consider {S_{7}, S_{8}} as one symmetric class. Similarly, {S_{3}, S_{4}},
{S_{11}, S_{14}},{S_{16}, S_{18}},{S_{19}, S_{20}},{S_{23}, S_{24}, S_{26}},{S_{29}, S_{30}},{S_{33}, S_{36}}are
symmetric classes.

Thus, cases that are not dismissed are all realizable and Weak Carousel property for Triangles holds in all of them.

6. Lemmas

Definition 6.1. Leta projection point associated with a circle inside a triangle be an endpoint of a perpendicular from a center of the circle to a side of the triangle.

Consider arbitrary triangle 4ABC on a plane. Let g(r_{g}, O_{g}) be a
circle inscribed in 4ABC with a center O_{g} and a radius r_{g}. Let G_{1},
G_{2} and G_{3} be projection points of xonAB,AC and BC respectively.

Lemma 6.2. IfM1 is a point onAG1, then the largest circle associated
with M_{1} and that is completely inside 4ABC is the circle inscribed in
the angle ∠BAC with a projection point M_{1}.

Figure 11

Proof. Let M^{0} ∈ AC s.t. M_{1}M^{0} ⊥ AB. Centers of circles associated
with a projection point M_{1} are on M_{1}M^{0}. Let m(r_{m}, O_{m}) be a circle
with a projection point M_{1} inscribed in ∠BAC.

Suppose there exists a circle n(r_{n}, O_{n}) with a projection point M_{1}
that is completely inside 4ABC and r_{n} > r_{m}. Then O_{n} is in O_{m}M^{0}.
LetN_{2} be a projection point of n onAC.

Let ∠BAC = 2α. Then∠BAOm =∠CAOm =α. Let ∠OmAOn =
β. Then AOn = M1On/sin(α+β) = OnN2/sin(α −β). M1On =
O_{n}N_{2} = r_{n} ⇒ sin(α+β) = sin(α−β) ⇒ β = 0. Hence, O_{m} = O_{n}.
But r_{n} > r_{m} implies that n is not completely inside 4ABC which
contradicts our assumption about n. Therefore, there exists no such
circle n.

Thus, m is the largest circle that is completely inside 4ABC asso-

ciated with the projection point M_{1}.

Lemma 6.3. Consider arbitrary triangle4ABC on the plane. LetDr
be the disc defined by inscribed circle with center O, whose touch point
G_{1} ∈ AB and touch point G_{2} ∈ AC. Consider point E ∈ 4ABC that
belongs to quadrilateral AG1OG2, but lays outside disk Dr. LetDr^{∗} be
any disk with center F such that Dr^{∗} ⊆ 4ABC and E ∈ Dr^{∗}. Then
projection of F to AB belongs to AG_{1} and projection to AC belongs to
AG_{2}.

Figure 12

Proof. Suppose that radius of Dr is r. Then the radius of any disk
Dr^{∗} ⊆ 4ABC, distinct from Dr, is r_{1} < r. We want to show that, for
any pointF outside quadrilateralAG_{1}OG_{2}, the distance|F E|is either
greater than r, or greater than r_{1}, which is the distance fromF to one
of the sides of triangle, hence, the disk with center at F containing
pointE will not be inside 4ABC. Thus, the only possible position for
F will be inside quadrilateralAG_{1}OG_{2}, hence, the projections ofF are
as required.

Draw line (A_{1}B_{1}) parallel to (AB) and line (A_{2}C_{2}) parallel to (AC)
through pointO. If pointF ∈ 4ABC is outside quadrilateralAG1OG2,
then it is either inOG1BB1, in OG2CC2, or in triangle 4OB1C2.

For any point F ∈ OB_{1}C_{2} and any point E taken in smaller angle
G_{1}OG_{2}, in particular, in quadrilateralAG_{1}OG_{2},∠EOF > π/2. Hence,
by cosine theorem, |F E|>|OE|> r.

For two other possibilities of location of F, the argument is similar,
so we consider only one. Let F ∈ OG_{1}BB_{1}. Take point F^{0} ∈ OG_{1},
whose distance to line (AB) is the same as for F: in other words, line
(F F^{0}) is parallel to (AB), and|F^{0}G_{1}| ≤r. Then∠EF^{0}F > π/2, hence,

|F E|>|F^{0}E|. Connect a with O and take E^{0} ∈EO, which belongs to
circle of disk Dr. Then ∠EE^{0}F^{0} > π/2, hence, |F^{0}E|>|F^{0}E^{0}|.

So, it remains to show that |F^{0}E^{0}| ≥ |F^{0}G_{1}| = r_{1}, the latter being
the radius of the largest circle centered at F^{0}, which is inside 4ABC.

This would imply that any circle centered at F with radius > r1 will not be inside triangle, while |F E|> r1.

CasesF^{0} =O andF^{0} =G_{1} are obvious, so we assumeF^{0} ∈OG_{1} and
0< r_{1} < r.

Denote α=∠F^{0}OE^{0} and use cosine theorem:

|F^{0}E^{0}|^{2} =|OE^{0}|^{2}+|OF^{0}|^{2}−2|OE^{0}||OF^{0}|cosα=r^{2}+ (r−r_{1})^{2}−2r(r−
r_{1}) cosα

= 2r(r−r_{1})(1−cosα) +r_{1}^{2}.

Definef(r_{1}) =|F^{0}E^{0}|^{2}−r_{1}^{2}, we need to show thatf(r_{1})≥0. Indeed,
f(r_{1}) = 2r(r−r_{1})(1−cosα)≥0, and we are done.

Lemma 6.4. Considerw=4ABC\g =w_{A}∪w_{B}∪w_{C}, the complement
of g in 4ABC, which is disjoint union of three areas (See Figure 13).

Then any circle y that contains a point in each of areas w_{A}, w_{B}, w_{C}, is
not completely inside 4ABC.

Figure 13

Proof. By 6.3, a position of projection points of circles that contain a
point inw_{A}is restricted toAG_{1}andAG_{2}. Similarly, inw_{B}toBG_{1}, BG_{3}
and in w_{C} toCG_{2}, CG_{3}. Suppose there exists a circle y that contains
points in each of areasw_{A}, w_{B}, w_{C} and completely inside4ABC. Then
y has projection points to AB in AG_{1}, BG_{1}, to BC in BG_{3}, CG_{3} abd
to AC in BC, AG_{2}, CG_{2}. Then, y has projection points G_{1}, G_{2} and
G_{3}. Then, y is centered inO_{g} and have points in w_{A}, w_{B}, w_{C} that are
disjoint fromg. But xis the largest circle that could be inside4ABC.

Therefore there exists no such circle y.

Lemma 6.5. Suppose p(r_{p}, O_{p}) is a circle inscribed in ∠BAC of a
triangle 4ABC. Consider w=4ABC\p=w1∪w2, the complement
of p in 4ABC, which is disjoint union of two areas (See Figure 14).

Then any circle y that contains a point in each of areas w_{1} and w_{2} is
not completely inside 4ABC.

Figure 14

Figure 15

Proof. LetP_{1} and P_{2} be projection points of p toAB and AC respec-
tively. Draw tangent lines CC1 and BB1 to p and let P3 and P4 be
projection points ofp toBB1 and CC1 respectively. LetM be a point
of intersection of CC_{1} and BB_{1}.

Suppose there exist a circle y that contains some points E_{1} and E_{2}
fromw_{1} and w_{2} respectively.

Case 1. E_{2} is in w_{2}∩ 4ACC_{1}.

Consider 4ACC_{1}: y contains E_{1} fromw_{1}, then due to 6.3, projection
points of y to AB and AC are restricted to AP_{1} and AP_{2}. If E_{2} is in
C_{1}P_{1}P_{4}\p, then projection points of y to AB and CC_{1} are restricted
to C_{1}P_{1} and C_{1}P_{4}. If E_{2} is in CP_{2}P_{4}\p, then projection points of y
to AC and CC_{1} are restricted to C_{P}_{2} and C_{P}_{4}. Then, from a similar
argument made in 6.4, there exists no such circle y.

The argument is similar when E_{2} is in w_{2}∩ 4ABB_{1}.
Case 2. E2 is in 4BM C.

Consider g(rg, Og) that is inscribed in 4ABC. Then E2 is either in 4BM C∩g or in area 4BM C\g.

If E_{2} is in area 4BM C disjoint from g, then Then, from a similar

argument made in 6.4, there exists no such circle y.

If E_{2} is in 4BM C∩g, then y intersect p in more than two points. It
contradicts to two circles intersecting in at most two points.

Therefore, there exists no such y.

Lemma 6.6. Suppose s is a circle inscribed in ∠A_{1}AA_{2} < π. Circle
s divides ∠A_{1}AA_{2} in two disjoint areas w_{1} and w_{2} (See Figure 16).

Then tangent lines to any point ofs bordering w_{1} and to any point of s
bordering w_{2} intersect in a point outside the interior area of ∠A_{1}AA_{2}.

Figure 16

Proof. Let S_{1} and S_{2} be touch points of s with AA_{1} and AA_{2} respec-
tively. Let P_{1} be a point on s that coincides with S_{1} at first. Let CC_{1}
be tangent line to s at P_{1}. If we move P_{1} on part of s bordering w_{1},
then CC_{1} moves from a position of AA_{2} anticlockwise until it becomes
AA_{1}.

Let P_{2} be a point on s that coincides with S_{2} at first. Let BB_{1} be
tangent line tos at P_{2}. If we move P_{2} on part of s bordering w_{2}, then
BB_{1} moves from a position of AA_{1} clockwise until it becomes AA_{2}.

Let points of intersections ofCC_{1} andBB_{1},BB_{1} andAA_{1},BB_{1} and
AA_{2}, CC_{1} and AA_{1}, CC_{1} and AA_{2} be O, M_{1}, M_{2}, N_{1} and N_{2} respec-
tively. Then position of point O moves on the line BB_{1} toward M_{2}
until CC1 becomes AA2. Similarly O moves on the line CC1 toward
N2 untilBB1 becomes AA2.

Then, O could not be inside interior area of ∠A_{1}AA_{2}.

7. Weak 2-Carousel rule for a geometry of circles on a plane

Theorem 7.1. Every convex geometry of circles in R^{2} satisfies Weak
2-Carousel rule.

Figure 17

Proof. Consider circles x, y that are in a convex hull of circles a, b, c.

be circles (See Figure 17). x, y ∈CH{a, b, c}

Draw tangent lines toa, b, cand denote point of intersection by A, B
and C (17). Let w_{A}, w_{B}, w_{C} denote disjoint areas as shown on the
picture.

CH{a, b, c}=CH{A, B, C}\{w_{A}∪w_{B}∪w_{C}}, sox,y∈CH{A, B, C}

We could use Theorem 5.1, forx, y, and a set of pointsS={A, B, C}.

By Theorem 5.1, eitherx is in a convex hull of two points from S and y, or y is in a convex hull of two points from S and x.

Say, y∈CH{x, B, C}. But y∈CH{x, B, C} ⇒ y∈CH{x, b, c}.

Therefore, either x is in a convex hull of two circles from {a, b, c}

and y, or y is in a convex hull of two circles from{a, b, c} and x.

8. Concluding Remarks

We demonstrated an example of convex geometry of cdim = 6 that fails Weak 2-Carousel property and therefore could not be represented by circles on a plane. This convex geometry fails 2-Carousel property, so it is not also weakly represented by affine convex geometries on a plane ([1]). Hence, we ask the following problem:

Problem 8.1. Is a convex geometry of cdim = 3,4 or 5 strongly rep- resented by a geometry of circles on a plane?

Since, we proved existence of geometries that are not strongly repre-
sentable by circles in R^{2}, we would like to consider higher dimensions
of a space. Therefore, we ask the following question:

Problem 8.2. Is every finite convex geometry could be strongly repre-
sented by balls in R^{n}

It is of interest to find some relationship, if such exists, between a convex dimension of a convex geometry and a dimension of a space for a representation.

Problem 8.3. In which dimension of a space, a convex geometry with cdim=k, k∈N has a representation?

9. Acknowledgements

I express sincere gratitude to my supervisor Dr. Kira Adaricheva for the continuous support and sharing extensive knowledge in the field of convex geometries. Thanks to Dr. Kira Adaricheva for providing a shorter proof of Lemma 6.3. I would also like to thank Dr. Rustem Takhanov for being a second reader and giving valuable comments regarding the paper. I thank my collaborator Zhanbota Myrzakul with whom we were learning a theory of convex geometries throughout a year.

10. Appendices Appendix A

Figure 18
Appendix B
S_{1} ={C_{121}, C_{122}, C_{112}, C_{221}, C_{211}, C_{212}}
S_{2} ={C_{111}, C_{222}}

S3 ={C123, C142, C214, C231, C312, C421}
S4 ={C124, C132, C213, C241, C321, C412}
S_{5} ={C_{113}, C_{131}, C_{224}, C_{242}, C_{311}, C_{422}}
S_{6} ={C_{114}, C_{141}, C_{223}, C_{232}, C_{322}, C_{411}}
S7 ={C125, C162, C216, C251, C512, C621}
S_{8} ={C_{126}, C_{152}, C_{215}, C_{261}, C_{521}, C_{612}}
S_{9} ={C_{115}, C_{151}, C_{226}, C_{262}, C_{511}, C_{622}}
S_{10}={C_{116}, C_{161}, C_{225}, C_{252}, C_{522}, C_{611}}
S_{11}={C_{133}, C_{244}, C_{313}, C_{331}, C_{424}, C_{442}}
S_{12}={C_{134}, C_{243}, C_{324}, C_{341}, C_{413}, C_{432}}
S_{13}={C_{143}, C_{234}, C_{314}, C_{342}, C_{423}, C_{431}}
S_{14}={C_{144}, C_{233}, C_{323}, C_{332}, C_{414}, C_{441}}
S_{15}={C_{135}, C_{246}, C_{351}, C_{462}, C_{513}, C_{624}}
S_{16}={C_{136}, C_{245}, C_{361}, C_{452}, C_{524}, C_{613}}

S17={C145, C236, C362, C451, C514, C623}
S_{18}={C_{146}, C_{235}, C_{352}, C_{461}, C_{523}, C_{614}}
S_{19}={C_{163}, C_{254}, C_{316}, C_{425}, C_{542}, C_{631}}
S20={C164, C253, C325, C416, C532, C664}
S21={C153, C264, C315, C426, C531, C642}
S_{22}={C_{154}, C_{263}, C_{326}, C_{415}, C_{541}, C_{632}}
S23={C165, C256, C516, C562, C625, C651}
S24={C166, C255, C525, C552, C616, C661}
S_{25}={C_{155}, C_{266}, C_{551}, C_{515}, C_{626}, C_{662}}
S_{26}={C_{156}, C_{265}, C_{526}, C_{561}, C_{615}, C_{652}}
S27={C333, C444}

S_{28}={C_{334}, C_{343}, C_{344}, C_{433}, C_{434}, C_{443}}
S_{29}={C_{335}, C_{353}, C_{446}, C_{464}, C_{533}, C_{644}}
S30={C336, C363, C445, C454, C544, C633}
S31={C345, C364, C436, C453, C534, C643}
S_{32}={C_{346}, C_{354}, C_{435}, C_{463}, C_{543}, C_{634}}
S33={C365, C456, C536, C564, C645, C653}
S34={C366, C455, C545, C554, C63, C636}
S_{35}={C_{355}, C_{466}, C_{535}, C_{553}, C_{646}, C_{664}}
S_{36}={C_{356}, C_{365}, C_{546}, C_{563}, C_{635}, C_{654}}
S37={C556, C565, C566, C655, C656, C665}
S_{38}={C_{555}, C_{666}}

Appendix C

Figure 19. S_{1}

Figure 20. S_{3}

Figure 21. S_{7}

Figure 22. S_{11}

Figure 23. S_{16}

Figure 24. S_{19}

Figure 25. S_{23}

Figure 26. S27

Figure 27. S_{29}

Figure 28. S33

Figure 29. S_{37}

References

[1] K. V. Adaricheva,Representing Finite Convex Geometries by Relatively Convex Sets. European Journal of Combinatorics 37 (2014), 68-78.

[2] K. V. Adaricheva,Join-semidistributive Lattices of Relatively Convex Sets. Con- tributions to General Algebra 14, Proceedings of the Olomouc Conference 2002 (AAA 64) and the Potsdam conference 2003 (AAA 65), Verlag Johannes Heyn, Klagenfurt, 2004, 1-14.

[3] K. V. Adaricheva, V. Gorbunov and V. Tumanov,Join Semidistributive Lattices and Convex Geometries. Advances in Mathematics 173 (2003), 1-49.

[4] K. V. Adaricheva and M. Wild,Realization of Abstract Convex Geometries by Point Configurations. Part I.. European Journal of Combinatorics 31 (2010), 379-400.

[5] G. Czedli, Finite Convex Geometries of Circles. Discreet Mathematics 330 (2014), 61-75.

[6] Private communication of Czedli with Adaricheva in January, 2013

[7] P. H. Edelman and R. Jamison,The Theory of Convex Geometries. Geom Ded- icata 19 (1985), 247-274.

[8] K. Kashiwabara,M. Nakamura and Y. Okamoto, The Affine Representation Theorem for Abstract Convex Geometries. Computational Geometry 30 (2005), 129-144.

[9] M. Richter and L.G. Rogers, Embedding Convex Geometries and a Bound on Convex Dimension. 2015 http://arxiv.org/abs/1502.01941.