Convex geometries representable with colors, by ellipses on the plane, and impossible by circles

Kira Adaricheva Department of Mathematics, Hofstra University, Hempstead, NY 11549, USA ([email protected]) Evan Daisy Amherst College, USA Ayush Garg Indian Institute of Technology, Delhi, India Zachary King Grace Ma University of Notre Dame, South Bend, USA Michelle Olson California State University, Fullerton, USA Cat Raanes Carnegie Mellon University, Pittsburgh, USA James Thompson University of North Carolina, Chapell Hill, USA

(August 2020 - May 2022)

Abstract

A convex geometry is a closure system satisfying the anti-exchange property. This paper, following the work of K. Adaricheva and M. Bolat (2016) and the Polymath REU 2020 team, continues to investigate representations of convex geometries on a 5-element base set. It introduces several properties: the opposite property, nested triangle property, area Q property, and separation property, of convex geometries of circles on a plane, preventing this representation for numerous convex geometries on a 5-element base set. It also demonstrates that all 672 convex geometries on a 5-element base set have a representation by ellipses, as given in the appendix for those without a known representation by circles, and introduces a method of expanding representation with circles by defining unary predicates, shown as colors.

1 Introduction

This paper follows the first paper of the convex geometries team [14] developed during the Polymath REU - 2020 project, see more details in [1].

In both papers we addressed the problem raised in Adaricheva and Bolat [2]: whether all convex geometries with convex dimension at most 5 are representable by circles on the plane using the closure operator of convex hull for circles.

A convex geometry is a closure system $(X,\phi)$ , where closure operator $\phi$ satisfies the anti-exchange property. The survey paper of Edelman and Jamison [9] was instrumental to start off the study of finite convex geometries, which are also the dual systems to antimatroids. The study of infinite convex geometries was initiated in Adaricheva, Gorbunov and Tumanov [3]. To see the development of the topic, including infinite convex geometries, one needs to consult the more recent survey Adaricheva and Nation [4].

In [7] G. Czédli proposed representation of convex geometries by interpreting elements of base set $X$ as circles on the plane, and closure operator $\phi$ as a convex hull operator acting on circles. He also showed that all finite convex geometries with convex dimension at most 2 can be represented by circles on the plane. The parameter $cdim$ of convex geometry represents the diversity of closed sets with respect to closure operator $\phi$ by measuring the size of maximal anti-chain of closed sets, see Edelman and Saks [10]. In Adaricheva and Bolat [2], it was found that there is an obstruction for representation of convex geometries by circles on the plane, in the form of the Weak Carousel property, which allowed the authors to build an example of a convex geometry on a 5-element set of $cdim=6$ .

In [14] it was discovered that all convex geometries for $|X|=4$ are representable by circles on the plane, and among 672 non-isomorphic geometries for $|X|=5$ , 621 were represented, while 49 were deemed “impossible”, i.e. no circle representation was found for them. Finally, it was proved in [14] that 7 of 49 impossible geometries cannot be represented due to the Triangle property, in addition to one from [2] due to the Weak Carousel property. In particular, some geometries are non-representable due to the Triangle property had $cdim=4,5$ .

In the current paper, we prove four new geometric properties related to circles on the plane that allow us to prove an additional 30 of the 49 geometries from the impossible list given in [14] are not representable.

We identify these geometries by their number in the list as generated in [14], and additionally by their tight implications, sometimes with the elements of the set relabeled for clarity.

1) Opposite Property (Theorem 1 and Corollary 2) implies that the following geometries are not representable:

G46,G60,G74,G84,G114,G115,G153

2) Nested Triangles Property (Theorem 7 and Corollary 9):

	$\displaystyle G12,G15,G18,G21,G23,G26,G27,G33,G35,$
	$\displaystyle G45,G47,G49,G56,G60,G70,G89,G94,G134$

3) Area Q Property (Theorem 10 and Corollary 11):

G74,G96,G105,G143,G147,G206,G235,G351

4) Separation Property (Theorem 5 and Corollary 6):

G14,G23,G26,G39,G54.

Note that these three lists slightly overlap, with several of the geometries appearing in more than one list, and a few appeared earlier due to the Triangle Property in [14].

This provides a partial answer to Question 2 in [14].

The following 11 impossible geometries comprise still unproven cases:

G43,G57,G69,G87,G95,G122,G129,G132,G161,G175,G211

Through the work on these “impossible” geometries, we used a program, previously developed for [14], which searched for all convex geometries that satisfied a given list of implications. In addition, we also used the GeoGebra software [11], to help with proofs and various representations.

Finally, we address two alternate schemes of representation.

In section 6 we discuss representation of geometries by ellipses on the plane. It was shown in J. Kincses [12] that not all geometries can be represented by ellipses. However, we demonstrate in Appendix A that all 49 geometries on a 5-element set that were deemed “impossible” for circle representation in [14], in fact, have representation by ellipses.

Question 1.

What is the smallest cardinality of the base set and the smallest convex dimension of a geometry that cannot be represented by ellipses on the plane?

In the last section 7 we introduce a new type of representation of geometries using unary predicates on the base set that can be interpreted as colors. In Appendix B we give representation of all 49 “impossible” convex geometries on a 5-element set using colored circles. It is also shown in section 7 that one of the geometries, G18, cannot be represented with two colors only. The rest of the “impossible” geometries are represented with 2 colors only. Note that G18 has $cdim=6$ , thus, we may ask:

Question 2.

Can all convex geometries of convex dimension 4 or 5 be represented by circles with 2 colors only?

2 Terminology and known results

A convex geometry is a special case of a closure system. It can be defined through a closure operator, or through an alignment.

Definition 1.

Let $X$ be a set. A mapping $\varphi\colon 2^{X}\to 2^{X}$ is called a closure operator, if for all $Y,Z\in 2^{X}$ :

1.

$Y\subseteq\varphi(Y)$
2.

if $Y\subseteq Z$ then $\varphi(Y)\subseteq\varphi(Z)$
3.

$\varphi(\varphi(Y))=\varphi(Y)$

A subset $Y\subseteq X$ is closed if $\varphi(Y)=Y$ . The pair $(X,\varphi)$ , where $\varphi$ is a closure operator, is called a closure system.

Definition 2.

Given any (finite) set $X$ , an alignment on $X$ is a family $\mathcal{F}$ of subsets of $X$ which satisfies two properties:

1.

$X\in\mathcal{F}$
2.

If $Y,Z\in\mathcal{F}$ then $Y\cap Z\in\mathcal{F}$ .

Closure systems are dual to alignments in the following sense:

Often, a closure operator is described by the means of implications. For example $Y\rightarrow z$ means that $z\in\varphi(Y)$ , for the underlying closure operator $\varphi$ . Note that every closure operator can be expressed by some set of implications, for example, $\Sigma_{\varphi}=\{A\rightarrow\varphi(A):A\in 2^{X}\}$ . On the other hand, given any set of implications $\{A\rightarrow B:A,B\subseteq X,B\not=\emptyset\}$ , one can find a unique minimal closure operator $\varphi$ such that $B\subseteq\varphi(A)$ .

If $(X,\varphi)$ is a closure system, one can define a family of closed sets $\mathcal{F}:=\{Y\subseteq X:\varphi(Y)=Y\}$ . Then $\mathcal{F}$ is an alignment.

If $\mathcal{F}$ is an alignment, then define $\varphi:2^{X}\rightarrow 2^{X}$ in the following manner:

for all $Y\subseteq X$ , let $\varphi(Y):=\bigcap\{Z\in\mathcal{F}:Y\subseteq Z\}$ . Then $(X,\varphi)$ is a closure system.

A useful perspective on closure systems is provided by its implications. Given a closure system $(X,\varphi)$ , an ordered pair $(A,B)$ , where $A,B\in 2^{X}\setminus\{\emptyset\}$ , also denoted $A\to B$ , is an implication if $B\subseteq\varphi(A)$ .

A set of implications fully defining closure operator $\varphi$ is often referred to as implicational basis of a closure system. The recent exposition on implicational bases is given in Adaricheva and Nation [5].

Definition 3.

A closure system $(X,\varphi)$ is called a convex geometry if

1.

$\varphi(\emptyset)=\emptyset$
2.

For any closed set $Y\subseteq X$ and any distinct points $x,y\in X\setminus Y,$ if $x\in\varphi(Y\cup\{y\})$ then $y\not\in\varphi(Y\cup\{x\})$ .

The second property in this definition is called the Anti-Exchange Property.

We can use duality between closure operators and alignments to provide another definition of a convex geometry.

Definition 4.

A closure system $(X,\varphi)$ is a convex geometry iff the corresponding alignment $\mathcal{F}$ satisfies the following two properties:

1.

$\emptyset\in\mathcal{F}$
2.

If $Y\in\mathcal{F}$ and $Y\neq X$ then $\exists a\in X\setminus Y$ s.t. $Y\cup\{a\}\in\mathcal{F}$ .

A particular example of a closure operator on a set is the convex hull operator, where the base set $X$ is a set of points in Euclidean space $\mathbb{R}^{n}$ . For the goals of this paper we use only the plane, i.e. the space $\mathbb{R}^{2}$ .

Definition 5.

A set $S$ in $\mathbb{R}^{2}$ is called convex if for any two points $p,q\in S$ , the line segment connecting $p$ and $q$ is also contained in $S$ .

Definition 6.

Given set $S$ of points in $\mathbb{R}^{2}$ , the convex hull of $S$ , in notation $\operatorname{CH}(S)$ , is the intersection of all convex sets in $\mathbb{R}^{2}$ which contain $S$ .

Thus, $\operatorname{CH}$ can be thought as a closure operator acting on $\mathbf{R}^{2}$ .

Finally, we want to recall the definition of the convex hull operator for circles introduced in Czédli [7].

If $x$ is a circle on the plane, then by $\tilde{x}$ we denote a set of points belonging to $x$ . We allow a circle to have a radius $0$ , in which case it is a point.

Definition 7.

Let $X$ be a finite set of circles in $\mathbb{R}^{2}$ . Define the operator $\operatorname{ch}_{c}:2^{X}\rightarrow 2^{X}$ , a convex hull operator for circles, as follows:

\operatorname{ch}_{c}(Y)=\{x\in X:\tilde{x}\subseteq\operatorname{CH}(\bigcup_{y\in Y}\tilde{y})\},

for any $Y\in 2^{X}$ .

For example, $a,e\in\operatorname{ch}_{c}(b,c,d)$ on Figure 1(a), while $a\not\in\operatorname{ch}_{c}(b,c,d)$ , $e\in\operatorname{ch}_{c}(b,c,d)$ in Figure 1(b).

We think of any circle $d$ as a closed set of points (in standard topology of $\mathbb{R}^{2}$ ), and we use $Circ(d)$ for the boundary of $d$ , which is included in $d$ . Often we will be using the same notation $d$ for an element of convex geometry of circles, but also as the set of points in $\mathbb{R}^{2}$ , thus avoiding notation $\tilde{d}$ . For example, $abc\rightarrow d$ means that $d\in\operatorname{ch}_{c}(a,b,c)$ in convex geometry of circles, but $c\subseteq d$ should be understood as $\tilde{c}\subseteq\tilde{d}$ .

Refer to caption — (a) Circle $a$ is in the convex hull of $b,c,d$

We often will be writing $\operatorname{CH}(Y)$ , for the subset $Y$ of circles, instead of $\operatorname{CH}(\bigcup_{y\in Y}\tilde{y})\}$ . For example, $\operatorname{CH}(a,b,c)$ for circles $a,b,c\in X$ represents the convex set of points $\operatorname{CH}(\tilde{a}\cup\tilde{b}\cup\tilde{c})$ .

The following statement is modified Lemma 5.1 in [2].

Lemma 1.

Let $a,b,c$ be three circles on the plane such that none is included into another. Then there are three different types of configurations formed by $a,b,c$ :

(1)

$\operatorname{CH}(x,y,z)=\operatorname{CH}(y,z)$ , for some labeling of $a,b,c$ by $x,y,z$ as on Figure 2;
(2)

$\operatorname{CH}(x,y,z)=\operatorname{CH}(x,y)\cup\operatorname{CH}(y,z)$ , for some labeling of $a,b,c$ by $x,y,z$ , as on Figure 2 or Figure 2.
(3)

$\operatorname{CH}(x,y,z)\not=\operatorname{CH}(x,y)\cup\operatorname{CH}(x,z)$ , for any labeling of $a,b,c$ by $x,y,z$ , as on Figure 2 or Figure 2.

