PDF《k -gons?》

k, by adding small sides at corner points. Henderson [10] gave an example of a symmetric Venn diagram of ?ve quadrilaterals. Gr¨ unbaum ?rst considered the problem of what polygons can be used to create Venn diagrams in [7], in which he gave a Venn diagram of six quadrilaterals (4-gons), a diagram of ?ve triangles, and an independent family of ?ve squares. He also provides a construction showing that n-Venn diagrams can be constructed from convex polygons, for any n. In [9] he conjectured that there is no symmetric Venn diagram of ?ve squares. We restate two lemmas ?rst observed by Gr¨ unbaum [7], some of the consequences of which inspired this work. A FISC is a family of Finitely I ntersecting Simple closed Curves in the plane, with the property that the intersection of the interiors of all the curves is not empty [3]. Clearly, every Venn diagram is a FISC. Lemma 1.2. In a FISC of n convex k-gons there are at most n

2 2k vertices. Proof. A pair of convex k-gons can intersect with each other at most 2k times;

there are n

2 pairs. Lemma 1.3. In a simple n-Venn diagram of k-gons, k ≥ (2n?1 ? 1)/ n

2 . (1) Proof. Euler'

s formula for plane graphs, combined with the fact that in a simple diagram all vertices have degree four, implies that the number of vertices in a simple Venn diagram is 2n ? 2. Combining this with Lemma 1.2, which gives an upper bound on the number of vertices, the inequality follows. Lemma 1.3 gives us a bound, for each n, on the minimum k required to form a simple n-Venn diagram of k-gons. Diagrams are well-known that achieve the bounds for n ≤ 5;

see [12] for examples. For n = 6, the Lemma implies k ≥ 3, and Carroll [4] achieved the lower bound by giving examples of 6-Venn diagrams formed of triangles;

his diagrams are all simple. Figure

1 shows one of Carroll'

s Venn diagrams of six triangles. For n = 7, Lemma 1.3 implies that k ≥ 3;

however until now the diagram with the smallest known k was a 7-Venn diagram of non-convex 5-gons by Gr¨ unbaum in [9]. The contributions of this paper are, ?rst, to prove a tighter lower bound than Lemma 1.3 for the minimum k required to draw a simple Venn diagram of k-gons;

second, to show that no 7-Venn diagram of triangles (simple or not) can exist, and third, to achieve the new lower bound for n =

7 by exhibiting a Venn diagram of seven quadrilaterals. In [7], Theorem

3 contains bounds on k? (n), which is de?ned as the minimal k such that there exists a Venn diagram of n k-gons. Carroll'

s results prove that k? (6) = 3, and our results prove that k? (7) = 4, and provide a lower bound on k? (n) for n >

7 when considering simple diagrams.

2 Venn Diagrams of k-Gons We now prove a tighter lower bound than that given by Lemma 1.3 for simple Venn diagrams. Observation 2.1. In a Venn diagram composed of convex curves, each curve has exactly one edge on the outer face. Figure 1: A Venn diagram of six triangles. Proof. An r-region is a region contained inside exactly r curves. It is proven in [3] that in a Venn diagram composed of convex curves, every r-region with r >

0 is adjacent to an (r ? 1)-region. In particular, every 1-region is adjacent to the outer face, and thus every curve has an edge on the outer face. Furthermore, Lemma 4.6 from [5] states that no two edges on any face in Venn diagram can belong to the same curve. We now introduce some notation before proving the main theorems of this section. In a Venn diagram of k-gons, consider any two k-gons Ci and Cj,

1 ≤ i <

j ≤ n. The corners of Ci may be labelled according to whether they are external (E) to Cj or internal (I) to Cj We only consider simple diagrams here and thus b........