A lower bound on the number of diagonals for polyhedra

Introduction Proof

A lower bound on the number of diagonals for polyhedra

Kazuhiro Ichihara

Nihon University, College of Humanities and Sciences

Joint work with

Shunsuke Kojima (Nihon Univ.)

“Topology and Computer 2018”

Nara Womens’ University, Oct. 14, 2018

Introduction Proof

Motivation

M. Wada, Y. Yamashita and H. Yoshida: An inequality for polyhedra and ideal triangulations of cusped hyperbolic 3-mainfolds, Proc. Amer. Math.

Soc. 124 (1996), no. 12, 3905–3911.

Let M be a non-compact hyperbolic 3-manifold of finite volume.

Question.

Can we decompose M into ideal tetrahedra?

Theorem [Wada-Yamashita-Yoshida]

Suppose that M is obtained from n convex ideal polyhedra P

, . . . , P

by identifying the faces in pairs. Suppose that each face of P

(i = 1, . . . , n − 1) is pasted with a face of P

, and the possibly remaining

faces of P

glued in pairs. Then M can be decomposed into

Introduction Proof

Motivation

Let P be a polyhedra, and denote

V = V (P ), E = E(P ), F = F (P ), F

= F

(P )

the sets of vertices, edges, faces, and d-gonal faces of P.

Theorem 1 [Wada-Yamashita-Yoshida]

In the notion above, we have

| V | ( | V | − 1) ≥ 8 | F

| + ∑

d≥5

d(d − 1) | F

|

Equality in the above holds if and only if P is combinatorially

equivalent to one of the polyhedra depicted in Figure 1.

Introduction Proof

Motivation

Theorem 1 is equivalent to the following:

Theorem 2 [ Wada-Yamashita-Yoshida ]

Let ∆(P ) denote the set of (interior) diagonals of a polyhedron P.

Then the following always holds:

| ∆(P) | ≥ − 3

2 | F

| + ∑

d≥5

d 2 | F

|

Equality in the above holds if and only if P is combinatorially

equivalent to one of the polyhedra depicted in Figure 1.

Introduction Proof

Figure 1 (1)

(calculation)

(left side)= | ∆(P ) | = 2 (right side)= −

|F

| + ∑

d≥5 d 2

|F

|

= −

× 2 +

× 2 = 2

Introduction Proof

Figure 1 (2)

(calculation)

(left side)= | ∆(P ) | = 6 (right side)= −

|F

| + ∑

d≥5 d 2

|F

|

= −

× 3 +

× 3 +

× 1 = 6

Introduction Proof

Remarks

Wada-Yamashita-Yoshida

In the proof of Theorem 1, (after smart reductions to the finite number of cases), they wrote:

“Next consider the case where r < 9. Running a computer program shows that there are twelve sequences ...”

However, no actual codes could be shown...

Our contribution

An alternative proof of Thm 2 without computer-asistance.

Introduction Proof

Remarks

Wada-Yamashita-Yoshida

In the proof of Theorem 1, (after smart reductions to the finite number of cases), they wrote:

“Next consider the case where r < 9. Running a computer program shows that there are twelve sequences ...”

However, no actual codes could be shown...

Our contribution

An alternative proof of Thm 2 without computer-asistance.

Introduction Proof

Outline of Proof Theorem 2 (1)

| ∆(P ) | ≥ − 3

2 | F

(P ) | + ∑

d≥5

d

2 | F

(P ) |

We show it by induction about the number of faces |F (P)| . Refer the right-hand side as δ(P );

δ(P ) = − 3

2 | F

(P ) | + ∑

d≥5

d

2 | F

(P ) |

(i) | F (P ) | = 4 (the minimal number of faces for polyhedra)

|∆(P)| = 0 δ(P ) = −6

Introduction Proof

Lemma

Lemma

If | ∆(P ) | = 0, then 3 | F

(P ) | > ∑

d≥5

d | F

(P ) | holds.

