Representation of Convex Geometries

(1)

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

(2)

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 combinatorial 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 example: 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 geometry inRⁿ. 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 satisfying 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]

(3)

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 convex 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 geometrical 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).

(4)

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 alignment 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 alignment:

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₁ = (X,F₁) is a sub-geometry of G₂ = (Y,F₂) if there is a one-to-one map f :F₁ → F₂ 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₁...a_n} for some a₁, ...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₁...a_n} or y ∈ ϕ{x, a₁...a_n} for some a₁, ...a_n∈S.

Definition 2.10. Consider F = (X, chc), whereX is a set of circles in R² 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.

(5)

Definition 2.11. Consider F = (A, chc) a convex geometry of circles 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 particular 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 geometries 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 convex 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

(6)

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₀(Rⁿ, X) = (X, ch), whereX is a set of points inRⁿ 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 convex geometry in C0(Rⁿ, 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 representation, 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 geometries in Rⁿ was raised by Edelman and Jamison in 1985 (See Problem 1 in [7]). The authors in [7] noted that such characterization problem 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² ([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

(7)

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ⁿ 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 geometries 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ⁿ

(8)

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⁰ = (X,F⁰), where X = {a₀, a₁, a₂, x, y} is a set of points on a plane as shown in Figure 1. Then, F⁰ =P(X)\{a0a1a2, a0a2x, a0a1y, a0a1a2x, a0a1a2y}.

Figure 1

Consider G= (X,F), whereF =P(X)\{a₀a₁a₂, a₀a₁a₂x, a₀a₁a₂y}, which we get by adding {a₀a₂x} and {a₀a₁y} to the alignment F⁰ of affine convex geometry G⁰.

It could be directly checked that F for G satisfies the properties of alignments from Definition 2.3. Initial alignment F⁰ satisfies the required properties since G⁰ is affine convex geometry. We add {a₀a₂x}

and {a₀a₁y} to F⁰. All subsets of added sets are in F and their intersection 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ⁿ. So, G could not be weakly represented by affine convex geometries in R². 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₀a₁a₂) since ϕ(a₀a₁a₂) =X.

ϕ(a_ia_jx) = {a_ia_jx}, fori, j = 0,1,2 ϕ(a_ia_jy) ={a_ia_jy}, 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₀, a₁, a₂} but x is not in a closure of any two from {a₀, a₁, a₂} 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.

(9)

5. Weak Carousel Property for Triangles

Theorem 5.1. Every configuration of two circles and a set of three distinct points in R² 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₁ and y₁ in Figure 18 are first in ordersx₁x₂ and iny₁y₂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₅₄₆.

Six possible configurations for each side produce 216 possible configurations of projections of x and y for 4ABC. We reduce 216 configurations to 38 classes up to isomorphism. Say, C₂₄₁ and C₁₂₄ 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.

(10)

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ÂC_C is earlier than yÂC_A . It is clear that, say, for x to be in a convex hull of y and B, C, xÂC_A must be earlier than yÂC_A and xÂB_A must be later thany_AÂB. On the other hand, x is not in a convex hull ofA,B and y, since both x^BC_C and xÂC_C are earlier than y_C^BC and y_CÂC respectively.

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

1) Consider a class S₂ 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ÂC_A is later than xÂC_A , and y_CÂC is later than xÂC_C on AC). Figure 4 illustrates a configuration C₂₂₂ as an example from a class S₂. 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⁰B⁰C⁰ formed by these three lines. It follows from assumption thatyis inside 4A⁰B⁰C⁰. Moreover, y should have points in each of three disjoint areas of4A⁰B⁰C⁰, whose union is4ABC\x. Then due to Lemma 6.4, the case is dismissed as impossible for realization.

Figure 3

(11)

Figure 4

Configurations from classes S₉, S₂₅, S₃₈ are dismissed using similar argument.

2) Consider a classS₁₃ when a segment of a projection of y is inside a segment of a projection of x on one side of 4ABC but a projection 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ÂC_A xÂC_C is insidey_AÂCy_CÂC. Figure 6 illustrates a configurationC₂₃₄ as an example from classS₁₃. Take tangent lines to x, connecting A with x^BC_B and x^BC_C (See Figure 5). It follows 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

(12)

Figure 6

Configurations from classes S₅, S₁₂, S₂₈, S₃₁, S₃₂ are dismissed using similar argument.

3) Consider a class S₁₅. Figure 8 illustrates a configuration C₁₃₅ as an example from class S₁₅. 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

(13)

Figure 8

Configurations from classes S₁₇, S₂₁, S₂₂, S₃₄, S₃₅ 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ÂC_A and xÂC_A , A with x^BC_C , C with xÂB_B (See Figure 9). Let Ax^BC_C and CxÂB_B intersect in a pointO. It follows from assumption thaty should be in4COx^BC_B . Moreover,yshould have a point in4xÂC_A BxÂC_C . Then, since O is not in 4xÂC_A BxÂC_C , due to Lemma 6.6 the case is dismissed as impossible for realization.

Figure 9

(14)