Figure 2:

Figure 3:

Figure 4:

Figure 5:

Figure 6:

Definition 8.

Let $x,y,z$ be circles in configuration 1 or 2. We say that circle $y$ is in the center (of configuration), if $\operatorname{CH}(x,y,z)=\operatorname{CH}(x,y)\cup\operatorname{CH}(y,z)$ or $y\in ch_{c}(x,z)$ . We call circles $x$ and $z$ external circles.

Definition 9.

Let $x,y,z$ be in configuration 2 such that $y$ has a touching point on only one tangent of $x,z$ and 2 points of intersection on the other tangent; then $x,y,z$ is in limit case 2.

Lemma 2.

Suppose $p$ is a circle inscribed in $\angle{A}$ of a triangle $\triangle{ABC}$ . Let $w_{1}$ be an area of $\triangle{ABC}$ outside the circle $p$ and adjacent to the vertex $A$ , and $w_{2}=\triangle{ABC}\setminus(p\cup w_{1})$ as in Figure 7. Then any circle $y\subseteq\triangle{ABC}$ cannot have non-empty intersections with both areas $w_{1},w_{2}$ .

Note that the version of this statement is still true and also addressed in [2], when circle $p$ touches two parallel lines $(AB)$ and $(A^{\prime}C)$ , and $w_{1}$ , $w_{2}$ denote two disjoint parts of a strip between these lines.

The next result was a crucial observation about tight implication for circles from [14]. The underlying closure operator here is $\operatorname{ch}_{c}$ .

Definition 10.

Let $(X,\varphi)$ be a closure system. An implication $Y\to u$ , $Y\subseteq X,u\in X$ , is called tight, if implications $(Y\setminus\{z\})\to u$ do not hold, for all $z\in Y$ . We will call implication $Y\to u$ loose, if $u\in\varphi(Y)$ and it may not be tight.

Lemma 3 (The Triangle Property).

If $a,b,c,$ and $e$ are circles in the plane with centers $A,B,C,$ and $E$ respectively, and $abc\to e$ is a tight implication, then $E$ must lie in the interior of triangle formed by $A$ , $B$ and $C$ .

Lemma 4.

Given points $A,B,C,E$ in the plane, for $E$ to lie in the interior of the triangle formed by $A$ , $B$ and $C$ , $C$ must be located in the opposite angle to $\angle AEB$ .

Figure 8: Possible locations for

C

shaded

We add one new observation we will need later in our paper.

Lemma 5.

Let circles $a,b,c$ be in configuration (3) of Lemma 1. If $a,c$ overlap, then $\operatorname{CH}(a,b,c)=\operatorname{CH}(b,c)\cup\operatorname{CH}(a,b)\cup\operatorname{CH}(a,c)$ .

Proof.

Let $A,B,C$ be centers of circles $a,b,c$ , respectively. Every point in $\operatorname{CH}(a,b,c)$ , which is not in $\triangle ABC$ , will belong to one of $\operatorname{CH}(b,c)$ , $\operatorname{CH}(a,b)$ , $\operatorname{CH}(a,c)$ . Therefore, we only need to consider a point $D\in\triangle ABC$ . Since $a,c$ overlap, segment $[AC]$ is covered by a union of two radii segments on the line $(AC)$ : radius $[AA_{1}]$ of circle $a$ and radius $[CC_{1}]$ of circle $c$ . Let $(BD)$ intersect $[AC]$ at point $P$ . Then either $P\in[AA_{1}]\subseteq\tilde{a}$ , or $P\in[CC_{1}]\subseteq\tilde{c}$ . Since $D\in[BP]$ , we have $D\in\operatorname{CH}(b,a)$ or $D\in\operatorname{CH}(b,c)$ . ∎

3 Opposite Property

In this section we show that circle configurations on the plane satisfy the property that we call the Opposite Property. It shows that 7 geometries that were included in the list of impossible geometries in paper [14] cannot be represented by circles on the plane.

Theorem 1.

If $bcd\to e$ is a tight implication and $ab\to e$ , $ac\to e$ , and $ad\to e$ , then $a\to e$ .

Proof.

Suppose the hypotheses hold, and let $A,B,C,D,E$ be the centers of circles $a,b,c,d,e$ respectively. If $A=E$ then either $a\to e$ , in which case the theorem holds, or $e\to a$ , in which case $ab\to e$ is only possible if $b\to e$ , but then $bcd\to e$ is not tight. If $A\neq E$ , we have the following picture, where the distance between $E$ and $E^{\prime}$ is the radius of $e$ (i.e. $E^{\prime}$ is the point in $e$ farthest away from $A$ ; note that $E$ and $E^{\prime}$ , and thus $\ell$ and $\ell^{\prime}$ , are not necessarily distinct):

$\ell^{\prime}$ splits the plane into two semi-planes, and if any point in $a$ is in the semi-plane opposite $A$ , then clearly $a\to e$ and the theorem holds.

If $a$ is contained in the open semi-plane containing $A$ , then in order for $ab\to e$ , $ac\to e$ , and $ad\to e$ , $b,c$ and $d$ must all have at least one point in the semi-plane opposite $A$ (otherwise both circles will be contained in the same open semi-plane not containing $E^{\prime}$ , and thus their convex hull cannot contain $E^{\prime}$ ).

$\ell$ also splits the plane into two semi-planes and since, by the triangle property (lemma 5), $E$ is in the interior of the triangle formed by $B,C$ and $D$ , at least one of $B,C,D$ must be contained in the same open semi-plane as $A$ . Without loss of generality, suppose this is true of $B$ . $B$ cannot be on the ray from $E$ through $A$ (else $b\to e$ , in which case $bcd\to e$ is not tight), so $B$ must be contained an open quadrant formed by $(AE)$ and $\ell$ .

Call this quadrant “quadrant I” (shaded below) and label the other quadrants II, III, and IV, according to the figure below and which semi-planes formed by $(AE)$ and $\ell$ they share with $B$ .

Since $b$ is a circle that must have at least one point in the semi-plane opposite $A$ with respect to $\ell^{\prime}$ , as noted above, $b$ must contain the point closest to $B$ in this semi-plane, namely the intersection of $\ell^{\prime}$ and a line through $B$ parallel to $(AE)$ , which we will call $B^{\prime}$ . Thus $b$ must at least contain the circle of minimal radius centered at $B$ that includes $B^{\prime}$ .

Call this circle, pictured below with a dashed line, $b^{\prime}$ .

Now $(BE)$ splits the plane into two semi-planes, and since $E$ is in the interior of the triangle formed by $B,C$ and $D$ , one of $C,D$ must be in the open semi-plane that does not contain $B^{\prime}$ , so without loss of generality suppose it is $C$ . Note that, regardless of the placement of $B$ , this semi-plane is contained within quadrants I, II, and III. As with $b$ , the convex hull of $c$ also must contain the point closest to $C$ in the semi-plane opposite $A$ with respect to $\ell^{\prime}$ , namely the point where $\ell^{\prime}$ and a line through $C$ parallel to $(AE)$ intersect, or $C$ itself if $C$ is already in this semi-plane. The convex hull of $c$ must at least contain the circle of minimal radius centered at $C$ that includes $C^{\prime}$ , which we will call $c^{\prime}$ , so the convex hull of $b^{\prime}$ and $c^{\prime}$ is contained in the convex hull of $b$ and $c$ .

If $C$ is not in quadrant I, it must be contained in the open semi-plane opposite $B$ with respect to $(AE)$ . First consider a placement of $C$ on the line $(BE)$ (although $C$ can in fact only be arbitrarily close to such a placement). In this case the convex hull of $b$ and $c$ is symmetric about $(BE)$ . If $C$ is in the same semi-plane as $B$ with respect to $\ell^{\prime}$ , i.e. $C\neq C^{\prime}$ , then $B^{\prime},E^{\prime},$ and $C^{\prime}$ are all on $\ell^{\prime}$ , so $b^{\prime},e,$ and $c^{\prime}$ all share a common tangent line. They must also share this common tangent reflected about $(BE)$ , the line through their centers, so $e$ is in the convex hull of $b^{\prime}$ and $c^{\prime}$ and thus also of $b$ and $c$ .

This argument still holds in the case where $C=C^{\prime}$ is on $\ell^{\prime}$ , and from here moving $C$ further away from $B$ along $(BE)$ only adds the the convex hull of $b^{\prime}$ and $C$ , which already includes $e$ . Thus all placements of $C$ on the line $(BE)$ lead to the implication $bc\to e$ .

Similarly, moving $C$ horizontally off the line $(BE)$ into the opposite semi-plane as $B^{\prime}$ with respect to $(BE)$ , where it is assumed to be, only adds to the convex hull of $b^{\prime}$ and $c^{\prime}$ .

Therefore any possible placement of $C$ not in quadrant I leads to the strict implication $bc\to e$ , so $C$ must be in quadrant I, as $B$ is.

