Gap inequalities for non-convex mixed-integer quadratic programs

Laurent and Poljak introduced a very general class of valid linear inequalities, called gap inequalities, for the max-cut problem. We show that an analogous class of inequalities can be defined for general non-convex mixed-integer quadratic programs. These inequalities dominate some inequalities arising from a natural semidefinite relaxation.     

A combinatorial classification of 2-regular simple modules for Nakayama algebras

Enomoto showed for finite dimensional algebras that the classification of exact structures on the category of finitely generated projective modules can be reduced to the classification of 2-regular simple modules. In this article, we give a combinatorial classification of 2-regular simple modules for Nakayama algebras and we use this classification to answer several natural questions such as when there is a unique exact structure on the category of finitely generated projective modules for Nakayama algebras. We also classify 1-regular simple modules, quasi-hereditary Nakayama algebras and Nakayama algebras of global dimension at most two. It turns out that most classes are enumerated by well-known combinatorial sequences, such as Fibonacci, Riordan and Narayana numbers. We first obtain interpretations in terms of the Auslander-Reiten quiver of the algebra using homological algebra, and then apply suitable bijections to relate these to combinatorial statistics on Dyck paths.     

Sums of Dilates in Ordered Groups

We address the ‘sums of dilates’ problem by looking for non-trivial lower bounds on sumsets of the form k·X + l·X, where k and l are non-zero integers and X is a subset of a possibly non-abelian group G (written additively). In particular, we investigate the extension of some results so far known only for the integers to the context of torsion-free or linearly orderable groups, either abelian or not.     

A combinatorial rule for (co)minuscule Schubert calculus

We prove a root system uniform, concise combinatorial rule for Schubert calculus of minuscule and cominuscule flag manifolds G/P (the latter are also known as compact Hermitian symmetric spaces). We connect this geometry to the poset combinatorics of Proctor, thereby giving a generalization of Schützenberger's jeu de taquin formulation of the Littlewood-Richardson rule that computes the intersection numbers of Grassmannian Schubert varieties. Our proof introduces cominuscule recursions, a general technique to relate the numbers for different Lie types.     

Testing cut generators for mixed-integer linear programming

In this paper, a methodology for testing the accuracy and strength of cut generators for mixed-integer linear programming is presented. The procedure amounts to random diving towards a feasible solution, recording several kinds of failures. This allows for a ranking of the accuracy of the generators. Then, for generators deemed to have similar accuracy, statistical tests are performed to compare their relative strength. An application on eight Gomory cut generators and six Reduce-and-Split cut generators is given. The problem of constructing benchmark instances for which feasible solutions can be obtained is also addressed. Supported by ONR grant N00014-09-1-0033.     

On types of growth for graph-different permutations

We consider an infinite graph G whose vertex set is the set of natural numbers and adjacency depends solely on the difference between vertices. We study the largest cardinality of a set of permutations of [n] any pair of which differ somewhere in a pair of adjacent vertices of G and determine it completely in an interesting special case. We give estimates for other cases and compare the results in case of complementary graphs. We also explore the close relationship between our problem and the concept of Shannon capacity “within a given type.”     

Immeubles de Kac–Moody hyperboliques, groupes non isomorphes de même immeuble (Hyperbolic Kac–Moody Buildings Nonisomorphic Groups with the Same Building)

We first remark that Kac–Moody groups enable us to produce hyperbolic buildings – automatically endowed with nonuniform lattices. The main result then deals with groups whose buildings are trees or two-dimensional hyperbolic. It is a factorization theorem for abstract isomorphisms. It shows the existence of nonisomorphic Kac–Moody groups with the same associated isomorphism class of buildings.