Figure 10

Configurations from a classS₆ is dismissed using similar argument.

All other configurations satisfy Weak Carousel property. We illustrate 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₇ andS₈ are symmetric , so we could consider {S₇, S₈} as one symmetric class. Similarly, {S₃, S₄}, {S₁₁, S₁₄},{S₁₆, S₁₈},{S₁₉, S₂₀},{S₂₃, S₂₄, S₂₆},{S₂₉, S₃₀},{S₃₃, S₃₆}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₁, G₂ and G₃ be projection points of xonAB,AC and BC respectively.

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

(15)

Figure 11

Proof. Let M⁰ ∈ AC s.t. M₁M⁰ ⊥ AB. Centers of circles associated with a projection point M₁ are on M₁M⁰. Let m(r_m, O_m) be a circle with a projection point M₁ inscribed in ∠BAC.

Suppose there exists a circle n(r_n, O_n) with a projection point M₁ that is completely inside 4ABC and r_n > r_m. Then O_n is in O_mM⁰. LetN₂ be a projection point of n onAC.

Let ∠BAC = 2α. Then∠BAOm =∠CAOm =α. Let ∠OmAOn = β. Then AOn = M1On/sin(α+β) = OnN2/sin(α −β). M1On = O_nN₂ = 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₁.

Lemma 6.3. Consider arbitrary triangle4ABC on the plane. LetDr be the disc defined by inscribed circle with center O, whose touch point G₁ ∈ AB and touch point G₂ ∈ 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₁ and projection to AC belongs to AG₂.

(16)

Figure 12

Proof. Suppose that radius of Dr is r. Then the radius of any disk Dr^∗ ⊆ 4ABC, distinct from Dr, is r₁ < r. We want to show that, for any pointF outside quadrilateralAG₁OG₂, the distance|F E|is either greater than r, or greater than r₁, 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₁OG₂, hence, the projections ofF are as required.

Draw line (A₁B₁) parallel to (AB) and line (A₂C₂) 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₁C₂ and any point E taken in smaller angle G₁OG₂, in particular, in quadrilateralAG₁OG₂,∠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₁BB₁. Take point F⁰ ∈ OG₁, whose distance to line (AB) is the same as for F: in other words, line (F F⁰) is parallel to (AB), and|F⁰G₁| ≤r. Then∠EF⁰F > π/2, hence,

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

So, it remains to show that |F⁰E⁰| ≥ |F⁰G₁| = r₁, the latter being the radius of the largest circle centered at F⁰, 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⁰ =O andF⁰ =G₁ are obvious, so we assumeF⁰ ∈OG₁ and 0< r₁ < r.

(17)

Denote α=∠F⁰OE⁰ and use cosine theorem:

|F⁰E⁰|² =|OE⁰|²+|OF⁰|²−2|OE⁰||OF⁰|cosα=r²+ (r−r₁)²−2r(r− r₁) cosα

= 2r(r−r₁)(1−cosα) +r₁².