Now $(CE)$ splits the plane into two semi-planes, and since $E$ is in the interior of the triangle formed by $B,C$ and $D$ , $D$ must be in the open semi-plane that does not contain $B$ . But now we have already seen that such a placement of $D$ not in quadrant I leads to the implication $cd\to e$ (by $C$ playing the role of $B$ and $D$ playing the role of $C$ in the previous argument, so $D$ must also be in quadrant I. (Note that while $B$ was additionally shown to be in the open quadrant I, by the same argument used for $B$ , $C$ also cannot be on the line $(AE)$ between $A$ and $E$ , and this is all that is needed.) However, this makes it impossible for $E$ to be in the interior of the triangle formed by $B,C,$ and $D$ , so there is no possible representation for the given implications without the additional implication $a\to e$ . ∎

In the next statement we use the numbering of geometries given in [14] with their implications, but elements of geometry 74 have been relabeled to better fit the statement of Theorem 1.

Corollary 2.

The following geometries, identified here by their tight implications, are not representable by circles on the plane:

Geometry 46: $ab\to e$ , $ac\to e$ , $ad\to e$ , and $bcd\to e$ .

Geometry 60: $ab\to e$ , $ac\to e$ , $ad\to e$ , $abc\to d$ , and $bcd\to e$ .

Geometry 74: $ab\to e$ , $ac\to e$ , $ad\to e$ , and $bcd\to ae$ .

Geometry 84: $ab\to de$ , $ac\to e$ , $ad\to e$ , and $bcd\to e$ .

Geometry 114: $ab\to de$ , $ac\to de$ , $ad\to e$ , and $bcd\to e$ .

Geometry 115: $ab\to cde$ , $ac\to e$ , $ad\to e$ , and $bcd\to e$ .

Geometry 153: $ab\to cde$ , $ac\to de$ , $ad\to e$ , and $bcd\to e$ .

Proof.

In all of the above geometries, no proper subset of $bcd$ implies $e$ , so this is a tight implication. Additionally, the implications $ab\to e$ , $ac\to e$ , and $ad\to e$ are all always present, so by theorem 4.1 any representation by circles on the plane would have the additional tight implication $a\to e$ not present in these geometries. ∎

4 Area Q and non-representable geometries

4.1 Area Q for binary hulls

In this section we consider simple facts about the convex hulls of two circles, which we call binary hulls. We investigate the possible configurations formed by two or three binary hulls involving one fixed circle $d$ . The center of $d$ is denoted $D$ , and similarly, we use $A,B,C$ for centers of circles $a,b,c$ , respectively.

Throughout this section we will use the following labels and notation: for $u,x\in\{a,b,c,d\}$ , with respect to a specified circle $u$ with center $U$ , when a different circle $x$ , with center $X$ , is given, we will denote by $[UX)$ the ray from $U$ that goes through $X$ . We denote $X_{0}=[UX)\cap Circ(u)$ , and denote another point of intersection of the line $(UX)$ with $Circ(u)$ by $X_{\infty}$ . Note that $X_{0}=X_{\infty}=U$ when $u$ is a point.

For any center $X$ on segment $[UX_{0}]$ , if the radius of $x$ is $\leq|XX_{0}|$ , then $\tilde{x}\subseteq\tilde{u}$ . When the radius of $x$ grows beyond $|XX_{0}|$ , there will be exactly two common tangent lines to $u,x$ with touching points on $Circ(u)$ . We will denote these two touching points $X_{1},X_{2}$ , and observe that they are symmetric around line $(UX)$ .

As the radius of $x$ grows, $X_{1},~{}X_{2}$ travel along corresponding halves of $Circ(u)$ from $X_{0}$ to $X_{\infty}$ . When the radius reaches or surpasses $|XX_{\infty}|$ , we obtain a configuration where $\tilde{u}\subseteq\tilde{x}$ .

Similarly, for $X$ located on $[UX_{0})\setminus[UX_{0}]$ , we may start from $x=\{X\}$ and find touching points $X_{1},X_{2}$ on $Circ(u)$ for tangents from $X$ to $u$ , and as the radius of $x$ is allowed to grow, the touching points travel toward point $X_{\infty}$ until $\tilde{u}\subseteq\tilde{x}$ .

For illustration with $u=d$ and $x=c$ , see Fig. 9.

Thus, whenever $\tilde{u}\not\subseteq\tilde{x}$ and $\tilde{x}\not\subseteq\tilde{u}$ , there will be two lines tangent to both $u$ and $x$ with touching points $X_{1},X_{2}$ on $Circ(u)$ , symmetric around $(UX)$ .

Now our goal is to establish some facts about the set of points

Q_{d}(Y)=[\bigcap_{y\in Y}\operatorname{CH}(d,y)]\setminus\tilde{d},

defined by some circle $d$ and set $Y$ of one, two or three additional circles.

We start from $Y=\{c\}$ , just a single circle, i.e. $Q_{d}(c)=\operatorname{CH}(d,c)\setminus\tilde{d}$ .

We will assume that $c,d$ are not included within each other and thus we will have points $C_{0},C_{1},C_{2},C_{\infty}$ on $Circ(d)$ , which are 4 distinct points, unless $d=\{D\}$ . To distinguish the two arcs connecting $C_{1},C_{2}$ on $d$ , we will include another point on the arc in the notation, in this case $\overset{\frown}{C_{1}C_{0}C_{2}}$ or $\overset{\frown}{C_{1}C_{\infty}C_{2}}$ .

The following lemma links the properties of certain arcs with information about points in $Q_{d}(Y)$ .

When we say that the set of points $S$ has points arbitrarily close to points of some set $Z$ , we mean that any open ball (standard open set of metric space $\mathbb{R}^{2}$ ) centered at $z\in Z$ has non-empty intersection with $S$ .

Lemma 6.

Suppose $\tilde{c}\not\subseteq\tilde{d}$ , $\tilde{d}\not\subseteq\tilde{c}$ and $d\not=\{D\}$ . Then

(1)

The arc $\overset{\frown}{C_{1}C_{\infty}C_{2}}$ is a part of the border of $\operatorname{CH}(c,d)$ .
(2)

$Q_{d}(c)$ has points arbitrarily close to all points of the arc $\overset{\frown}{C_{1}C_{0}C_{2}}$ .

Proof.

(1) $\operatorname{CH}(c,d)$ is a convex closed set (in regular topology of $\mathbb{R}^{2}$ ), whose border consists of two tangent segments with end points $C_{1},C_{2}$ on $Circ(d)$ , the arc $\overset{\frown}{C_{1}C_{\infty}C_{2}}$ of $Circ(d)$ and arc of circle $c$ , see Figure 9.

(2) The arc $\overset{\frown}{C_{1}C_{0}C_{2}}$ is inside closed set $\operatorname{CH}(c,d)$ . When $d$ is removed from $\operatorname{CH}(c,d)$ , the remaining set $Q_{d}(c)$ has points arbitrary close to the points of this arc.

∎

Now we move to consider configurations of three circles. For area Q in these cases, $Y$ consists of two circles, for example, $Y=\{b,c\}$ , and $Q_{d}=(\operatorname{CH}(b,d)\cap\operatorname{CH}(c,d))\setminus\tilde{d}$ .

We will assume that none of the three circles involved is included into another, and in the next several statements we will refer to configurations 1, 2 or 3 from Lemma 1.

Lemma 7.

Let circles $x,y,z$ be in configuration 1 with center $z$ . Then points $X_{i}$ follow $Y_{i}$ on circle $z$ such that ${\overset{\frown}{X_{1}X_{\infty}X_{2}}}\subseteq{\overset{\frown}{Y_{1}Y_{0}Y_{2}}}$ and ${\overset{\frown}{Y_{1}Y_{\infty}Y_{2}}}\subseteq{\overset{\frown}{X_{1}X_{0}X_{2}}}$ .

Proof.

See the proof by picture on Fig. 10.

∎

Lemma 8.

Suppose that circles $x,y,z$ are in configuration 2 with center $z$ . Then:

a)

Points $X_{i}$ follow $Y_{i}$ such that

${\overset{\frown}{Y_{1}Y_{0}Y_{2}}}~{}\subset~{}{\overset{\frown}{X_{1}X_{\infty}X_{2}}}$ and ${\overset{\frown}{X_{1}X_{0}X_{2}}}~{}\subset~{}{\overset{\frown}{Y_{1}Y_{\infty}Y_{2}}}$ .
b)

On external circle $x$ , ${\overset{\frown}{Y_{1},Y_{0}Y_{2}}}\subset{\overset{\frown}{Z_{1}Z_{0}Z_{2}}}$ .
c)

The border arcs of $\operatorname{CH}(x,y,z)$ on $z$ are formed by the intersection of arcs $\overset{\frown}{X_{1}X_{\infty}X_{2}}$ and $\overset{\frown}{Y_{1}Y_{\infty}Y_{2}}$ .
d)

$Q_{z}(x,y)=\emptyset$ .

Furthermore:

d)

If the circles are not in limit case 2, then $X_{i}\neq Y_{i}$ and there are two border arcs of $\operatorname{CH}(x,y,z)$ on $z$ .
e)

If the circles are in limit case 2, then $X_{1}=Y_{1}$ or $X_{2}=Y_{2}$ , and there is one nontrivial (i.e. consisting of more than one point) border arc of $\operatorname{CH}(x,y,z)$ on $z$ .

Lemma 9.

Suppose that circles $x,y,z$ are in configuration 3. Then:

a)

Points $X_{i}$ and $Y_{i}$ alternate on $z$ .
b)

The arc ${\overset{\frown}{X_{1}X_{0}X_{2}}}\cap{\overset{\frown}{Y_{1}Y_{0}Y_{2}}}$ is arbitrarily close to $Q_{z}(x,y)$ and ${\overset{\frown}{X_{1}X_{\infty}X_{2}}}\cap{\overset{\frown}{Y_{1}Y_{\infty}Y_{2}}}$ is part of the border of $\operatorname{CH}(x,y,z)$ . Neither of these arcs are empty or trivial.

Lemma 10.

Suppose circles $a,d,c$ are in limit case 2 configuration with $d$ in the center, and let the points on $d$ be in counter-clockwise order

A_{1},A_{0},A_{2}=C_{2},C_{0},C_{1}

If the radius of $d$ is decreased, but still $d\not\in ch_{c}(a,c)$ , then $A_{2}\not=C_{2}$ and the points are in the order

A_{1},C_{2},A_{2},C_{1}

Proof.

Indeed, when the radius is reduced, the circles become in configuration 3, therefore, the points $A_{i},C_{i}$ should alternate. ∎

Note that, by lemma 1, any three circles on the plane with none included into another must be in one of the three configurations addressed by Lemmas 7 - 9. Therefore, for such circles, one of those Lemmas must apply, and observations of the conclusions of Lemmas 7 - 9 can be used to determine the possible configuration(s) of such circles.

4.2 Configurations of circles in a tight implication

The goal of this section is to show that some circle configurations are restricted under tight implication.

We first make observations about configuration of circles $a,b,c$ and $a,c,d$ given the tight implication $abc\to d$ .

Lemma 11.

If $abc\to d$ is tight, then $a,b,c$ are in configuration 3.

Proof.

Indeed, if $a,b,c$ is in configuration 1, then, say $c\in ch_{c}(a,b)$ , therefore, $ab\to d$ holds, which contradicts the tightness of implication $abc\to d$ . If $a,b,c$ are in configuration 2, say, with $b$ at the center, then $d\in ch_{c}(a,b,c)$ implies either $d\in ch_{c}(a,b)$ or $d\in ch_{c}(b,c)$ , again a contradiction with the tightness. ∎

Lemma 12.

If $abc\to d$ is tight, then $a,c,d$ cannot be in configuration 1.

Proof.

If $\operatorname{CH}(a,c,d)=\operatorname{CH}(a,c)$ , then $d\in ch_{c}(a,c)$ and therefore $ac\to d$ , so $abc\to d$ is not tight. If $\operatorname{CH}(a,c,d)=\operatorname{CH}(a,d)$ , then $ad\to c$ , and combination with $abc\to d$ requires the additional implication $ab\to cd$ , as in every convex geometry, due to the anti-exchange axiom. This once again violates tightness of $abc\to d$ , so $\operatorname{CH}(a,c,d)\neq\operatorname{CH}(a,d)$ , and by the same argument $\operatorname{CH}(a,c,d)\neq\operatorname{CH}(c,d)$ . ∎

Our next goal is to show that whenever $abc\to d$ is tight, circles $a,c,d$ will not form configuration 2, except in limit case with $d$ in the center.

For this we show some extended version of Lemma 2.

Consider the setting: circle $c$ inscribed into angle with vertex $J$ and touching sides of angle at points $A_{1},A_{2}$ . We may adopt notation of Lemma 2 and denote two disjoint regions of the angle outside $c$ as $w_{1}$ and $w_{2}$ , and notation outlined in section 4.1 for points $B_{0},B_{1},B_{2}$ , relating to circle $b$ , on circle $c$ . Suppose points $B_{0},B_{1},B_{2}$ are on arc ${\overset{\frown}{A_{1}A_{2}}}$ bordering $w_{i}$ .

Similar version of the statement should work for the case when two tangents of $c$ at $A_{1},A_{2}$ are parallel lines.

Figure 13: circle

b

and

w_{2}

Lemma 13.

If $B_{0},B_{1},B_{2}$ related to circle $b$ form a sub-arc ${\overset{\frown}{B_{1}B_{0}B_{2}}}$ on arc ${\overset{\frown}{A_{1}A_{2}}}$ of circle $c$ bordering area $w_{i}$ , then $\tilde{b}\subseteq w_{i}\cup\tilde{c}$ .

In Figure 13 circle $b$ satisfying requirement on points $B_{0},B_{1},B_{2}$ can be located inside $\operatorname{CH}(M,c)$ , where $M$ is the intersection of tangent lines at $B_{1}$ and $B_{2}$ .

Proof.

We start from the case of infinite region $w_{2}$ . Given point $B_{1}$ on the arc ${\overset{\frown}{A_{1}A_{2}}}$ bordering $w_{2}$ , we think of ray $[B_{1})$ as obtained from rotating ray $[A_{1})$ that is on line $(A_{1}J)$ and does not have $J$ : point $A_{1}$ moves along the arc ${\overset{\frown}{A_{1}B_{1}A_{2}}}$ until it arrives at $B_{1}$ , while the ray is tangent to circle $c$ at every location.

Ray $[B_{1})$ may be completely inside angle $\angle A_{1}JA_{2}$ , or it may cross side $[JA_{2})$ . Assume that it does cross it, say, at point $F$ .

Now we will be rotating ray $[A_{2}F)$ so that $A_{2}$ goes along the arc ${\overset{\frown}{A_{2}B_{2}A_{1}}}$ until $A_{2}$ reaches $B_{2}$ , and at every location the ray remains to be tangent to $c$ . If we watch the point of intersection with line $(B_{1}F)$ , then it moves from $F$ toward $B_{1}$ , so it remains inside area $w_{2}$ . In particular, the final location is point $M$ , the point of intersection of two rays $[B_{1})$ and $[B_{2})$ .

We must have $[CM)\cap Circ(c)=B_{0}$ and $\operatorname{CH}(M,c)\subseteq w_{2}\cup\tilde{c}$ . Since any circle $b$ with touching points $B_{1},B_{2}$ and center on $[CM)$ must be in $\operatorname{CH}(M,c)$ , we obtain $\tilde{b}\subseteq w_{2}\cup\tilde{c}$ .

In case none of rays $[B_{1}),[B_{2})$ intersect with the sides of angle $\angle A_{1}JA_{2}$ , we conclude that $[B_{1}),[B_{2})\subseteq w_{2}$ , thus, $\tilde{b}\subseteq\operatorname{CH}([B_{1}),[B_{2}),c)\subseteq w_{2}$ .

