Regular combinatorial maps

The classical approach to maps is by cell decomposition of a surface. A combinatorial map is a graph-theoretic generalization of a map on a surface. Besides maps on orientable and non-orientable surfaces, combinatorial maps include tessellations, hypermaps, higher dimensional analogues of maps, and certain toroidal complexes of Coxeter, Shephard, and Grünbaum. In a previous paper the incidence structure, diagram, and underlying topological space of a combinatorial map were investigated. This paper treats highly symmetric combinatorial maps. With regularity defined in terms of the automorphism group, necessary and sufficient conditions for a combinatorial map to be regular are given both graph- and group-theoretically. A classification of regular combinatorial maps on closed simply connected manifolds generalizes the well-known classification of metrically regular polytopes. On any closed manifold with nonzero Euler characteristic there are at most finitely many regular combinatorial maps. However, it is shown that, for nearly any diagram D, there are infinitely many regular combinatorial maps with diagram D. A necessary and sufficient condition for the regularity of rank 3 combinatorial maps is given in terms of Coxeter groups. This condition reveals the difficulty in classifying the regular maps on surfaces. In light of this difficulty an algorithm for generating a large class of regular combinatorial maps that are obtained as cyclic coverings of a given regular combinatorial map is given.     

Discrete quasi-Einstein metrics and combinatorial curvature flows in 3-dimension

Motivated by the definition of combinatorial scalar curvature given by Cooper and Rivin, we introduce a new combinatorial scalar curvature. Then we define the discrete quasi-Einstein metric, which is a combinatorial analogue of the constant scalar curvature metric in smooth case. We find that discrete quasi-Einstein metric is critical point of both the combinatorial Yamabe functional and the quadratic energy functional we defined on triangulated 3-manifolds. We introduce combinatorial curvature flows, including a new type of combinatorial Yamabe flow, to study the discrete quasi-Einstein metrics and prove that the flows produce solutions converging to discrete quasi-Einstein metrics if the initial normalized quadratic energy is small enough. As a corollary, we prove that nonsingular solution of the combinatorial Yamabe flow with nonpositive initial curvatures converges to discrete quasi-Einstein metric. The proof relies on a careful analysis of the discrete dual-Laplacian, which we interpret as the Jacobian matrix of curvature map.     

Combinatorial 3-Manifolds with Transitive Cyclic Symmetry

In this article we give combinatorial criteria to decide whether a transitive cyclic combinatorial d-manifold can be generalized to an infinite family of such complexes, together with an explicit construction in the case that such a family exists. In addition, we substantially extend the classification of combinatorial 3-manifolds with transitive cyclic symmetry up to 22 vertices. Finally, a combination of these results is used to describe new infinite families of transitive cyclic combinatorial manifolds and in particular a family of neighborly combinatorial lens spaces of infinitely many distinct topological types.     

Combinatorial sums through Riordan arrays

The aim of this work is to show how Riordan arrays are able to generate and close combinatorial identities, by means of the method of coefficients (generating functions). We also show how the same approach can be used to deal with other combinatorial problems, for instance asymptotic approximation and combinatorial inversion. Finally, we propose a method for generating new combinatorial sums by extending the concept of Riordan arrays to bi-infinite matrices.     

Toward a model for students’ combinatorial thinking

Combinatorics has many applications in different disciplines, however, only a few studies have explored students’ combinatorial thinking at the upper secondary and tertiary levels concurrently. The present research is a grounded theory study of eight Year 12 and five undergraduate students, who have participated in semi-structured interviews and responded to eight combinatorial tasks. Three types of combinatorial tasks were designed: combinatorial reasoning, evaluating, and problem-posing tasks. In the open coding phase of data analysis, seventy-one codes were identified which categorized into seven main categories at the axial coding phase. At the selective coding phase, five relationships between categories were identified that led to designing a model of students’ combinatorial thinking. The model consists of three movements: Horizontal, vertical downward, and vertical upward movement. It is asserted that this model could be used to improve the quality of teaching combinatorics, and also as a lens to explore students’ combinatorial thinking.     

On an extension of a combinatorial identity

Using Frobenius partitions we extend the main results of [4]. This leads to an infinite family of 4-way combinatorial identities. In some particular cases we get even 5-way combinatorial identities which give us four new combinatorial versions of Göllnitz-Gordon identities.     

The method of combinatorial telescoping

We present a method for proving q-series identities by combinatorial telescoping, in the sense that one can transform a bijection or a classification of combinatorial objects into a telescoping relation. We shall illustrate this method by giving a combinatorial derivation of Watson's identity, which implies the Rogers-Ramanujan identities.     

On Incidence Algebras of Combinatorial Inverse Monoids

We study the incidence algebra of the reduced standard division category of a combinatorial bisimple inverse monoid [with (E(S), ≤) locally finite], and we describe semigroups of poset type (i.e., a combinatorial inverse semigroup for which the corresponding Möbius category is a poset) as being combinatorial strict inverse semigroups. Up to isomorphism, the only Möbius-division categories are the reduced standard division categories of combinatorial inverse monoids.     

Earthquakes and circle packings