Definef(r₁) =|F⁰E⁰|²−r₁², we need to show thatf(r₁)≥0. Indeed, f(r₁) = 2r(r−r₁)(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_Ais restricted toAG₁andAG₂. Similarly, inw_BtoBG₁, BG₃ and in w_C toCG₂, CG₃. 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₁, BG₁, to BC in BG₃, CG₃ abd to AC in BC, AG₂, CG₂. Then, y has projection points G₁, G₂ and G₃. 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₁ and w₂ is not completely inside 4ABC.

(18)

Figure 14

Figure 15

Proof. LetP₁ and P₂ be projection points of p toAB and AC respectively. 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₁ and BB₁.

Suppose there exist a circle y that contains some points E₁ and E₂ fromw₁ and w₂ respectively.

Case 1. E₂ is in w₂∩ 4ACC₁.

Consider 4ACC₁: y contains E₁ fromw₁, then due to 6.3, projection points of y to AB and AC are restricted to AP₁ and AP₂. If E₂ is in C₁P₁P₄\p, then projection points of y to AB and CC₁ are restricted to C₁P₁ and C₁P₄. If E₂ is in CP₂P₄\p, then projection points of y to AC and CC₁ are restricted to C_P₂ and C_P₄. Then, from a similar argument made in 6.4, there exists no such circle y.

The argument is similar when E₂ is in w₂∩ 4ABB₁. 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₂ is in area 4BM C disjoint from g, then Then, from a similar

(19)

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

If E₂ 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₁AA₂ < π. Circle s divides ∠A₁AA₂ in two disjoint areas w₁ and w₂ (See Figure 16).

Then tangent lines to any point ofs bordering w₁ and to any point of s bordering w₂ intersect in a point outside the interior area of ∠A₁AA₂.

Figure 16

Proof. Let S₁ and S₂ be touch points of s with AA₁ and AA₂ respectively. Let P₁ be a point on s that coincides with S₁ at first. Let CC₁ be tangent line to s at P₁. If we move P₁ on part of s bordering w₁, then CC₁ moves from a position of AA₂ anticlockwise until it becomes AA₁.

Let P₂ be a point on s that coincides with S₂ at first. Let BB₁ be tangent line tos at P₂. If we move P₂ on part of s bordering w₂, then BB₁ moves from a position of AA₁ clockwise until it becomes AA₂.

Let points of intersections ofCC₁ andBB₁,BB₁ andAA₁,BB₁ and AA₂, CC₁ and AA₁, CC₁ and AA₂ be O, M₁, M₂, N₁ and N₂ respectively. Then position of point O moves on the line BB₁ toward M₂ 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₁AA₂.

(20)

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

Theorem 7.1. Every convex geometry of circles in R² 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 represented by a geometry of circles on a plane?

(21)

Since, we proved existence of geometries that are not strongly representable by circles in R², 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 represented by balls in Rⁿ

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.

(22)

10. Appendices Appendix A

Figure 18 Appendix B S₁ ={C₁₂₁, C₁₂₂, C₁₁₂, C₂₂₁, C₂₁₁, C₂₁₂} S₂ ={C₁₁₁, C₂₂₂}

S3 ={C123, C142, C214, C231, C312, C421} S4 ={C124, C132, C213, C241, C321, C412} S₅ ={C₁₁₃, C₁₃₁, C₂₂₄, C₂₄₂, C₃₁₁, C₄₂₂} S₆ ={C₁₁₄, C₁₄₁, C₂₂₃, C₂₃₂, C₃₂₂, C₄₁₁} S7 ={C125, C162, C216, C251, C512, C621} S₈ ={C₁₂₆, C₁₅₂, C₂₁₅, C₂₆₁, C₅₂₁, C₆₁₂} S₉ ={C₁₁₅, C₁₅₁, C₂₂₆, C₂₆₂, C₅₁₁, C₆₂₂} S₁₀={C₁₁₆, C₁₆₁, C₂₂₅, C₂₅₂, C₅₂₂, C₆₁₁} S₁₁={C₁₃₃, C₂₄₄, C₃₁₃, C₃₃₁, C₄₂₄, C₄₄₂} S₁₂={C₁₃₄, C₂₄₃, C₃₂₄, C₃₄₁, C₄₁₃, C₄₃₂} S₁₃={C₁₄₃, C₂₃₄, C₃₁₄, C₃₄₂, C₄₂₃, C₄₃₁} S₁₄={C₁₄₄, C₂₃₃, C₃₂₃, C₃₃₂, C₄₁₄, C₄₄₁} S₁₅={C₁₃₅, C₂₄₆, C₃₅₁, C₄₆₂, C₅₁₃, C₆₂₄} S₁₆={C₁₃₆, C₂₄₅, C₃₆₁, C₄₅₂, C₅₂₄, C₆₁₃}

(23)

S17={C145, C236, C362, C451, C514, C623} S₁₈={C₁₄₆, C₂₃₅, C₃₅₂, C₄₆₁, C₅₂₃, C₆₁₄} S₁₉={C₁₆₃, C₂₅₄, C₃₁₆, C₄₂₅, C₅₄₂, C₆₃₁} S20={C164, C253, C325, C416, C532, C664} S21={C153, C264, C315, C426, C531, C642} S₂₂={C₁₅₄, C₂₆₃, C₃₂₆, C₄₁₅, C₅₄₁, C₆₃₂} S23={C165, C256, C516, C562, C625, C651} S24={C166, C255, C525, C552, C616, C661} S₂₅={C₁₅₅, C₂₆₆, C₅₅₁, C₅₁₅, C₆₂₆, C₆₆₂} S₂₆={C₁₅₆, C₂₆₅, C₅₂₆, C₅₆₁, C₆₁₅, C₆₅₂} S27={C333, C444}

S₂₈={C₃₃₄, C₃₄₃, C₃₄₄, C₄₃₃, C₄₃₄, C₄₄₃} S₂₉={C₃₃₅, C₃₅₃, C₄₄₆, C₄₆₄, C₅₃₃, C₆₄₄} S30={C336, C363, C445, C454, C544, C633} S31={C345, C364, C436, C453, C534, C643} S₃₂={C₃₄₆, C₃₅₄, C₄₃₅, C₄₆₃, C₅₄₃, C₆₃₄} S33={C365, C456, C536, C564, C645, C653} S34={C366, C455, C545, C554, C63, C636} S₃₅={C₃₅₅, C₄₆₆, C₅₃₅, C₅₅₃, C₆₄₆, C₆₆₄} S₃₆={C₃₅₆, C₃₆₅, C₅₄₆, C₅₆₃, C₆₃₅, C₆₅₄} S37={C556, C565, C566, C655, C656, C665} S₃₈={C₅₅₅, C₆₆₆}

(24)

Appendix C

Figure 19. S₁

Figure 20. S₃

Figure 21. S₇

(25)

Figure 22. S₁₁

Figure 23. S₁₆

Figure 24. S₁₉

(26)

Figure 25. S₂₃

Figure 26. S27

Figure 27. S₂₉

(27)

Figure 28. S33

Figure 29. S₃₇

(28)

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.