[4] **viXra:1807.0197 [pdf]**
*submitted on 2018-07-09 09:58:18*

**Authors:** Thinh D. Nguyen

**Comments:** 3 Pages.

In this work, we will take one problem, namely Packing Triangles as an example of combinatorial optimization problems. We show that if one has ever loved reading Prasolov’s books, then one should not try to ﬁnd efﬁcient algorithm for various restricted cases of this problem.

**Category:** General Mathematics

[3] **viXra:1807.0125 [pdf]**
*submitted on 2018-07-05 14:59:41*

**Authors:** Thinh Nguyen

**Comments:** 19 Pages.

We prove that for every d≥2, deciding if a pure, d-dimensional, simplicial complex is
shellable is NP-hard, hence NP-complete. This resolves a question raised, e.g., by Danaraj
and Klee in 1978. Our reduction also yields that for every d≥2 and k≥0, deciding if a pure,
d-dimensional, simplicial complex is k-decomposable is NP-hard. For d≥ 3, both problems
remain NP-hard when restricted to contractible pure d-dimensional complexes. Another
simple corollary of our result is that it is NP-hard to decide whether a given poset is CL-
shellable.

**Category:** General Mathematics

[2] **viXra:1807.0098 [pdf]**
*submitted on 2018-07-03 06:11:19*

**Authors:** Thinh Nguyen

**Comments:** 4 Pages.

The Erd ̋os-Szekeres theorem states that, for every $k$, there is a number $n_k$ such that every set of $n_k$ points in general position in the plane contains a subset of $k$ points in convex position. If we ask the same question for subsets whose convex hull does not contain any other point from the set, this is not true: as shown by Horton, there are sets of arbitrary size that do not contain an empty 7-gon.
These questions have also been studied extensively
from a computational point of view, and polynomial time algorithms for finding the largest (empty) convex set have been given for the planar case. In higher dimension, it is not known how to compute such a set efficiently. In this paper, we show that already in 3 dimensions no polynomial time algorithm exists for determining the largest (empty) convex set (unless $P$=$NP$), by proving that the corresponding decision problem is $NP$-hard. This answers a question by Dobkin, Edelsbrunner and Overmars from 1990.
As a corollary, we derive a similar result for the closely related problem of testing weak $ε$-nets in $R^3$ . Answering a question by Chazelle et al. from 1995, our reduction shows that the problem is $co-NP$-hard.
Finally, we make several suggestions for further research on the subject.

**Category:** General Mathematics

[1] **viXra:1807.0031 [pdf]**
*replaced on 2018-07-02 07:45:23*

**Authors:** August Lau

**Comments:** 6 Pages.

Mathematics has been highly effective in its application of formalism to the real world. It spans from physical science to data science. Mathematical algorithm affects our everyday life. Mathematization (converting data to equations or mathematical forms) has been very successful. It has led to comments like “the unreasonable effectiveness of mathematics,” but we might have “unreasonable expectation of mathematics.”

**Category:** General Mathematics