Cyclic branched coverings of some pretzel links

We construct infinite families of closed connected orientable 3-manifolds obtained from certain triangulated 3-cells by pairwise identifications of their boundary faces. Our combinatorial constructions extend and complete a particular polyhedral scheme which Kim and Kostrikin used in [10] and [11] to define a series of spaces denoted M ₃(n). Then we determine geometric presentations of the fundamental groups, and prove that many of the constructed manifolds are n-fold (non-strongly) cyclic coverings of the ³-sphere branched over some specified pretzel links.     

Geometry in Grassmannians and a generalization of the dilogarithm

In this paper we introduce some polyhedra in Grassman manifolds which we call Grassmannian simplices. We study two aspects of these polyhedra: their combinatorial structure (Section 2) and their relation to harmonic differential forms on the Grassmannian (Section 3). Using this we obtain results about some new differential forms, one of which is the classical dilogarithm (Section 1). The results here unite two threads of mathematics that were much studied in the 19th century. The analytic one, concerning the dilogarithm, goes back to Leibnitz (1696) and Euler (1779) and the geometric one, concerning Grassmannian simplices, can be traced to Binet (1811). In Section 4, we give some of this history along with some recent related results and open problems. In Section 0, we give as an introduction an account in geometric terms of the simplest cases.     

Small overlap monoids I: The word problem

We develop a combinatorial approach to the study of semigroups and monoids with finite presentations satisfying small overlap conditions. In contrast to existing geometric methods, our approach facilitates a sequential left–right analysis of words which lends itself to the development of practical, efficient computational algorithms. In particular, we obtain a highly practical linear time solution to the word problem for monoids and semigroups with finite presentations satisfying the condition $C(4)$, and a polynomial time solution to the uniform word problem for presentations satisfying the same condition.     

Geometric and design-theoretic aspects of semibent functions I

The two parts of this paper consider combinatorial and geometric aspects of semibent functions. In the first part of this note we obtain 2-designs from semibent functions and we characterize their automorphism groups. In the second part semibent functions of partial spread type with a linear structure are investigated.     

Type-II matrices and combinatorial structures

Type-II matrices are a class of matrices used by Jones in his work on spin models. In this paper we show that type-II matrices arise naturally in connection with some interesting combinatorial and geometric structures.     

Two geometric representation theorems for separoids