Similar argument works for region $w_{1}$ , except rays $[B_{1})$ and $[B_{2})$ , obtained by rotation of $[A_{1}J)$ and $[A_{2}J)$ , respectively, always intersect with sides of angle $\angle A_{1}JA_{2}$ . ∎

Lemma 14.

If circle $c$ is at the center of configuration 2 for $a,c,d$ and $b,c,d$ , then $d\not\in ch_{c}(a,b,c)$ .

Figure 14:

c

is at the center in

b,c,d

Proof.

Note that $c$ cannot have radius 0 in the described configurations.

Let $D_{1},D_{2},D_{0},D_{\infty}$ on $c$ be as specified in section 4.1.

Then $A_{1}A_{2},B_{1},B_{2}$ , the touching points on $Circ(c)$ from circles $a,b$ , do not alternate with $D_{1},D_{2}$ ; thus, all are located on arc ${\overset{\frown}{D_{1}D_{\infty}D_{2}}}$ . By assumption on configurations, points $A_{0}$ and $B_{0}$ are also on the same arc.

Let us assume wlog that the region between tangents bordered by this arc is $w_{2}$ . Then by Lemma 13 we have $\tilde{a},\tilde{b}\subseteq w_{2}\cup\tilde{c}$ . On the other hand, $\tilde{d}\subseteq w_{1}\cup\tilde{c}$ , where we call $w_{1}$ the region formed by extending tangent segments between $c,d$ beyond touching points on $d$ , and bordered by arc ${\overset{\frown}{D_{1}D_{0}D_{2}}}$ . Since $w_{1},w_{2}$ are disjoint regions, $d$ cannot be in $ch_{c}(a,b,c)$ (unless $d$ is inside $c$ , which we exclude). ∎

Lemma 15.

Let circles $a,b,c$ form configuration 3 and $abc\to d$ . If $a,c,d$ form configuration 2 with center $c$ , then $bc\to d$ .

Proof.

Let $A_{0},A_{\infty},D_{0},D_{\infty}$ on $c$ be as specified in section 4.1.

Since $c$ is in the center of $a,c,d$ in configuration 2, touching points $A_{i},D_{i}$ on $c$ do not alternate (and $c$ has a positive radius). Then $D_{1},D_{2}$ are located on arc ${\overset{\frown}{A_{1}A_{\infty}A_{2}}}$ .

Since $a,b,c$ are in configuration 3, touching points $A_{i},B_{i}$ alternate on $c$ . Without loss of generality assume that ${\overset{\frown}{A_{1}B_{1}}}$ is an arc where $Q_{c}(a,b)$ is attached, then ${\overset{\frown}{A_{2}B_{2}}}$ is the arc on $c$ which is part of the border of $\operatorname{CH}(a,b,c)$ . Due to the latter fact, arc ${\overset{\frown}{A_{2}B_{2}}}$ cannot be on ${\overset{\frown}{A_{1}A_{0}A_{2}}}$ , which is inside $\operatorname{CH}(a,c)$ , therefore, arc ${\overset{\frown}{A_{2}B_{2}}}$ is on ${\overset{\frown}{A_{1}A_{\infty}A_{2}}}$ . Apparently, $D_{1},D_{2}$ cannot be on arc ${\overset{\frown}{A_{2}B_{2}}}$ , therefore, they are on arc ${\overset{\frown}{A_{1}A_{\infty}A_{2}}}$ from which we remove arc ${\overset{\frown}{A_{2}B_{2}}}$ . This is arc ${\overset{\frown}{B_{2}A_{1}}}$ , which is also a part of arc ${\overset{\frown}{B_{2}A_{1}B_{1}}}$ . We conclude that $D_{1},D_{2}$ are also on the arc ${\overset{\frown}{B_{2}A_{1}B_{1}}}$ , therefore, $B_{i},D_{i}$ do not alternate.

This means that $b,c,d$ are in configuration 1 or 2. If $d$ is in the center of configuration 1, then $bc\to d$ and we are done. If, say, $b$ is in the center of configuration 1, then $cd\to b$ , thus, together with $abc\to d$ we conclude $ac\to bd$ due to the anti-exchange property, and $ac\to d$ contradicts the assumption that $c$ is in the center of $a,c,d$ in configuration 2.

It remains to show that $b,c,d$ in configuration 2 will bring $bc\to d$ or a contradiction with $abc\to d$ or configuration 3 for $a,b,c$ .

If $c$ is at the center of configuration 2 for $b,c,d$ , then we have the setting of Lemma 14, and we get to the contradiction with $abc\to d$ . See Figure 14.

Figure 15:

d

is at the center in

c,d,b

Suppose $c,d,b$ are in configuration 2 and $d$ is in the center. Then on circle $c$ points $B_{1}B_{2}$ are located on the arc ${\overset{\frown}{D_{1}D_{0}D_{2}}}$ , while points $A_{1},A_{2}$ are located on arc ${\overset{\frown}{D_{1}D_{\infty}D_{2}}}$ .

Indeed, the latter is due to $a,c,d$ also in configuration 2 with $c$ in the center. Thus, $A_{i},B_{i}$ do not alternate on $c$ , a contradiction with assumption that $a,b,c$ in configuration 3. See Figure 15.

Figure 16:

b

is at the center in

c,b,d

Finally, consider $b$ at the center of $c,b,d$ , like in Figure 16. For now, assume $d$ has a positive radius. Then on circle $d$ points $B_{i}C_{i}$ do not alternate , and $C_{1},C_{2},C_{0}$ are on the arc ${\overset{\frown}{B_{1}B_{0}B_{2}}}$ . But also, since $a,c,d$ are in configuration 2 with $c$ at the center, $A_{1},A_{2},A_{0}$ on $d$ are on the arc ${\overset{\frown}{C_{1}C_{0}C_{2}}}$ . Apply Lemma 13 replacing $c$ by $d$ , points $A_{1},A_{2}$ by $B_{1},B_{2}$ , lines $(A_{1}J),(A_{2}J)$ by tangents of $b,d$ and $B_{1},B_{2},B_{0}$ by either $A_{1},A_{2},A_{0}$ or by $C_{1},C_{2},C_{0}$ . Then, circles $a,b,c$ are inside $w_{i}\cup\tilde{d}$ , where $w_{i}$ is a region formed by tangents of $d$ at $B_{1},B_{2}$ and bordered by arc ${\overset{\frown}{B_{1}B_{0}B_{2}}}$ . This implies that $d\not\in ch_{c}(a,b,c)$ (unless $b=d$ , which we exclude).

The case when $d$ is a point follows from the above: if $d$ is not on a tangent of binary hulls within $\operatorname{CH}(a,b,c)$ , we can pick some small radius for a circle $d^{\prime}$ with center $d$ such that the assumptions hold ( $abc->d^{\prime}$ , $a,c,d^{\prime}$ are in configuration 2 with center $c$ , and $c,b,d^{\prime}$ are in configuration 2 with $b$ in the center) and lead to a contradiction as before. If $d$ is on a tangent of $\operatorname{CH}(b,c)$ then the conclusion holds, and if $d$ is on a tangent of $\operatorname{CH}(a,b)$ or $\operatorname{CH}(a,c)$ , we can replace both $d$ and $a$ with slightly larger circles such that the given assumptions hold and are again in the case above. ∎

We finally collect all the previous observations in the following result.

Theorem 3.

If $abc\to d$ is tight, then $a,c,d$ is in configuration 3 or in limit case 2 with $d$ at the center.

Proof.

By Lemma 12, circles $a,c,d$ cannot be in configuration 1. By Lemma 11 $a,b,c$ form configuration 3, therefore, the assumptions of Lemma 15 hold. By Lemma 15 if any $a$ or $c$ is in the center of configuration 2 for $a,c,d$ , then the implication $abc\to d$ is not tight.

Thus, if $a,c,d$ form configuration 2, then only $d$ can be in the center. Moreover one of common tangents of $a,c$ has the border of $\operatorname{CH}(a,b,c)$ , therefore, $d$ cannot intersect it in more than one point. Thus, if $d$ is in center of configuration 2 for $a,c,d$ , then it is in limit case 2. ∎

4.3 Point Order Theorem

We will be establishing consistent labeling of touching points on circle $d$ , when four circles satisfy tight implication $abc\to d$ , for the underlying closure operator $ch_{c}$ .

We first fix a consistent orientation of circles $a,b,c$ around $d$ . We will set points on $Circ(d)$ using the approach described in section 4.1. Let ray $[DA)$ start at center $D$ and go through center $A$ . The point of crossing $Circ(d)$ and $[DA)$ is called $A_{0}$ .

The second point of intersection of $Circ(d)$ and $(AD)$ is denoted $A_{\infty}$ . The same labeling conventions give $B_{0}$ , $B_{\infty}$ from ray $[DB)$ and circle $b$ . Furthermore, points $C_{0}$ and $C_{\infty}$ come from $[DC)$ and $c$ .

Now we establish the orientation. Consider circle $d$ as a clock with the center of rotation for the clock hand at $D$ . Start the clock hand at $B_{0}$ and move counterclockwise. Without loss of generality, the circular order on $Circ(d)$ will be as follows: $B_{0},A_{0},C_{0}$ .

Now we establish the orientation of tangent points with respect to the various ray intersections on $d$ . There are two tangent points on $d$ from $\operatorname{CH}(b,d)$ that we label $B_{1}$ and $B_{2}$ . When starting at $B_{1}$ and walking counterclockwise, the circular order will be $B_{1},B_{0},B_{2}$ . The tangent points from $\operatorname{CH}(a,d)$ are $A_{1}$ and $A_{2}$ with $A_{0}$ inside $\operatorname{CH}(a,d)$ . Starting at $A_{1}$ , we have the circular order as $A_{1},A_{0},A_{2}$ . For $\operatorname{CH}(c,d)$ , we have points $C_{1},C_{2}$ . When walking counterclockwise, we get the point order $C_{2},C_{0},C_{1}$ .

Finally, we label the outer tangents of $\operatorname{CH}(a,b,c)$ as $(A_{b}B_{a})$ , $(A_{c}C_{a})$ and $(B_{c}C_{b})$ .

For any two non-collinear rays $[DA)$ and $[DC)$ we call proper angle a smaller of two angles formed by these two rays.

Theorem 4 (Point Order Theorem).

With the counterclockwise orientation of $B_{0},A_{0},C_{0}$ and the associated labeling when $abc\to d$ is tight, the counterclockwise point order on $d$ beginning at $B_{1}$ is $B_{1},C_{1},A_{1},B_{2},C_{2},A_{2}$ .

Proof.

By Theorem 3, triples of circles: $\{a,c,d\}$ , $\{b,c,d\}$ , and $\{a,b,d\}$ , are only in limit case 2 with $d$ at the center or the convex hulls are in configuration 3. Since $d$ is in $\operatorname{CH}(abc)$ , we may start with the case where $d$ is touching all three lines $(A_{b}B_{a})$ , $(A_{c}C_{a})$ and $(B_{c}C_{b})$ .

Then we proceed with cases where $d$ is tangent to two of these lines, one of these lines, and finally none of these lines.

Case 1: $d$ is inscribed in $\operatorname{CH}(a,b,c)$ .

This is the case where $d$ is tangent to $(A_{b}B_{a})$ , $(A_{c}C_{a})$ , and $(B_{c}C_{b})$ . For discussion convenience, label the tangent points on $d$ as $B_{d}$ , $A_{d}$ and $C_{d}$ , on lines $(B_{c}C_{b})$ , $(A_{c}C_{a})$ and $(B_{c}C_{b})$ , respectively.

Then, according to agreement on orientation of $a,b,c$ around $d$ , we have the following coincidence of points:

B_{1}=C_{1}=B_{d},\ \ A_{1}=B_{2}=A_{d},\ \ C_{2}=A_{2}=C_{d}

Therefore, the counter-clock sequence is, indeed,

B_{1},C_{1}=B_{1},A_{1},B_{2}=A_{1},C_{2},A_{2}=C_{2}.

Case 2: $d$ is tangent to $(A_{b}B_{a})$ and $(A_{c}C_{a})$ but not $(B_{c}C_{b})$ .

This new condition does not change the assumption that $A_{1}=B_{2}=A_{d}$ and $C_{2}=A_{2}=C_{d}$ .

