The Hamiltonian cycle problem is an important problem in graph theory and computer science. It is a special case of the famous traveling salesman problem. A signicant amount of research has been done on the special cases of nding Hamiltonian cycles in subgraphs of triangular, square and hexagonal grids. However, there is little work on more complicated grids. In this paper, we investigate the hardness of Hamiltonian cycle problem in grid graphs of semiregular tessellations, which are tessellations formed by two or more kinds of regular polygons. There are only eight semiregular tessellations, and we prove that the Hamiltonian cycle problem in all of them are NP-complete by reducing from NP-complete problems, such as the Hamiltonian cycle problem in max degree 3 bipartite planar graphs. Knowing the NP-completeness of Hamiltonian cycle problem in semiregular grids indicates that there will not be any polynomial time algorithm that solves the Hamiltonian path problem in these tessellations if NP does not equal to P, which helps show the limits of ecient motion planning algorithms and provides new information about what makes problems computationally dicult to solve.

To study arithmetic structures of natural numbers, we introduce a notion of entropy of arithmetic functions, called anqie entropy. This entropy possesses some crucial properties common to both Shannon's and Kolmogorov's entropies. We show that all arithmetic functions with zero anqie entropy form a C*-algebra. Its maximal ideal space defines our arithmetic compactification of natural numbers, which is totally disconnected but not extremely disconnected. We also compute the $K$-groups of the space of all continuous functions on the arithmetic compactification. As an application, we show that any topological dynamical system with topological entropy $\lambda$, can be approximated by symbolic dynamical systems with entropy less than or equal to $\lambda$.

No abstract uploaded!

Let (X, ) be a pair. We study how the condition (X, ) causes surjectivity or birationality of the Albanese map and the Albanese morphism of (X, ) in both characteristic (X, ) and characteristic (X, ) . In particular in characteristic (X, ) we generalize Kawamata's result to the cases of log canonial pairs, and in characteristic (X, ) we generalize a result of Hacon-Patakfalvi to the cases of log pairs. Moreover we show that if (X, ) is a normal projective threefold in characteristic (X, ) , the coefficients of the components of (X, ) are (X, ) and (X, ) is semiample, then the Albanese morphism of (X, ) is surjective under reasonable assumptions on (X, ) and the singularities of the general fibers of the Albanese morphism. This is a positive characteristic analog in dimension 3 of a result of Zhang on a conjecture of Demailly-Peternell-Schneider.

This paper is motivated by the problem of subdividing a prismatic mesh to a tetrahedral mesh (without inserting Steiner points) so as to not only match arbitrarily prescribed boundary conditions but also allow arbitrary topologies in the base mesh. We explore all possible combinations of these two factors, and propose a complete solution to this 3D problem by converting it to an equivalent 2D graph problem, called cutting flow problem. For each case, we not only prove the sufficient and necessary condition for the existence of solutions, but also provide linear and provable algorithms to compute a solution whenever there is one.