We prove that earthquakes on hyperbolic surfaces can be approximated by discrete earthquakes constructed using circle packings. Consequently, we obtain a combinatorial version of Thurston’s Earthquake Theorem. Any surface can be approximated by combinatorial earthquakes of a packable surface. This provides a controlled combinatorial method for deforming hyperbolic surfaces.     

An asymptotical study of combinatorial optimization problems by means of statistical mechanics

The analogy between combinatorial optimization and statistical mechanics has proven to be a fruitful object of study. Simulated annealing, a metaheuristic for combinatorial optimization problems, is based on this analogy. In this paper we show how a statistical mechanics formalism can be utilized to analyze the asymptotic behavior of combinatorial optimization problems with sum objective function and provide an alternative proof for the following result: Under a certain combinatorial condition and some natural probabilistic assumptions on the coefficients of the problem, the ratio between the optimal solution and an arbitrary feasible solution tends to one almost surely, as the size of the problem tends to infinity, so that the problem of optimization becomes trivial in some sense. Whereas this result can also be proven by purely probabilistic techniques, the above approach allows one to understand why the assumed combinatorial condition is essential for such a type of asymptotic behavior.     

On a combinatorial theorem related to a theorem of G. Szegö

In 1954, M. Kac discovered a probabilistic interpretation of a theorem of G. Szegö of Toeplitz matrices and demonstrated that this theorem can be provedin an elementary way by using a combinatorial identify of G. A. Hunt. In this paper Hunt's combinatorial identity is derived from a more general combinatorial result.     

Phase space universality for multimodal maps

We study the dynamics of the renormalization operator for multimodal maps. In particular, we develop a combinatorial theory for certain kind of multimodal maps. We also prove that renormalizations of infinitely renormalizable multimodal maps with same bounded combinatorial type are exponentially close. Our results imply, for instance, the existence and uniqueness of periodic points for the renormalization operator with arbitrary combinatorial type.     

Investigating undergraduate students’ proof schemes and perspectives about combinatorial proof

Combinatorics is an area of mathematics with accessible, rich problems and applications in a variety of fields. Combinatorial proof is an important topic within combinatorics that has received relatively little attention within the mathematics education community, and there is much to investigate about how students reason about and engage with combinatorial proof. In this paper, we use Harel and Sowder’s (1998) proof schemes to investigate ways that students may characterize combinatorial proofs as different from other types of proof. We gave five upper-division mathematics students combinatorial-proof tasks and asked them to reflect on their activity and combinatorial proof more generally. We found that the students used several of Harel and Sowder’s proof schemes to characterize combinatorial proof, and we discuss whether and how other proof schemes may emerge for students engaging in combinatorial proof. We conclude by discussing implications and avenues for future research.     

An integrable semi-discrete equation and combinatorial numbers with their combinatorial interpretations

A Hankel type determinant solution for an integrable semi-discrete equation is presented. As an application, the relations between the solution and combinatorial numbers are discussed, which lead to new combinatorial numbers. The so-called Motzkin-like numbers are obtained, and the corresponding combinatorial interpretation is given. Additionally, it is also shown that some lattice paths have connections with the special solution.     

Combinatorial 3-manifolds with few vertices

It is proved that every combinatorial 3-manifold with at most eight vertices is a combinatorial sphere.     

Approximations and Randomization to Boost CSP Techniques

In recent years we have seen an increasing interest in combining constraint satisfaction problem (CSP) formulations and linear programming (LP) based techniques for solving hard computational problems. While considerable progress has been made in the integration of these techniques for solving problems that exhibit a mixture of linear and combinatorial constraints, it has been surprisingly difficult to successfully integrate LP-based and CSP-based methods in a purely combinatorial setting. Our approach draws on recent results on approximation algorithms based on LP relaxations and randomized rounding techniques, with theoretical guarantees, as well on results that provide evidence that the runtime distributions of combinatorial search methods are often heavy-tailed. We propose a complete randomized backtrack search method for combinatorial problems that tightly couples CSP propagation techniques with randomized LP-based approximations. We present experimental results that show that our hybrid CSP/LP backtrack search method outperforms the pure CSP and pure LP strategies on instances of a hard combinatorial problem.     

Combinatorial Interpretations for Identities Using Chromatic Partitions

Czechoslovak Mathematical Journal - We provide combinatorial interpretations for three new classes of partitions, the so-called chromatic partitions. Using only combinatorial arguments, we show...     

A Description of the Resonance Variety of a Line Combinatorics via Combinatorial Pencils

In this paper we study the resonance variety of a line combinatorics. We introduce the concept of combinatorial pencil, which characterizes the components of this variety and their dimensions. The main theorem in this paper states that there is a correspondence between components of the resonance variety and combinatorial pencils. As a consequence, we conclude that the depth of a component of the resonance variety is determined by its dimension; and that there are no embedded components. This result is useful to study the isomorphisms between fundamental groups of the complements of line arrangements with the same combinatorial type. The definition of combinatorial pencil generalizes the idea of net given by Yuzvinsky and others.     

布尔矩阵的组合合成及其图表示

本文综术了有关布尔矩阵的组合合成的现有结果,用图论方法展示了它们的组合性质,提出了一些待解决的问题。