Now $b,c,d$ are in configuration 3 by Theorem 3, which means $B_{i},C_{i}$ alternate around $d$ by Lemma 9. This allows the counter-clockwise point order $B_{1},C_{1},B_{2},C_{2},$ or, the order $B_{1},C_{2},B_{2},C_{1}$ . The latter order is not possible, because circles $a,c,d$ are in limit case 2 with center $d$ , therefore, by Lemma 8, ${\overset{\frown}{A_{1}A_{0}A_{2}}}~{}\subset~{}{\overset{\frown}{C_{1}C_{\infty}C_{2}}}=~{}{\overset{\frown}{C_{1}C_{\infty}A_{2}}}$ . But with the order $B_{1},C_{2},B_{2},C_{1}$ , the arc ${\overset{\frown}{C_{2}C_{0}C_{1}}}$ will contain point $B_{2}=A_{1}$ instead of the arc ${\overset{\frown}{C_{2}C_{\infty}C_{1}}}$ , a contradiction.

Therefore, the only possible order is $B_{1},C_{1},B_{2},C_{2},$ , and, thus, including $A_{1},A_{2}$ into the sequence, we get

B_{1},C_{1},A_{1}=B_{2},B_{2},C_{2},A_{2}=C_{2}.

Case 3: $d$ is tangent to $(A_{c}C_{a})$ but not $(B_{c}C_{b})$ and $(A_{b}B_{a})$ .

We still have $C_{2}=A_{2}=C_{d}$ , thus $d$ is at the center of limit case 2 for circles $a,c,d$ . Therefore, the circular sequence of points on $d$ starting from $C_{2}=A_{2}$ will be either

C_{2},C_{0},C_{1},A_{1},A_{0},A_{2}=C_{2}

A_{2},A_{0},A_{1},C_{1},C_{0},C_{2}=A_{2}

But only first sequence satisfies the agreement of counter-clockwise order $A_{1},A_{0},A_{2}$ .

Now, by assumption in this case, circles $a,b,d$ as well as $b,c,d$ are in configuration 3. Since points $B_{i}$ alternate with both $A_{i}$ and $C_{i}$ , by Lemma 9, one of points $B_{i}$ is on arc ${\overset{\frown}{C_{2}C_{0}C_{1}}}$ and another on arc ${\overset{\frown}{A_{2}A_{0}A_{1}}}$ . There are two possibilities to insert points $B_{i}$ into the first sequence above. Suppose we have the following placement of $B_{i}$ :

C_{2},B_{2},C_{1},A_{1},B_{1},A_{2}=C_{2}

This would mean that the arc ${\overset{\frown}{B_{1}B_{0}B_{2}}}$ is the same as ${\overset{\frown}{B_{1}A_{2}B_{2}}}$ , but arc ${\overset{\frown}{B_{1}B_{0}B_{2}}}$ is an inner arc of $\operatorname{CH}(b,d)$ , with only points $B_{1},B_{2}$ on its border, thus, it is an inner arc of $\operatorname{CH}(a,b,c)$ , and cannot have points on the border of $\operatorname{CH}(a,b,c)$ , in particular, cannot have point $A_{2}=C_{2}$ .

Therefore, the only possible sequence of points is

C_{2},B_{1},C_{1},A_{1},B_{2},A_{2}=C_{2}

which can be written starting from $B_{1}$ as follows:

B_{1},C_{1},A_{1},B_{2},C_{2},A_{2}=C_{2}

Case 4: $d$ is not tangent to $(A_{c}C_{a})$ , $(B_{c}C_{b})$ and $(A_{b}B_{a})$ .

Now every triple of circles: $\{a,b,d\}$ , $\{b,c,d\}$ and $\{a,c,d\}$ - is in configuration 3 by Theorem 3, therefore, $A_{i},B_{i}$ alternate on $d$ , as well as $B_{i},C_{i}$ and $A_{i},C_{i}$ .

Gradually increase the radius of $d$ so that $d$ remains in $\operatorname{CH}(a,b,c)$ . At the limit of this process $d$ will touch at least one of outer borders of $\operatorname{CH}(a,b,c)$ . Call new circle $d_{1}$ . Then $abc\to d_{1}$ is again tight. Moreover, one of Cases 1-3 will describe the configuration of $a,b,c,d_{1}$ .

Assume wlog that $d_{1}$ is touching $(A_{c}C_{a})$ and not touching other lines $(A_{b}B_{a})$ , $(B_{c}C_{b})$ . Then we can apply the result of Case 3 to $d_{1}$ . Therefore, the sequence of points on $d_{1}$ is

B_{1},C_{1},A_{1},B_{2},C_{2}=A_{2}

Also, focusing on subsequence of $A_{i},C_{i}$ , we have, starting from $A_{1}$ :

A_{1},A_{0},A_{2}=C_{2},C_{0},C_{1}

If we slightly reduce the radius of $d_{1}$ , circles $a,c,d_{1}$ will no longer be in limit case 2, but since $abc\to d_{1}$ is tight, $a,c,d_{1}$ are in configuration 3, due to Theorem 3. By Lemma 10, the sequence of $A_{i},C_{i}$ points on $d_{1}$ starting from $A_{1}$ is

A_{1},C_{2},A_{2},C_{1}

We need to embed this sequence into sequence of limit case 2

B_{1},C_{1},A_{1},B_{2},A_{2}=C_{2}

We notice that we have to place $C_{2}$ after $A_{1}$ , and if we place it before $B_{2}$ , then points $B_{i},C_{i}$ will not alternate, which contradicts $b,c,d_{1}$ being in configuration 3. Therefore, the proper sequence is

B_{1},C_{1},A_{1},B_{2},C_{2},A_{2}

If we continue reducing the radius of $d_{1}$ back to $d$ , we remain in configuration 3 for all triples of circles. Indeed, at every moment of the process we have $abc\to d_{1}$ tight, and at the start of the process $d_{1}$ was not at the center of limit case 2 with any two other circles. Therefore, the sequence of points on $d$ will not change.

Suppose we get $d_{1}$ in its limit position touching $(A_{b}B_{a})$ and $(A_{c}C_{a})$ . Then, according to the result for case 2, we get the following sequence on $d_{1}$ :

B_{1},C_{1},A_{1}=B_{2},B_{2},C_{2},A_{2}=C_{2}

When the radius of $d_{1}$ is slightly reduced, we get the following sequence of points $B_{i},A_{i}$ :

B_{1},A_{1},B_{2},A_{2}

Similarly, we expect the following sequence of points $A_{i},C_{i}$ :

C_{1},A_{1},C_{2},A_{2}

Incorporating them into original sequence in limit position of $d_{1}$ , we get only one possibility:

B_{1},C_{1},A_{1},B_{2},C_{2},A_{2}

Finally, consider the case when $d_{1}$ in its limit position is touching all three lines $(A_{c}C_{a})$ , $(B_{c}C_{b})$ and $(A_{b}B_{a})$ . Then we have configuration of $a,b,c,d_{1}$ in case 1, therefore, there are only three distinct touching points on $d_{1}$ :

B_{1},A_{1},C_{2}

If we give them other labeling, focusing on $A_{i},B_{i}$ , then we get the same sequence as

B_{1},B_{2}=A_{1},A_{2}

Then, when the radius of $d_{1}$ is slightly reduced, we expect, by Lemma 10, that the points will alternate:

B_{1},A_{1},B_{2},A_{2}

Similarly, if we write the original sequence of points on $d_{1}$ in their $A_{i},C_{i}$ labeling, we get

C_{1},A_{1},C_{2}=A_{2}

Therefore, after reducing the radius of $d_{1}$ we obtain

C_{1},A_{1},C_{2},A_{2}

Finally, if we write the original sequence in its $B_{i},C_{i}$ labeling, we will have

B_{1}=C_{1},B_{2},C_{2}

After the radius of $d_{1}$ is reduced it turns into

B_{1},C_{1},B_{2},C_{2}

There is only one circular sequence of all points $A_{i},B_{i},C_{i}$ that honors three established subsequences:

B_{1},C_{1},A_{1},B_{2},C_{2},A_{2}

This finishes the analysis of Case 4. ∎

5 Point Order Theorem in action

In this section we find several applications of Point Order Theorem, which will generate several families of non-representable convex geometries.

5.1 Separation property

Theorem 5.

Let $a,b,c,d,e$ be circles on the plane. If $acd\to e$ and $bcd\to e$ are both tight, then it is not possible to also have the implication $ab\to e$ .

Proof.

First, let us consider the case where $e=\{E\}$ . Since $acd\to e$ and $bcd\to e$ are both tight, by the triangle property (Lemma 3) the center of circle $e$ must lie in the interior of the triangles formed by centers $B,C,D$ and $A,C,D$ . Then, by lemma 4, both $B$ and $A$ must be in the opposite angle to $\angle DEC$ . Thus, if any point of $a$ crosses the line $(DE)$ , then $E\in\operatorname{CH}(a,D)\subseteq\operatorname{CH}(a,d)$ , violating the tightness of the implication $acd\to e$ . (See figure 18 below.)

Similarly, if any point of $a$ crosses the line $(CE)$ , then $E\in\operatorname{CH}(a,c)$ , so $a$ , and by the same argument $b$ , must be strictly contained in the opposite angle to $\angle DEC$ , and therefore their convex hull cannot contain $e$ and the hypothesis holds.

Figure 18: Possible locations for

A,B

shaded

Now let us consider the case when $e$ has a positive radius. Wlog, let us assume the counterclockwise orientation of $B_{0},D_{0},C_{0}$ and associated labeling around circle $e$ as in Theorem 4, with circles $d$ and $e$ playing the roles of circles $c$ and $d$ respectively. Specifically, note that we have labeled such that $B_{1},B_{0},B_{2}$ is the counterclockwise circular order of these points around $e$ . Since $bcd\to e$ is tight, this Lemma then tells us that the counterclockwise point order on $e$ beginning at $B_{1}$ is $B_{1},C_{1},D_{1},B_{2},C_{2},D_{2}$ .

Now, consider the placement of $A$ , the center of circle $a$ . Again, since $acd\to e$ and $bcd\to e$ are both tight, by the triangle property the center of circle $e$ must lie in the interior of the triangles formed by centers $B,C,D$ and $A,C,D$ , and by lemma 4, both $B$ and $A$ must be in the opposite angle to $\angle DEC$ .

In particular, the rays from $E$ to $A$ and $B$ that define $A_{0}$ and $B_{0}$ are both in the opposite angle to $\angle DEC$ , and so the counterclockwise orientation of $B_{0},D_{0},C_{0}$ around $e$ must be the same as the counterclockwise orientation of $A_{0},D_{0},C_{0}$ . Thus, again using the same labeling such that $A_{1},A_{0},A_{2}$ is the counterclockwise circular order of these points around $e$ , by Theorem 4 the counterclockwise point order on $e$ beginning at $A_{1}$ is $A_{1},C_{1},D_{1},A_{2},C_{2},D_{2}$ .

Now, for the sake of contradiction, suppose we also have the implication $ab\to e$ . Then circles $a,b,e$ are in configuration 1, with $e$ in the center, so by lemma 7 $A_{1},A_{2}$ follow $B_{1},B_{2}$ on a walk around $e$ . The only possible point orders are then $A_{1},B_{1},C_{1},D_{1},B_{2},A_{2},C_{2},D_{2}$ , or the symmetric order with $a$ and $b$ switched. In this case, $\overset{\frown}{B_{1}B_{0}B_{2}}\subseteq\overset{\frown}{A_{1}A_{0}A_{2}}$ , so the complementary arc $\overset{\frown}{B_{1}B_{\infty}B_{2}}\not\subseteq\overset{\frown}{A_{1}A_{0}A_{2}}$ (unless $\overset{\frown}{A_{1}A_{0}A_{2}}$ is all of circle $e$ , which we exclude since $a\to e$ contradicts $acd\to e$ being tight), which contradicts Lemma 7. Thus the implication $ab\to e$ must be absent.

∎

In the following corollary, the labels in geometry 26 have been changed to better fit the statement of theorem 5.

Corollary 6.

The following geometries, identified here by their tight implications, are not representable by circles on the plane:

Geometry 14: $acd\to e$ , $bcd\to e$ , and $ab\to e$ .

Geometry 23: $acd\to e$ , $bcd\to e$ , $abc\to de$ , and $ab\to e$ .

Geometry 26: $acd\to be$ , $bcd\to e$ , and $ab\to e$ .

Geometry 39: $acd\to e$ , $bcd\to e$ , and $ab\to de$ .

Geometry 54: $acd\to e$ , $bcd\to e$ , and $ab\to cde$ .

Proof.

In all these geometries the assumptions of Theorem 5 hold, but the conclusion is not compatible with the given implications. ∎