Summary {\it Separoids\/} capture the combinatorial structure which arises from the separations by hyperplanes of a family of convex sets in some Euclidian space. Furthermore, as we prove in this note, every abstract separoid <InlineEquation ID=IE"1"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"2"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"3"><EquationSource Format="TEX"><![CDATA[$]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>S$ can be represented by a family of convex sets in the $(|S|-1)$-dimensional Euclidian space. The {\it geometric dimension\/} of the separoid is the minimum dimension where it can be represented and the upper bound given here is tight. Separoids have also the notions of {\it combinatorial dimension\/} and {\it general position\/} which are purely combinatorial in nature. In this note we also prove that: {\it a separoid in general position can be represented by a family of points if and only if its geometric and combinatorial dimensions coincide\/}.     

The Gallery Length Filling Function and a Geometric Inequality for Filling Length

We exploit duality considerations in the study of singular combinatorial2-discs (diagrams) and are led to the following innovationsconcerning the geometry of the word problem for finite presentationsof groups. We define a filling function called gallery lengththat measures the diameter of the 1-skeleton of the dual ofdiagrams; we show it to be a group invariant and we give upperbounds on the gallery length of combable groups. We use gallerylength to give a new proof of the Double Exponential Theorem.Also we give geometric inequalities relating gallery lengthto the space-complexity filling function known as filling length.2000 Mathematics Subject Classification 20F05 (primary), 20F06,57M05, 57M20 (secondary).     

Deriving compact extended formulations via LP-based separation techniques

The best formulations for some combinatorial optimization problems are integer linear programming models with an exponential number of rows and/or columns, which are solved incrementally by generating missing rows and columns only when needed. As an alternative to row generation, some exponential formulations can be rewritten in a compact extended form, which have only a polynomial number of constraints and a polynomial, although larger, number of variables. As an alternative to column generation, there are compact extended formulations for the dual problems, which lead to compact equivalent primal formulations, again with only a polynomial number of constraints and variables. In this this paper we introduce a tool to derive compact extended formulations and survey many combinatorial optimization problems for which it can be applied. The tool is based on the possibility of formulating the separation procedure by an LP model. It can be seen as one further method to generate compact extended formulations besides other tools of geometric and combinatorial nature present in the literature.     

Small Triangle-Free Configurations of Points and Lines

In the paper we show that all combinatorial triangle-free configurations for v ≤ 18 are geometrically realizable. We also show that there is a unique smallest astral (18₃) triangle-free configuration and its Levi graph is the generalized Petersen graph G(18,5). In addition, we present geometric realizations of the unique flag transitive triangle-free configuration (20₃) and the unique point transitive triangle-free configuration (21₃).     

Some Explanations of Dobinski's Formula

The geometric, algebraic, and combinatorial explanations of Dobinski's formula are presented by mixed volumes of compact convex sets, Möbius inversion, difference operator, and species. The employed method may be useful in proving some other combinatorial identities.     

Isoperimetric inequalities in simplicial complexes

In graph theory there are intimate connections between the expansion properties of a graph and the spectrum of its Laplacian. In this paper we define a notion of combinatorial expansion for simplicial complexes of general dimension, and prove that similar connections exist between the combinatorial expansion of a complex, and the spectrum of the high dimensional Laplacian defined by Eckmann. In particular, we present a Cheeger-type inequality, and a high-dimensional Expander Mixing Lemma. As a corollary, using the work of Pach, we obtain a connection between spectral properties of complexes and Gromov’s notion of geometric overlap. Using the work of Gundert and Wagner, we give an estimate for the combinatorial expansion and geometric overlap of random Linial-Meshulam complexes.     

Realizations of Symmetric Maps by Symmetric Polyhedra

Representations by polyhedra of several regular maps of positive genus are developed. The groups of symmetries of some of these polyhedra are proper subgroups of their groups of combinatorial symmetries, but we show that faithful representations can be obtained if appropriately general polyhedra are admitted. The general definition of polyhedra, which may be useful in other contexts as well, is also discussed, as are some of the reasons for its absence from the literature. Received February 3, 1997, and in revised form August 5, 1997.     

A Stochastic Heuristic for Visualising Graph Clusters in a Bi-Dimensional Space Prior to Partitioning

This paper presents a new stochastic heuristic to reveal some structures inherent in large graphs, by displaying spatially separate clusters of highly connected vertex subsets on a two-dimensional grid. The algorithm employed is inspired by a biological model of ant behavior; it proceeds by local optimisations, and requires neither global criteria, nor any a priori knowledge of the graph. It is presented here as a preliminary phase in a recent approach to graph partitioning problems: transforming the combinatorial problem (minimising edge cuts) into one of clustering by constructing some bijective mapping between the graph vertices and points in some geometric space. After reviewing different embeddings proposed in the literature, we define a dissimilarity coefficient on the vertex set which translates the graph's interesting structural properties into distances on the grid, and incorporate it into the clustering heuristic. The heuristic's performance on a well-known class of pseudo-random graphs is assessed according to several metric and combinatorial criteria.     

Combinatorial realizations of crystals via torus actions on quiver varieties

Let V(λ) be a highest-weight representation of a symmetric Kac–Moody algebra, and let B(λ) be its crystal. There is a geometric realization of B(λ) using Nakajima’s quiver varieties. In many particular cases one can also realize B(λ) by elementary combinatorial methods. Here we study a general method of extracting combinatorial realizations from the geometric picture: we use Morse theory to index the irreducible components by connected components of the subvariety of fixed points for a certain torus action. We then discuss the case of $\widehat{\mathfrak{sl}}_{n}$ , where the fixed point components are just points, and are naturally indexed by multi-partitions. There is some choice in our construction, leading to a family of combinatorial realizations for each highest-weight crystal. In the case of B(Λ ₀) we recover a family of realizations which was recently constructed by Fayers. This gives a more conceptual proof of Fayers’ result as well as a generalization to higher level crystals. We also discuss a relationship with Nakajima’s monomial crystal.     

On cyclic bra nched coverings of torus knots

We prove that then-fold cyclic coverings of the 3-sphere branched over the torus knotsK(p,q), p>q2 (i.e. the Brieskorn manifolds in the sense of [12]) admit spines corresponding to cyclic presentations of groups ifp1 (modq). These presentations include as a very particular case the Sieradski groups, first introduced in [14] and successively obtained from geometric constructions in [4], [9], and [15]. So our main theorem answers in affirmative to an open question suggested by the referee in [14]. Then we discuss a question concerning cyclic presentations of groups and Alexander polynomials of knots.Work Performed under the auspicies of the G.N.S.A.G.A. of the C.N.R. (National Research Council) of Italy and partially supported by the Ministero per la Ricerca Scientifica e Tecnologica of Italy Within the projectsGeometria Reale e Complessa andTopologia and by the Korean Science and Engineering Foundation.     

Weighted Ehrhart theory and orbifold cohomology

We introduce the notion of a weighted δ-vector of a lattice polytope. Although the definition is motivated by motivic integration, we study weighted δ-vectors from a combinatorial perspective. We present a version of Ehrhart Reciprocity and prove a change of variables formula. We deduce a new geometric interpretation of the coefficients of the Ehrhart δ-vector. More specifically, they are sums of dimensions of orbifold cohomology groups of a toric stack.     

Formal specification and proofs for the topology and classification of combinatorial surfaces

We describe one of the first attempts at using modern specification techniques in the field of geometric modeling and computational geometry. Using the Coq system, we developed a formal multi-level specification of combinatorial maps, used to represent subdivisions of geometric manifolds, and then exploited it to formally prove fundamental theorems. In particular, we outline here an original and constructive proof of a combinatorial part of the famous Surface Classification Theorem, based on a set of so-called “conservative” elementary operations on subdivisions.     

恒等式的几何意义及其组合证明

给出G auss系数的定义及其几何意义,对一些G auss系数恒等式给出了组合分析的证明,并且相应地给出它们的几何解释.