Higher Dimensional Moore Bounds

Upper bounds on the face numbers of simplicial complexes are proven in terms on their girths, in analogy with the Moore bound from graph theory. Our definition of girth generalizes the usual definition for graphs.     

Properties of Groups for the Cage and Degree/Diameter Problems

A (k, g)-cage is a k-regular graph of girth g of minimum order. While many of the best known constructions of small k-regular graphs of girth g are known to be Cayley graphs, no general theory of the relation between the girth of a Cayley graph and the structure of the underlying group has been developed. We attempt to fill the gap by focusing on the girths of Caley graphs of nilpotent and solvable groups, and present a series of results supporting the intuitive idea that the closer a group is to being abelian, the less suitable it is for constructing Cayley graphs of large girths. Specifically, we establish the existence of upper bounds on the girths of Cayley graphs with respect to the nilpotency class and/or the length of the derived sequence of the underlying groups.     

Noncommuting graphs of matrices over semirings

We study diameters and girths of noncommuting graphs of semirings. For a noncommutative semiring that is either multiplicatively or additively cancellative, we find the diameter and the girth of its noncommuting graph and prove that it is Hamiltonian. Moreover, we find diameters and girths of noncommuting graphs of all nilpotent matrices over a semiring, all invertible matrices over a semiring, all noninvertible matrices over a semiring, and the full matrix semiring. In nearly all cases we prove that diameters are less than or equal to 2 and girths are less than or equal to 3, except in the case of 2×2 nilpotent matrices.     

Enriched homology and cohomology modules of simiplicial complexes

For a simplicial complex Δ on {1, 2,…, n} we define enriched homology and cohomology modules. They are graded modules over k[x ₁,…, x _n ] whose ranks are equal to the dimensions of the reduced homology and cohomology groups. We characterize Cohen-Macaulay, l-Cohen-Macaulay, Buchsbaum, and Gorenstein^* complexes Δ, and also orientable homology manifolds in terms of the enriched modules. We introduce the notion of girth for simplicial complexes and make a conjecture relating the girth to invariants of the simplicial complex. We also put strong vanishing conditions on the enriched homology modules and describe the simplicial complexes we then get. They are block designs and include Steiner systems S(c, d, n) and cyclic polytopes of even dimension. This paper is to a large extent a complete rewriting of a previous preprint, “Hierarchies of simplicial complexes via the BGG-correspondence”. Also Propositions 1.7 and 3.1 have been generalized to cell complexes in [11].     

The maximum genus of a 3-regular simplicial graph

In this paper, the relationship between non-separating independent number and the maximum genus of a 3-regular simplicial graph is presented. A lower bound on the maximumgenus of a 3-regular graph invalving girth is provided. The lower bound is tight, it improves a bound of Huang and Liu.     

Connectivity of graphs with given girth pair

Girth pairs were introduced by Harary and Kovács [Regular graphs with given girth pair, J. Graph Theory 7 (1983) 209-218]. The odd girth (even girth) of a graph is the length of a shortest odd (even) cycle. Let g denote the smaller of the odd and even girths, and let h denote the larger. Then (g,h) is called the girth pair of the graph. In this paper we prove that a graph with girth pair (g,h) such that g is odd and h?g+3 is even has high (vertex-)connectivity if its diameter is at most h-3. The edge version of all results is also studied.     

New LP bound in multivariate Lipschitz optimization: Theory and applications

Most numerically promising methods for solving multivariate unconstrained Lipschitz optimization problems of dimension greater than two use rectangular or simplicial branch-and-bound techniques with computationally cheap but rather crude lower bounds.Generalizations to constrained problems, however, require additional devices to detect sufficiently many infeasible partition sets. In this article, a new lower bounding procedure is proposed for simplicial methods yielding considerably better bounds at the expense of two linear programs in each iteration. Moreover, the resulting approach can solve easily linearly constrained problems, since in this case infeasible partition sets are automatically detected by the lower bounding procedure.Finally, it is shown that the lower bounds can be further improved when the method is applied to solve systems of inequalities. Implementation issues, numerical experiments, and comparisons are discussed in some detail.The authors are indebted to the Editor-in-Chief of this journal for his valuable suggestions which have considerably improved the final version of this article.     

Regular graphs with given girth pair

The girth pair of a graph gives the length of a shortest odd and a shortest even cycle. The existence of regular graphs with given degree and girth pair is proved and simple bounds for their smallest order are developed. Several infinite classes of such graphs are constructed and it is proved that two of these families consist of smallest graphs.     

Mesh-dependent stability for finite element approximations of parabolic equations with mass lumping

In this paper, based on some mesh-dependent estimates on the extreme eigenvalues of a general finite element system defined on a simplicial mesh, novel and sharp bounds on the permissible time step size are derived for the mass lumping finite element approximations of parabolic equations. The bounds are dependent not only on the mesh size but also on the mesh shape. These results provide guidance to the stability of numerical solutions of parabolic problems in relation to the unstructured geometric meshing. Numerical experiments on both uniform meshes and adaptive meshes are presented to validate the theoretical analysis.     

Mesh-dependent stability for finite element approximations of parabolic equations with mass lumping

In this paper, based on some mesh-dependent estimates on the extreme eigenvalues of a general finite element system defined on a simplicial mesh, novel and sharp bounds on the permissible time step size are derived for the mass lumping finite element approximations of parabolic equations. The bounds are dependent not only on the mesh size but also on the mesh shape. These results provide guidance to the stability of numerical solutions of parabolic problems in relation to the unstructured geometric meshing. Numerical experiments on both uniform meshes and adaptive meshes are presented to validate the theoretical analysis.     