5.2 Nested triangles

Finally, we will make use of technical work of the previous section. The first statement is a key Lemma that deals with the tight implication $abc\to d$ . We could think of the combination of “nested triangles” formed by $d,a,b$ and $d,b,c$ (or $d,a,c$ ) within the larger “triangle” formed by $a,b,c$ .

Lemma 16.

If $abc\to d$ is tight, then $\operatorname{CH}(a,b,d)\cap\operatorname{CH}(b,c,d)=\operatorname{CH}(b,d)\cup Q_{d}(a,c)$ in case $r_{d}>0$ , and $\operatorname{CH}(a,b,d)\cap\operatorname{CH}(b,c,d)=\operatorname{CH}(b,d)$ when $r_{d}=0$ .

Proof.

Let us assume that we proved the case $r_{d}>0$ , and consider $r_{d}=0$ .

Since the right side of the equality for that case is always contained in the left side, we need to show that the left side is contained in the right side.

According to assumption, we have for $r_{d}>0$ :

\operatorname{CH}(a,b,\{D\})\cap\operatorname{CH}(b,c,\{D\})\subseteq\operatorname{CH}(a,b,d)\cap\operatorname{CH}(b,c,d)=\operatorname{CH}(b,d)\cup Q_{d}(a,c)

Now we can take the limit when $r_{d}$ approaches $0$ , and the right side will approach $\operatorname{CH}(b,\{D\})\cup Q_{\{D\}}(a,c)$ .

It remains to notice that $a,c$ cannot overlap, when $d=\{D\}$ and $abc\to d$ is tight. Indeed, by Lemma 5, if $a,c$ overlap, then $D$ is in one of double hulls $\operatorname{CH}(b,c),\operatorname{CH}(a,b),\operatorname{CH}(a,c)$ , thus, $abc\to d$ is not tight.

Since $a,c$ do not overlap, $Q_{\{D\}}(a,c)=\emptyset$ . Therefore, $\operatorname{CH}(a,b,d)\cap\operatorname{CH}(b,c,d)=\operatorname{CH}(b,d)$ .

Thus, it remains to prove the case when $d$ has a positive radius.

Note that it follows from the definition of $Q_{d}(ac)=\operatorname{CH}(a,d)\cap\operatorname{CH}(c,d)$ that $\operatorname{CH}(b,d)\cup Q_{d}(a,c)\subseteq\operatorname{CH}(a,b,d)\cap\operatorname{CH}(c,b,d)$ . Moreover, set $\operatorname{CH}(a,b,d)\cap\operatorname{CH}(b,c,d)$ is convex; therefore, it will contain an area around every point not in $\operatorname{CH}(b,d)$ with points arbitrarily close to some portion of the border of $\operatorname{CH}(b,d)$ . We will show that the only portion of the border of $\operatorname{CH}(b,d)$ for which $(\operatorname{CH}(a,b,d)\cap\operatorname{CH}(b,c,d))\setminus\operatorname{CH}(b,d)$ contains arbitrarily close points is the arc of attachment of $Q_{d}(a,c)$ .

We would think of orientation of $a,b,c,d$ so that we would take advantage of circular order of touching points on circle $d$ . Draw line $(BC)$ through centers of $b,c$ , and then name touching points on $b$ as $B_{1},B_{2}$ and point of intersection of $[DB)$ with $Circ(d)$ as $B_{0}$ so that moving from $B_{1}$ to $B_{0}$ to $B_{2}$ would be in counter clockwise order. By assumption, points $B_{0},A_{0},C_{0}$ appear in counter clockwise order. Besides, by Triangle Propoerty (Lemma 3), $D$ must be inside $\triangle ABC$ , therefore, $A,C$ are separated by $(BD)$ , and, thus, $C$ is in the same semiplane with respect to $(BD)$ as point $B_{1}$ , and $B_{2}$ and $A$ are in the opposite semiplane. See Figure 19 for illustration.

By Theorem 4, we have the following point order on $d$ :

B_{1},C_{1},A_{1},B_{2},C_{2},A_{2},B_{1}.

Note that $C_{0}$ is located on arc ${\overset{\frown}{C_{2}B_{1}C_{1}}}$ because of the labelling assumption which states the counter clockwise points on $d$ from $\operatorname{CH}(c,d)$ is $\overset{\frown}{C_{2}C_{0}C_{1}}$ . Thus, $B_{2}$ is contained on the complement arc $\overset{\frown}{C_{1}C_{\infty}C_{2}}$ . The intersection of ${\overset{\frown}{C_{1}C_{\infty}C_{2}}}$ and ${\overset{\frown}{B_{2}B_{\infty}B_{1}}}$ gives arc ${\overset{\frown}{B_{2}C_{2}}}$ .

Furthermore, $A_{0}$ is located on arc ${\overset{\frown}{A_{1}B_{2}A_{2}}}$ , because of the labelling assumption, so ${\overset{\frown}{A_{1}B_{2}A_{2}}}={\overset{\frown}{A_{1}A_{0}A_{2}}}$ . Thus, $B_{1}$ is on arc ${\overset{\frown}{A_{2}A_{\infty}A_{1}}}$ . By the labelling assumption and Theorem 4, arc ${\overset{\frown}{B_{2}C_{2}A_{2}B_{1}}}={\overset{\frown}{B_{2}B_{\infty}B_{1}}}$ , so the intersection of ${\overset{\frown}{B_{2}B_{\infty}B_{1}}}$ and ${\overset{\frown}{A_{2}A_{\infty}A_{1}}}$ gives arc ${\overset{\frown}{A_{2}B_{1}}}$ .

Finally, $A_{1}$ is on arc ${\overset{\frown}{C_{1}C_{\infty}C_{2}}}$ and $C_{1}$ is on ${\overset{\frown}{A_{2}A_{\infty}A_{1}}}$ , so ${\overset{\frown}{C_{1}A_{1}}}$ is a border arc of $\operatorname{CH}(a,c,d)$ on $d$ .

By Lemma 9, the following arcs on circle $d$ are border arcs of corresponding convex hulls:

•

${\overset{\frown}{B_{2}C_{2}}}$ is a border arc of $\operatorname{CH}(b,c,d)$ ;
•

${\overset{\frown}{A_{2}B_{1}}}$ is a border arc of $\operatorname{CH}(a,b,d)$ ;
•

${\overset{\frown}{C_{1}A_{1}}}$ is a border arc of $\operatorname{CH}(a,c,d)$ .

By Lemma 9, ${\overset{\frown}{C_{2}A_{2}}}$ is where $Q_{d}(ac)$ is attached because ${\overset{\frown}{C_{1}A_{1}}}$ is a border arc of $\operatorname{CH}(a,c,d)$ .

Consider now the touching points on $b$ . Denote by $D_{1},D_{2}$ the touching points of the common tangents with $d$ , so that $d,b$ are connected by common tangents $[B_{1}D_{1}]$ and $[B_{2},D_{2}]$ . Note that $D_{1}$ is in the same semiplane with respect to $(BD)$ as point $B_{1}$ , and $D_{2}$ is in the opposite semiplane.

Denote by $C_{b}$ the touching point of the outer tangent between $b,c$ , and $A_{b}$ the touching point of the outer tangent between $b,a$ . Then moving around $b$ from $D_{1}$ to $D_{2}$ , we will meet $C_{b}$ , then $A_{b}$ . Note that arc ${\overset{\frown}{C_{b}A_{b}}}$ on $b$ is part of the border of $\operatorname{CH}(a,b,c)$ , while arc ${\overset{\frown}{D_{1}C_{b}A_{b}}}$ is part of the border of $\operatorname{CH}(a,b,d)$ , and ${\overset{\frown}{C_{b}A_{b}D_{2}}}$ is a part of the border of $\operatorname{CH}(c,b,d)$ .

Here is the sequence of points on the border of $\operatorname{CH}(b,d)$ , when walking around this binary hull:

B_{1},D_{1},C_{b},A_{b},D_{2},B_{2},C_{2},A_{2},B_{1},

and we summarize what we established earlier:

•

segment $[B_{1}D_{1}]$ is on the border of $\operatorname{CH}(a,b,d)$ ;
•

arc ${\overset{\frown}{D_{1}C_{b}A_{b}}}$ of $b$ is on the border of $\operatorname{CH}(a,b,d)$ ;
•

arc ${\overset{\frown}{A_{b}D_{2}}}$ of $b$ is on the border of $\operatorname{CH}(b,c,d)$ ;
•

segment $[D_{2}B_{2}]$ is on the border of $\operatorname{CH}(b,c,d)$ ;
•

arc ${\overset{\frown}{B_{2}C_{2}}}$ on $d$ is a part of the border of $\operatorname{CH}(b,c,d)$ ;
•

arc ${\overset{\frown}{C_{2}A_{2}}}$ of $d$ is where $Q_{d}(a,c)$ is attached;
•

arc ${\overset{\frown}{A_{2}B_{1}}}$ of $d$ is a part of the border of $\operatorname{CH}(a,b,d)$ .

Therefore, there are no other points in $\operatorname{CH}(a,b,d)\cap\operatorname{CH}(b,c,d)$ than those in $\operatorname{CH}(b,d)\cup Q_{d}(a,c)$ . ∎

Note. Since $Q_{d}(a,c)=\operatorname{CH}(a,d)\cap\operatorname{CH}(c,d)\setminus\tilde{d}$ and $\tilde{d}\subseteq\operatorname{CH}(b,d)$ , we can rewrite the conclusion of Lemma 16 as follows:

\operatorname{CH}(a,b,d)\cap\operatorname{CH}(b,c,d)=\operatorname{CH}(b,d)\cup(\operatorname{CH}(a,d)\cap\operatorname{CH}(c,d))=

=(\operatorname{CH}(b,d)\cup\operatorname{CH}(a,d))\cap(\operatorname{CH}(b,d)\cup\operatorname{CH}(c,d))

The left side of equality involves “triple” convex hulls, while the right side is $\cup,\cap$ -combination of “double” convex hulls. Remarkably, the only assumption is the tight implication $abc\to d$ .

Theorem 7.

Assume that $abc\to d$ is a tight implication. Suppose that $\tilde{e}\subseteq\operatorname{CH}(a,b,d)\cap\operatorname{CH}(c,b,d)$ , but $\tilde{e}\not\subseteq\operatorname{CH}(b,d)$ . Then $\tilde{e}\subseteq\operatorname{CH}(a,d)\cap\operatorname{CH}(c,d)$ .

Proof.

By assumption, we have $\tilde{e}\subseteq\operatorname{CH}(a,b,d)\cap\operatorname{CH}(c,b,d)=\operatorname{CH}(b,d)\cup Q_{d}(a,c)$ . Since $\tilde{e}\not\subseteq\operatorname{CH}(b,d)$ , we cannot have $r_{d}=0$ and $Q_{d}(a,c)=\emptyset$ , thus, we must have point $E_{x}$ from $e$ in $Q_{d}(a,c)$ .

By Lemma 2, if circle $p$ is inscribed into angle, and $w_{1},w_{2}$ are two areas: $w_{1}$ outside circle $p$ and next to vertex of angle, and another outside of circle $p$ and far from the vertex - then any other circle inside that angle cannot have points in both $w_{1}$ and $w_{2}$ . The version of this Lemma is also true in the case the tangents forming $Q_{d}(a,c)$ are parallel.

Figure 20:

w_{1}=Q_{d}(ac)

We have an application of this Lemma here: vertex of the angle is a point of intersection of tangents forming $Q_{d}(a,c)$ , and circle $d$ plays the role of $p$ . Then $Q_{d}(a,c)$ is contained either in $w_{1}$ or $w_{2}$ from that Lemma. Say, the case on Figure 20 is $Q_{d}(a,c)=w_{1}$ .

Thus, if $e$ has a point in $Q_{d}(a,c)$ , and $e$ is contained in angle formed by extension of sides of $Q_{d}(a,c)$ from its vertex (which follows from $\tilde{e}\subseteq\operatorname{CH}(b,d)\cup Q_{d}(a,c)$ ), then $\tilde{e}\subseteq\tilde{d}\cup Q_{d}(a,c)$ . But then $\tilde{e}\subseteq\operatorname{CH}(a,d)$ , because $\tilde{d}\cup Q_{d}(a,c)\subseteq\operatorname{CH}(a,d)$ . Similarly, $\tilde{e}\subseteq\operatorname{CH}(c,d)$ . ∎

We will say that implication $X\to d$ on circles is loose, if $d\in ch_{c}(X)$ .