We show Lemma by contraposition.

Suppose that 3|F

(P)| ≤ ∑

d≥5

d|F

(P )|

Then, there exists an edge such as;

⇒ | ∆(P) | ̸ = 0

Introduction Proof

Lemma

Lemma

If | ∆(P ) | = 0, then 3 | F

(P ) | > ∑

d≥5

d | F

(P ) | holds.

We show Lemma by contraposition.

Suppose that 3|F

(P)| ≤ ∑

d≥5

d|F

(P )|

Then, there exists an edge such as;

⇒ | ∆(P) | ̸ = 0

Introduction Proof

Now suppose | ∆ | ≥ δ holds for any polyhedron with | F | ≤ k − 1 for k ≥ 5, and consider a polyhedron P with |F (P )| = k.

Key operation: collapsing a face

Introduction Proof

Now suppose | ∆ | ≥ δ holds for any polyhedron with | F | ≤ k − 1 for k ≥ 5, and consider a polyhedron P with |F (P )| = k.

Key operation: collapsing a face

Introduction Proof

Sample case

The number of diagonals toward to each vertex of d-gon is

d(d − 3) at least.

Introduction Proof

(setting)

(the number of quadrangle adjacent to collapsed face ):=d

(the number of pentagon adjacent to collapsed face ):=d

(the number of d-gon adjacent to collapsed face ):=d

(d ≥ 6)

(change by collapsing a face: P ⇝ P

)

| ∆(P ) | − d(d − 3) − d

(d − 2) − 2d

(d − 2) ≥ | ∆(P

) |

| F

(P ) | + d

= | F

(P

) |

∑

d≥5

d|F

(P )| − d − 5d

− d

= ∑

d≥5

d|F

(P

)|

Introduction Proof

(calculation)

| ∆(P ) | ≥ | ∆(P

) | + d(d − 3) + d

(d − 2) + 2d

(d − 2)

= −

| F

(P

) | +

∑

d | F

(P

) | + d(d − 3)

+d

(d − 2) + 2d

(d − 2)

= −

| F

(P ) | −

d

+

∑

d | F

(P ) | −

−

d

−

+d

(d − 2) + 2d

(d − 2)

≥ δ(P ) + d

−

d −

d

−

d

+ 3d

−

+ 6d

= δ(P ) + d(d −

) −

d

+

d

+

d

≥ δ(P ) + d(d − 5) +

d

+

d

Introduction Proof

Some other cases

If there are triangles adjacent to a face, we can’t collapse the face.

Then, we need some more operations.

Operation 1

Introduction Proof

Operation 2

Introduction Proof

Proof for the equality

| ∆(P ) | ≥ −

| F

(P ) | + ∑

d≥5 d

2

| F

(P ) |

⇒ one of the polyhedra shown in Figure 1 (Proof)

We conform the change by collapsing a face;

| ∆(P ) | − δ(P ) ≥ | ∆(P

) | − δ(P

) + . Then

|∆(P

)| − δ(P

) ≥ 0 by the argument before, and so;

| ∆(P ) | − δ(P ) = 0 ⇒ ≤ 0.

We calculate in the case that we can collapse a face and a collapse face is triangle.

= 1 − d

− d

+ d

+

d

Introduction Proof

Case by case arguments..

(1) 1 − d

− d

+ d

+

d

= 0 (i) d

= d

= d

= 1, d

= 0 (ii) d

= 2, d

= 1, d

= 0

(iii) d

= 2, d

= 1, d

= 0 ⇒ (Figure 1 right) (2) 1 − d

− d

+ d

+

d

< 0

(i) d

= 3, d

= 0 d

= 2

(ii) d

= 2, d

= 1, d

= 0 d

= 2

(iii) d

= 1, d

= 2, d

= 0 ⇒ (Figure 1 left) d

= 2

(iv) d

= 3, d

= 0

d

= 2

Introduction Proof

Thank you for your attention!