A simplicial homology algorithm for Lipschitz optimisation

The simplicial homology global optimisation (SHGO) algorithm is a general purpose global optimisation algorithm based on applications of simplicial integral homology and combinatorial topology. SHGO approximates the homology groups of a complex built on a hypersurface homeomorphic to a complex on the objective function. This provides both approximations of locally convex subdomains in the search space through Sperner’s lemma and a useful visual tool for characterising and efficiently solving higher dimensional black and grey box optimisation problems. This complex is built up using sampling points within the feasible search space as vertices. The algorithm is specialised in finding all the local minima of an objective function with expensive function evaluations efficiently which is especially suitable to applications such as energy landscape exploration. SHGO was initially developed as an improvement on the topographical global optimisation (TGO) method. It is proven that the SHGO algorithm will always outperform TGO on function evaluations if the objective function is Lipschitz smooth. In this paper SHGO is applied to non-convex problems with linear and box constraints with bounds placed on the variables. Numerical experiments on linearly constrained test problems show that SHGO gives competitive results compared to TGO and the recently developed Lc-DISIMPL algorithm as well as the PSwarm, LGO and DIRECT-L1 algorithms. Furthermore SHGO is compared with the TGO, basinhopping (BH) and differential evolution (DE) global optimisation algorithms over a large selection of black-box problems with bounds placed on the variables from the SciPy benchmarking test suite. A Python implementation of the SHGO and TGO algorithms published under a MIT license can be found from https://bitbucket.org/upiamcompthermo/shgo/.     

On Generalized h -Vectors of Rational Polytopes with a Symmetry of Prime Order

We prove tight lower bounds for the coefficients of the generalized h -vector of a rational polytope with a symmetry of prime order that is fixed-point free on the boundary. These bounds generalize results of Stanley and Adin for the h -vector of a simplicial rational polytope with a central symmetry or a symmetry of prime order, respectively. Received November 6, 1997, and in revised form March 17, 1998.     

Empty Simplices of Polytopes and Graded Betti Numbers

The conjecture of Kalai, Kleinschmidt, and Lee on the number of empty simplices of a simplicial polytope is established by relating it to the first graded Betti numbers of the polytope and applying a result of Migliore and the author. This approach allows us to derive explicit optimal bounds on the number of empty simplices of any given dimension. As a key result, we prove optimal bounds for the graded Betti numbers of any standard graded K-algebra in terms of its Hilbert function.     

Lower bounds for the average genus

Two lower bounds are obtained for the average genus of graphs. The average genus for a graph of maximum valence at most 3 is at least half its maximum genus, and the average genus for a 2-connected simplicial graph other than a cycle is at least 1/16 of its cycle rank. © 1995 John Wiley & Sons, Inc.     

Partitions of Graphs into Cographs

Cographs from the minimal family of graphs containing K₁ which are closed with respect to complements and unions. We discuss vertex partitions of graphs into the smallest number of cographs, where the partition is as small as possible. We shall call the order of such a partition the c-chromatic number of the graph. We begin by axiomatizing several well-known graphical parameters as motivation for this function. We present several bounds on c-chromatic number in terms of well-known expressions. We show that if a graph is triangle-free, then its chromatic number is bounded between the c-chromatic number and twice this number. We show both bounds are sharp, for graphs with arbitrarily high girth. This provides an alternative proof to a result in [3]; there exist triangle-free graphs with arbitrarily large c-chromatic numbers. We show that any planar graph with girth at least 11 has a c-chromatic number of at most two. We close with several remarks on computational complexity. In particular, we show that computing the c-chromatic number is NP-complete for planar graphs.     

On the number of generators in the algebra of continuous functions

It is proven that there are (n+1) generators in the algebra of continuous functions on finite n-dimensional simplicial polyhedra.Translated from Matematicheskie Zametki, Vol. 10, No. 5, pp. 537–540, November, 1971.     

与直径和围长有关的图的最大亏格

利用图的直径和围长来研究图的最大亏格的下界,得到了如下结果：设G是直径为d的简单图,若G的围长不小于d（其中d为不小于3的整数）,则ξ（G）≤2,即γM（G）≥1/2β（G）-1．而且,在这种意义下,所得到的界是最好的．     

On locally constructible spheres and balls

Durhuus and Jonsson (1995) introduced the class of “locally constructible” (LC) 3-spheres and showed that there are only exponentially many combinatorial types of simplicial LC 3-spheres. Such upper bounds are crucial for the convergence of models for 3D quantum gravity.     

Matchings in simplicial complexes, circuits and toric varieties

Using a generalized notion of matching in a simplicial complex and circuits of vector configurations, we compute lower bounds for the minimum number of generators, the binomial arithmetical rank and the A-homogeneous arithmetical rank of a lattice ideal. Prime lattice ideals are toric ideals, i.e. the defining ideals of toric varieties.     

Multiperiod Portfolio Optimization with Terminal Liability: Bounds for the Convex Case

This paper is concerned with an investor trading in multiple securities over many time periods in order to meet an outstanding liability at some future date. The investor is concerned with maximizing the expected profits from portfolio rebalancing under an initial wealth restriction to meet the future liabilities. We formulate the problem as a discrete-time stochastic optimization model and allow asset prices to have continuous probability distributions on compact domains. For the case of Markovian price uncertainty and convex terminal liability, we develop a simplicial approximation, under which bounds on the problem can be computed efficiently. Computations only require evaluating a dynamic programming recursion, which thus, allows its application to problems with a large number of trading periods. The bounds are tight in that they are exact in certain cases. Numerical results are given to demonstrate the computational efficiency of the procedure.