Corollary 8.

Let $a,b,c,d,e$ be circles on the plane. If $abc\to d$ is tight, $abd\to e$ and $cbd\to e$ are loose, then either $bd\to e$ , or $ad\to e$ and $cd\to e$ .

Proof.

Indeed, if $e\not\in ch_{c}(b,d)$ , then, by Theorem 7, we will conclude that $e\in ch_{c}(a,d)$ and $e\in ch_{c}(c,d)$ . ∎

In the statement of the next corollary, we use the numbering of geometries given in [11] along with their implications. Elements of geometries 12, 15, 21, 23, 27, 33, and 47 have been relabeled to better fit the statement of Corollary 8.

Corollary 9.

The following geometries, identified here by their tight implications, are not representable by circles on the plane:

Geometry 12: $abc\to d$ , $abd\to e$ , and $cbd\to e$ .

Geometry 15: $abc\to d$ , $ab\to e$ , and $cbd\to e$ .

Geometry 18: $abc\to d$ , $abd\to e$ , $cbd\to e$ , and $acd\to e$ .

Geometry 21: $abc\to d$ , $abd\to e$ , $cbd\to e$ , and $ace\to d$ .

Geometry 23: $abc\to d$ , $abd\to e$ , $cbd\to e$ , and $ac\to e$ .

Geometry 26: $abc\to d$ , $ad\to e$ , and $cbd\to e$ .

Geometry 27: $abc\to d$ , $ab\to e$ , $cbd\to e$ , and $ace\to d$ .

Geometry 33: $abc\to d$ , $ab\to e$ , and $cb\to e$ .

Geometry 35: $abc\to d$ , $ad\to e$ , $cbd\to e$ , and $ab\to e$ .

Geometry 45: $abc\to d$ , $ad\to e$ , and $cb\to e$ .

Geometry 47: $abc\to d$ , $ab\to e$ , $cb\to e$ , and $ace\to d$ .

Geometry 49: $abc\to d$ , $ab\to e$ , $cbd\to e$ , and $ac\to e$ .

Geometry 56: $abc\to d$ , $ad\to e$ , $cb\to e$ , and $ab\to e$ .

Geometry 60: $abc\to d$ , $ad\to e$ , $cbd\to e$ , $ac\to e$ , and $ab\to e$ .

Geometry 70: $abc\to d$ , $ab\to e$ , $cb\to e$ , and $ac\to e$ .

Geometry 89: $abc\to d$ , $a\to e$ , and $cbd\to e$ .

Geometry 94: $abc\to d$ , $ad\to e$ , $cb\to e$ , $ac\to e$ , and $ab\to e$ .

Geometry 134: $abc\to d$ , $a\to e$ , and $bc\to e$ .

Proof.

In all these geometries the assumptions of Corollary 8 hold, but the conclusion either does not follow from given implications, or make one of them not tight. ∎

5.3 Surrounding and capturing

The following result describes the situation of “capturing” circle $e$ surrounded within a special set-up of 4 other circles.

Theorem 10.

If $abc\to d$ is tight and $ad\to e$ , $bd\to e$ , $cd\to e$ , then $d\to e$ .

Proof.

Suppose the statement is proved when $r_{d}>0$ , and we have 5 circles with all assumptions of Theorem and $d=\{D\}$ . Since $abc\to d$ is tight, $D$ is an inner points of $\operatorname{CH}(a,b,c)$ . Therefore, we may set a small positive number as $r_{d}$ so that $abc\to d$ still holds, as well as other assumptions $ad\to e$ , $bd\to e$ , $cd\to e$ . Since we assumed that statement is proved for the case $r_{d}>0$ , we conclude that $d\to e$ . This will hold for arbitrary $r_{d}>0$ , therefore, $e=\{D\}=d$ , and we are done. Thus, we only prove Theorem under additional assumption that $r_{d}>0$ .

By Theorem 4, using the same labeling, the counterclockwise point order on $d$ beginning at $B_{1}$ is $B_{1},C_{1},A_{1},B_{2},C_{2},A_{2}$ .

Now, by Lemma 16 arc $\overset{\frown}{A_{2}C_{1}C_{2}}$ is part of the border for $\operatorname{CH}(a,d)\cap\operatorname{CH}(c,d)$ , and arc $\overset{\frown}{C_{1}C_{2}B_{1}}$ is part of the border for $\operatorname{CH}(b,d)\cap\operatorname{CH}(c,d)$ , see Figure 19.

$A_{2}\neq B_{1}$ , else $d\in ch_{c}(a,b)$ and $abc\to d$ is not tight, and $C_{1}\neq C_{2}$ , since $d$ is not contained in $c$ , so the complements of the arcs mentioned above are disjoint. Therefore, the two arcs forming the borders of the convex hulls include the entire border of $d$ . It follows that there is no point outside $d$ from $\operatorname{CH}(a,d)\cap\operatorname{CH}(b,d)\cap\operatorname{CH}(c,d)$ . Thus $Q_{d}(abc)=\emptyset$ and $d\to e$ . ∎

Corollary 11.

The following geometries, identified here by their tight implications, are not representable by circles on the plane:

Geometry 74: $abc\to d$ , $ad\to e$ , $bd\to e$ and $cd\to e$ .

Geometry 96: $abc\to d$ , $ad\to e$ , $bd\to e$ , $cd\to e$ and $ab\to e$ .

Geometry 105: $abc\to d$ , $ad\to e$ , $bd\to e$ , $cd\to e$ , $ab\to e$ and $ac\to e$ .

Geometry 143: $abc\to d$ , $a\to e$ , $bd\to e$ and $cd\to e$ .

Geometry 147: $abc\to d$ , $ad\to e$ , $bd\to e$ , $cd\to e$ , $ab\to e$ , $bc\to e$ and $ac\to e$ .

Geometry 206: $abc\to d$ , $a\to e$ , $bd\to e$ , $cd\to e$ and $bc\to e$ .

Geometry 235: $abc\to d$ , $a\to e$ , $b\to e$ and $cd\to e$ .

Geometry 351: $abc\to d$ , $a\to e$ , $b\to e$ and $c\to e$ .

Proof.

In all these geometries the assumptions of Theorem 10 hold, but the conclusion does not follow from given implications. ∎

6 Representation of geometries by ellipses

In paper [14] it was shown that from 672 known non-isomorphic geometries on 5-element set 623 can be represented by circles on the plane. From remaining 49, 8 are not representable due to the Weak carousel property from [2] or the Triangle property from [14]. It turns out that all of these 49 geometry can be represented by ellipses. See appendix for the representations.

In recent paper [12], it was shown that there exist convex geometries not representable by ellipses. The result provides Erdös-Szekeres type of obstruction and follows from specific construction in [8] of arbitrary large families of convex sets on the plane with the list of specific properties, which cannot be realized by families of ellipses.

But no specific convex geometry defined by convex sets or implications was found so far that cannot be represented by ellipses. Also, the minimal cardinality of the base set of such convex geometry is not yet known.

7 Geometries with colors

In this section, we propose a method of expanding the number of convex geometries which can be represented with circles in the plane by defining several unary predicates on the set of circles in representations. For visualization purposes unary predicates can be shown as colors.

7.1 An operator on systems with unary predicates

In this section we consider a general approach of defining a special operator on sets with unary predicates.

In general a $k$ -ary predicate on set $X$ is a subset of $X^{k}$ . In particular, for $k=1$ , a unary predicate $P$ is a subset of $X$ . Predicates are parts of the language of general algebraic systems, that may have, besides predicates, some functions defined on base set of a system. A unary predicate can distinguish elements from $X$ with a special property.

Suppose $P_{1},\dots,P_{s}$ are $s$ unary predicates on set $X$ , thus, we think of $\langle X;\{P_{1},\dots,P_{s}\}\rangle$ as an algebraic predicate system. For every $z\in X$ define $P(z)=\{k:z\in P_{k}\}$ .

Define an operator $\mathcal{S}:2^{X}\rightarrow 2^{X}$ as follows:

\mathcal{S}(Y)=\{z\in X:P(z)\subseteq\bigcup_{y\in Y}P(y)\}.

Lemma 17.

$\mathcal{S}$ is a closure operator on $X$ .

Proof.

Apparently, this operator is increasing and monotone. So we only need to check that it is idempotent: $\mathcal{S}(\mathcal{S}(Y))=\mathcal{S}(Y)$ . Indeed, $\mathcal{S}(\mathcal{S}(Y))=\{z\in X:P(z)\subseteq\bigcup_{y\in\mathcal{S}(Y)}P(y)\}=\{z\in X:P(z)\subseteq\bigcup_{y\in Y}P(y)\}=\mathcal{S}(Y)$ . ∎

The following example shows that $\mathcal{S}$ does not necessarily satisfy the anti-exchange property.

Example 1.

Consider $X=\{x,z,y_{1},y_{2},w\}$ and $P_{1}=\{x,z,y_{2}\}$ , $P_{2}=\{z,y_{1}\}$ . Then $P(x)=\{1\},P(z)=\{1,2\},P(y_{1})=\{2\},P(y_{2})=\{1\},P(w)=\emptyset.$ One can check that the range of $\mathcal{S}$ in $2^{X}$ is $\{w,y_{1}w,xy_{2}w,X\}$ .

Note that $\mathcal{S}$ does not satisfy the anti-exchange property: set $xy_{2}w$ covers $w$ in the lattice of closed sets, but the difference between the two subsets is 2 elements. ∎

Suppose now that we have another closure operator $\phi:2^{X}\rightarrow 2^{X}$ on $X$ . We then can define an associated operator $\phi_{\mathcal{S}}:2^{X}\to 2^{X}$ on $\langle X;\{P_{1},\dots,P_{s}\}\rangle$ as follows:

\phi_{\mathcal{S}}(Y)=\phi(Y)\cap\mathcal{S}(Y).

Lemma 18.

$\phi_{\mathcal{S}}$ is a closure operator. Moreover, $\phi_{\mathcal{S}}(Y)\subseteq\phi(Y)$ , for any $Y\in 2^{X}$ , therefore, all $\phi$ -closed sets are simultaneously $\phi_{\mathcal{S}}$ -closed.

Proof.

Since both $\phi$ and $\mathcal{S}$ are closure operators, so is operator $\phi_{\mathcal{S}}$ , which incidentally equals the greatest lower bound of two operators on poset of closure operators on $X$ . In particular, $\phi_{\mathcal{S}}(Y)\subseteq\phi(Y)$ for any $Y\in 2^{X}$ . Therefore, every $\phi(Y)$ is also closed for $\phi_{\mathcal{S}}$ . Indeed, $\phi(Y)\subseteq\phi_{\mathcal{S}}(\phi(Y))\subseteq\phi(\phi(Y))=\phi(Y)$ , i.e., $\phi_{\mathcal{S}}(\phi(Y))=\phi(Y)$ . ∎

The poset of closure operators on set $X$ was studied in J.B. Nation [13].

Unfortunately, operator $\phi_{\mathcal{S}}$ might not satisfy the anti-exchange property, even if $\phi$ does. This is due to the earlier observation that $\mathcal{S}$ may fail the anti-exchange property.

Example 2.

Consider 4-element base set $X=\{x,z,y_{1},y_{2}\}$ and linear convex geometry $(X,\phi)$ with following convex sets: $\{\emptyset,x,xy_{1},xzy_{1},xzy_{1}y_{2}\}$ . Suppose $P_{1}=\{x,z\}$ and $P_{2}=\{y_{1},y_{2}\}$ are two predicates on $X$ .

Then $\phi_{\mathcal{S}}(\{y_{1},y_{2}\})=\{y_{1},y_{2}\}$ , because $\phi$ -closure is the whole set and $\mathcal{S}(\{y_{1},y_{2}\})\\ =\{y_{1},y_{2}\}$ . Thus, $Y=\{y_{1},y_{2}\}$ is $\phi_{\mathcal{S}}$ -closed set. Moreover, $z$ is in $\phi_{\mathcal{S}}(Y\cup\{x\})$ , because $z$ is in $P_{1}$ together with $x$ , and $z$ is in $\phi(Y\cup\{x\})$ . But the same is true when they are switched: $x$ is in $\phi_{\mathcal{S}}(Y\cup\{z\})$ . Thus, we can exchange elements $x,z$ and anti-exchange fails. This is shown by the fact that in the lattice of closed sets of $\phi_{\mathcal{S}}$ from element $Y$ to $X$ there is no progression by adding one element: one would jump by two elements $x,z$ . ∎

Example 3.

We could change the predicates on $X$ from Example 2 and get an extension of convex geometry $(X,\phi)$ in that example. Let $P_{1}=\{z,y_{2}\}$ , $P_{2}=\{x\}$ . Then $P(y_{1})=\emptyset,P(z)=P(y_{2})=\{1\}$ , $P(x)=\{2\}$ .

We verify that there are new closed sets $\{y_{1}\},\{zy_{1}\},\{z,y_{1},y_{2}\}$ for operator $\phi_{\mathcal{S}}$ . Moreover, the operator is with the anti-exchange property. ∎

What was shown in Example 3 is possible to achieve for convex geometries given by circle configuration. Introducing one, two or three predicates to circle configuration, it is possible to represent all 5-element geometries that are not representable by circles only.

Example 4.

It was shown in Corollary 9 that G134 is not representable by circles. G134 is given by the following implications on $X=\{a,b,c,d,e\}$ :

abc\to d,bc\to e,a\to e

The geometry $G=(X,\operatorname{CH})$ on same set $X$ as circles, with closure operator $\operatorname{CH}$ , represented on Figure 21 satisfies these implications, except $abc\to d$ is not tight, and can be replaced by $bc\to d$ .

Figure 21:

abc\to de,bc\to e,a\to e,C_{1}=\{a,b,c,e\},C_{2}=\{a,d\}

It can be checked directly that the family of closed sets of G134 has $bce$ , which is not closed in $G$ .

We can introduce two predicates $C_{1}=\{a,b,c,e\}$ and $C_{2}=\{a,d\}$ on $X$ , which results in the following family of closed sets for operator $\mathcal{S}$ :

\emptyset,d,bce,X

Note that sets $\emptyset$ and $d$ are already closed in $G$ , and proper intersections of closed sets of $G$ with $bce$ give $b,c,e,be,ce$ , which are already $\operatorname{CH}$ -closed. Therefore, $bce$ is the only new closed set of operator $\operatorname{CH}_{\mathcal{P}}$ compared to $\operatorname{CH}$ . Moreover, set $bcde$ is $\operatorname{CH}$ -closed set, which is one-point extension of $bce$ . This means that $\operatorname{CH}_{\mathcal{P}}$ has exactly one more closed set than $\operatorname{CH}$ and it satisfies the anti-exchange property. ∎

7.2 Sufficient condition for representation with unary predicates

We are going to formulate a sufficient property of operator $\mathcal{S}$ so that a closure system with operator $\phi$ can be expanded by $\mathcal{S}$ -closed sets so that $\phi_{\mathcal{S}}$ still satisfies the anti-exchange property. Let $\mathcal{C}_{\phi}$ be the family of $\phi$ -closed sets.

Recall, say, from [6] that subset $Y\subseteq X$ is called quasi-closed w.r.to operator $\phi$ , if it is not in $\mathcal{C}_{\phi}$ and $\mathcal{C}_{\phi}\cup\{Y\}$ is closed under the intersection, i.e., it is a family of closed sets of another closure operator. Such property is equivalent to:

Z\cap Y\in\mathcal{C}_{\phi}\text{ or }Z\cap Y=Y

for all $Z\in\mathcal{C}_{\phi}$ .

Lemma 19.

Suppose $\phi$ is a closure operator with the anti-exchange property defined on set $X$ , and operator $\mathcal{S}$ is defined by unary predicates $P_{1},\dots,P_{k}$ on $X$ . Assume that every $\mathcal{S}$ -closed set is ether $\phi$ -closed or quasi-closed w.r.t. $\phi$ , and in latter case has one-element extension in $\mathcal{C}_{\phi}$ . Then $\phi_{\mathcal{S}}$ satisfies the anti-exchange property as well.

Proof.

$\phi_{\mathcal{S}}$ -closed sets are of the form $C\cap L$ , where $C\in\mathcal{C}_{\phi}$ and $L$ is $\mathcal{S}$ -closed. By the definition, it is either in $\mathcal{C}_{\phi}$ , or it is $L$ . Thus only $\mathcal{S}$ -closed sets may be added to the family of $\phi$ -closed sets. By assumption, all $\mathcal{S}$ -closed sets have one-element extensions in $\mathcal{C}_{\phi}$ , thus, adding them to $\mathcal{C}_{\phi}$ will give us a closure system with one-point extension, which is equivalent to $\phi_{\mathcal{S}}$ to satisfy the anti-exchange property. ∎

Revisiting Example 4, note that the closed sets of operator $\mathcal{S}$ are

\emptyset,d,bce,X

From these, only $bce$ is not $\phi$ -closed. We check that all proper intersections of this set with $\phi$ -closed sets give $c,e,be,b,ce$ , which are $\phi$ -closed. Therefore, $bce$ is quasi-closed. It also has one-element extension among $\phi$ -closed sets. Therefore, Lemma 19 applies.

The next example shows that Lemma 19 allows some further generalization.

Example 5.

Consider representation of $G7$ (id: 4294924159 in [14]) by circles with predicates given by implications

acd\to e,abd\to e,abc\to e

We start with representation of $G7$ on 4-element set $\{b,c,d,e\}$ , with id:65303 from [14]. It is defined by implications

cd\to e,bd\to e,bc\to e

If we ignore color-predicates on Figure 22, then we get representation of G52(id: 4294907671 in [14]) on $X=\{a,b,c,d,e\}$ with implications

cd\to e,bd\to e,bc\to e,

i.e., $b,c,d,e$ represent $G7$ on $\{b,c,d,e\}$ , and $a$ is added so that $a$ does not participate in any implication.

We can introduce two predicates on $X$ : red and blue, where $R=\{a,e\}$ and $B=\{b,c,d\}$ , as on Figure 22. This gives the $\mathcal{S}$ -closed sets:

\emptyset,ae,bcd,X

This time, $\emptyset,ae,X$ are closed in $G52=(X,\phi)$ , while $bcd$ is neither closed nor quasi-closed, and intersections of $bcd$ with $\phi$ -closed sets give non-closed sets for $\phi$ :

bc,bd,cd.

All of these are quasi-closed w.r.t. $\phi$ , and they have one-point extensions in $C_{\phi}$ : $bce,bde,cde$ , respectively. Similarly, $bcd$ has one-point extension $bcde$ in $C_{\phi}$ . Thus, sets $bc,cd,bd,bcd$ can be added to $C_{\phi}$ preserving one-point extension property, which guarantees that $C_{\phi}$ has AEP.

Adding $bc,cd,bd,bcd$ to $\phi$ -closed sets, make all subsets of $\{b,c,d,e\}$ $\phi_{\mathcal{S}}$ -closed, but $abc,acd,abd,abcd$ are still not closed, which gives needed implications describing $\phi_{\mathcal{S}}$ :

acd\to e,abd\to e,abc\to e.

This example shows that we can extend assumptions of Lemma 19 to sets that are the intersections of $\phi$ -closed and $\mathcal{S}$ -closed sets, and obtain the same conclusion.

7.3 Geometry that requires more than 2 colors

In Appendix A we show colored representations of all convex geometries on 5-element set which cannot be represented by circles. Most of them require only one or two colors for representation by colored circles. Only one geometry, G18 requires three colors, which is demonstrated in this section.

Proposition 12.

Convex geometry G18 on 5-element set defined by implications:

abc\to de,acd\to e,bcd\to e,abd\to e

cannot be represented by circles with coloring by at most two colors.

Proof.

Assume that we have representation of G18 by 5 circles with at most two colors $c_{1}$ and $c_{2}$ . Let $A,B,C,D,E$ be color sets of $a,b,c,d,e$ respectively. Since we have $abc\to d$ tight, $abd\to e$ and $bcd\to e$ , by Corollary 8 we have either $bd\to e$ or $ad\to e$ and $cd\to e$ that hold by the convex hall operator on circles. We study both of these cases and show that we get to a contradiction.

Case 1: Assume that $ad\to e$ and $cd\to e$ hold. Since $ad\to e$ and $cd\to e$ by the convex hull operator, we need to have some color $c_{1}\in E$ such that $c_{1}\notin D$ , $c_{1}\notin C$ and $c_{1}\notin A$ . Thus $A,C,D\subseteq\{c_{2}\}$ . Thus $acd\to e$ does not hold with the new $\operatorname{CH}_{C}$ operator, since $c_{1}\in E$ and $A,C,D=\{c_{2}\}$ . This brings to the contradiction.

Case 2: $bd\to e$ . We further split it into two sub-cases:

Case 2.1: Suppose $cd\to e$ holds for the convex hall operator on circles. Since $bd\to e$ and $cd\to e$ by the convex hull operator, we need to have some color $c_{1}\in E$ such that $c_{1}\notin D$ , $c_{1}\notin C$ and $c_{1}\notin B$ . Thus $B,C,D\subseteq\{c_{2}\}$ and $bcd\to e$ does not hold with the new $\operatorname{CH}_{C}$ operator. This brings to the contradiction.

Case 2.2: Assume that $cd\not\to e$ . We use Corollary 8 again, relabelling b with c. Since $abc\to d$ tight, $acd\to e$ and $bcd\to e$ , by Corollary 8 we have either $cd\to e$ or $ad\to e$ and $bd\to e$ . Now, since $cd\not\to e$ , we have $ad\to e$ and $bd\to e$ . Since $ad\to e$ and $bd\to e$ hold for the convex hull operator, we need to have some color $c_{1}\in E$ such that $c_{1}\notin D$ , $c_{1}\notin B$ and $c_{1}\notin A$ . Thus $A,B,D\subseteq\{c_{2}\}$ . Thus, $abd\to e$ does not hold with the new $\operatorname{CH}_{C}$ operator, bringing to the contradiction. ∎

On the other hand, the representation with three colors is possible and it is shown on Figure LABEL:fig:G18.

8 Acknowledgments.

The paper follows up [14] completed by the team of 18 undergraduate and 2 graduate students in 2020, in the framework of PolyMath - 2020 project. We thank participants of the original project who continued to support the work of the current group in various capacities: Fernanda Yepez-Lopez, Rohit Pai and Stephanie Zhou.

Address for correspondence:
Kira Adaricheva, Department of Mathematics, Hofstra University, Hempstead NY, 11549
Email address: [email protected]

References

[1] K. Adaricheva, B. Brubaker, P. Devlin, S. J. Miller, V. Reiner, A. Seceleanu, A. Sheffer, and Y. Zeytuncu, When life gives you lemons, make mathematicians, Notices of AMS, March 2021, 375–78.
[2] K. Adaricheva, M. Bolat, Representation of finite convex geometries by circles on the plane, Discrete Mathematics v.342 (2019), N3, 726-746.
[3] Adaricheva K.V., Gorbunov V.A., Tumanov V.I., Join-semidistributive lattices and convex geometries, Advances in Mathematics 173(2003), 1-49.
[4] K. Adaricheva, J.B.Nation, Convex geometries, in Lattice Theory: Special Topics and Applications, v.2, G. Grätzer and F. Wehrung, eds. Springer, Basel, 2016.
[5] K. Adaricheva, J.B.Nation, Bases in closure systems, in Lattice Theory: Special Topics and Applications, v.2, G. Grätzer and F. Wehrung, eds. Springer, Basel, 2016.
[6] N. Caspard and B. Monjardet, The lattices of closure systems, closure operators, and implicational systems on a finite set: a survey, Disc. Appl. Math. 127 (2003), 241–269.
[7] G. Czédli, Finite Convex Geometries of Circles. Discrete Mathematics 330 (2014), 61–75.
[8] M.G.Dobbins, A.Holmes, A.Hubard, Regular systems of paths and families of convex sets in convex position, Trans. AMS 368 (2016), N5, 3271–3303.
[9] P.H. Edelman and R.E. Jamison, The Theory of Convex Geometries. Geom Dedicata 19 (1985), 247–274.
[10] P.H. Edelman and M. Saks, Combinatorial representation and convex dimension of convex geometries. Order 5 (1988), 23–32.
[11] GeoGebra Toolkit https://www.geogebra.org/classic/dk88mrgu
[12] J. Kincses, On the representation of finite convex geometries with convex sets, Acta Sci. Math.83 (2017).
[13] J.B.Nation, Closure operators and lattice extensions. Order 21 (2004), 43–48.
[14] PolyMath REU-2020, Convex geometries representable by at most 5 circles on the plane, arxiv: 2008.13077

\appendixpage\addappheadtotoc