A type-B associahedron

The (type-A) associahedron is a polytope related to polygon dissections which arises in several mathematical subjects. We propose a B-analogue of the associahedron. Our original motivation was to extend the analogies between type-A and type-B noncrossing partitions, by exhibiting a simplicial polytope whose h-vector is given by the rank-sizes of the type-B noncrossing partition lattice, just as the h-vector of the (simplicial type-A) associahedron is given by the Narayana numbers. The desired polytope Q^B_n is constructed via stellar subdivisions of a simplex, similarly to Lee's construction of the associahedron. As in the case of the (type-A) associahedron, the faces of Q^B_n can be described in terms of dissections of a convex polygon, and the f-vector can be computed from lattice path enumeration. Properties of the simple dual $\text{Q}{}^{\mathrm{<mtext>B</mtext><mtext>1</mtext>}}{}_{\mathrm{n}}$ are also discussed and the construction of a space tessellated by $\text{Q}{}^{\mathrm{<mtext>B</mtext><mtext>1</mtext>}}{}_{\mathrm{n}}$ is given. Additional analogies and relations with type A and further questions are also discussed.     

Classifying smooth lattice polytopes via toric fibrations

We show that any smooth Q-normal lattice polytope P of dimension n and degree d is a strict Cayley polytope if n?2d+1. This gives a sharp answer, for this class of polytopes, to a question raised by V.V. Batyrev and B. Nill.     

A composition for matroids

The composition of a quotient matroid Q over a collection of component matroids f₁, …, f_n indexed on the cells of Q, is described. This composition, called quotient composition, may be viewed as an application of clutter composition to matroids, or as a generalization of matroid direct sum composition to the next higher connectivity. It may also be viewed as equivalent to compositions described by Minty in 1966, and Brylawski in 1971.Quotient composition is characterized, and the circuits and rank function of a composed matroid are given. Various other properties are described, along with a category for quotient composition.     

Colorful polytopes and graphs

The paper investigates connections between abstract polytopes and properly edge colored graphs. Given any finite n-edge-colored n-regular graph G, we associate to G a simple abstract polytope P _G of rank n, the colorful polytope of G, with 1-skeleton isomorphic to G. We investigate the interplay between the geometric, combinatorial, or algebraic properties of the polytope P _G and the combinatorial or algebraic structure of the underlying graph G, focussing in particular on aspects of symmetry. Several such families of colorful polytopes are studied including examples derived from a Cayley graph, in particular the graphicahedra, as well as the flagadjacency polytopes and related monodromy polytopes associated with a given abstract polytope. The duals of certain families of colorful polytopes have been important in the topological study of colored triangulations and crystallization of manifolds.     

Permanental Polytopes of Doubly Stochastic Matrices

A subpolytope Γ of the polytope Ω_n of all n×n nonnegative doubly stochastic matrices is said to be a permanental polytope if the permanent function is constant on Γ. Geometrical properties of permanental polytopes are investigated. No matrix of the form 1⊕A where A is in Ω₂ is contained in any permanental polytope of Ω₃ with positive dimension. There is no 3-dimensional permanental polytope of Ω₃, and there is essentially a unique maximal 2-dimensional permanental polytope of Ω₃ (a square of side $\text{1}\text{3}$). Permanental polytopes of dimension $\text{(n}{}^2\text{?3n+4)}\text{2}$ are exhibited for each n?4.     

An Adjacency Criterion for Coxeter Matroids

A Coxeter matroid is a generalization of matroid, ordinary matroid being the case corresponding to the family of Coxeter groups A _n , which are isomorphic to the symmetric groups. A basic result in the subject is a geometric characterization of Coxeter matroid in terms of the matroid polytope, a result first stated by Gelfand and Serganova. This paper concerns properties of the matroid polytope. In particular, a criterion is given for adjacency of vertices in the matroid polytope.     

On convergence analysis of space homeomorphisms

Various theorems on convergence of general spatial homeomorphisms are proved and, on this basis, theorems on convergence and compactness for classes of the so-called ring Q-homeomorphisms are obtained. In particular, it is established that a family of all ring Q-homeomorphisms f in ? ⁿ fixing two points is compact provided that the function Q is of finite mean oscillation. The corresponding applications have been given to mappings in the Sobolev classes W _loc ^1,p for the case p > n ? 1.     

A theorem about antiprisms

Let P be a polytope in Rⁿ containing the origin in its interior, and let P¹ be the algebraic dual polytope of P. Let Q ? Rⁿ×[0,1] be the (n+1)-dimensional polytope that is the convex hull of P×{1} and P¹×{0}. For each face F of P, let Q(F) denote the convex hull of F×{1} and F¹×{0}, where F¹ is the dual face of P¹. Then Q is an antiprism if the set of facets of Q is precisely the collection {Q (F)} for all faces F of P. If Q is an antiprism, the correspondence between primal and dual faces of P and P¹ is manifested in the facets of Q. In this paper, necessary and sufficient conditions for the existence of antiprisms are stated and proved.     

The complexity of assigning genotypes to people in a pedigree consistently

We discuss the complexity of a combinatorial problem in the field of genetics, which we call Genotype ASsignability problem and abbreviate as GAS. A pair of genes at a position on a pair of chromosomes is called a genotype. GAS is defined as follows: “A pedigree is given and, for one of positions where genotypes are located in a set of pairs of chromosomes of a person, the genotypes at the position of some people in the pedigree are given. Is it possible to assign all other people (i.e., all of the people of which the genotypes are not given) genotypes for the position so as not to cause inconsistency in the heredity of genotypes at the position in the whole of the pedigree?” GAS can be used to compute, from the genotypes at the same position of some people in a pedigree, the genotypes that each person in the pedigree can possess at the position. Although many combinatorial problems have been studied so far, GAS seems not to have been done yet. Let m be the number of different genes in a pedigree and n that of people in the pedigree. We prove that GAS is NP-complete when m?3 and that it can be solved in linear time O(n) when m=2.     

Minkowski Length of 3D Lattice Polytopes

We study the Minkowski length L(P) of a lattice polytope P, which is defined to be the largest number of non-trivial primitive segments whose Minkowski sum lies in P. The Minkowski length represents the largest possible number of factors in a factorization of polynomials with exponent vectors in P, and shows up in lower bounds for the minimum distance of toric codes. In this paper we give a polytime algorithm for computing L(P) where P is a 3D lattice polytope. We next study 3D lattice polytopes of Minkowski length 1. In particular, we show that if Q, a subpolytope of P, is the Minkowski sum of L=L(P) lattice polytopes Q _i , each of Minkowski length 1, then the total number of interior lattice points of the polytopes Q ₁,??,Q _L is at most 4. Both results extend previously known results for lattice polygons. Our methods differ substantially from those used in the two-dimensional case.     

On the immersion of digraphs in cubes

We consider some problems concerning generalizations of embeddings of acyclic digraphs inton-dimensional dicubes. In particular, we define an injectioni from a digraphD into then-dimensional dicubeQ _n to be animmersion if for any two elementsa andb inD there is a directed path inD froma tob iff there is a directed path inQ _n fromi(a) toi(b). We further define the immersion to bestrong iff there is a way of choosing these paths so that paths inQ _n corresponding to arcs inD have disjoint interiors, and we introduce a natural notion of “minimality” on the set of arcs of a digraph in terms of its paths. Our main theorem then becomes:Every (minimal) n-element acyclic digraph can be (strongly) immersed in Q _n. We also present examples ofn-element digraphs which cannot be immersed inQ _n?1 and examples of 9n-element non-minimal digraphs which cannot be strongly immersed inQ10n _?1. We conclude with some applications.     

On the Skeleton of the Polytope of Pyramidal Tours

We consider the skeleton of the polytope of pyramidal tours. A Hamiltonian tour is called pyramidal if the salesperson starts in city 1, then visits some cities in increasing order of their numbers, reaches city n, and returns to city 1 visiting the remaining cities in decreasing order. The polytope PYR(n) is defined as the convex hull of the characteristic vectors of all pyramidal tours in the complete graph K _n . The skeleton of PYR(n) is the graph whose vertex set is the vertex set of PYR(n) and the edge set is the set of geometric edges or one-dimensional faces of PYR(n). We describe the necessary and sufficient condition for the adjacency of vertices of the polytope PYR(n). On this basis we developed an algorithm to check the vertex adjacency with linear complexity. We establish that the diameter of the skeleton of PYR(n) equals 2, and the asymptotically exact estimate of the clique number of the skeleton of PYR(n) is Θ(n²). It is known that this value characterizes the time complexity in a broad class of algorithms based on linear comparisons.     

On maximal and minimal elements of partially ordered sets of Boolean degrees

The paper addresses the “weakest” algorithmic reducibility—Boolean reducibility. Under study are the partially ordered sets of Boolean degrees L _Q corresponding to the various closed classes of Boolean functions Q. The set L _Q is shown to have no maximal elements for many closed classes Q. Some examples are given of a sufficiently large classes Q for which L _Q contains continuum many maximal elements. It is found that the sets of degrees corresponding to the closed classes T ₀₁ and SM contain continuum many minimal elements.     

Deflating quadratic matrix polynomials with structure preserving transformations

Given a pair of distinct eigenvalues (λ₁,λ₂) of an n×n quadratic matrix polynomial Q(λ) with nonsingular leading coefficient and their corresponding eigenvectors, we show how to transform Q(λ) into a quadratic of the form having the same eigenvalue s as Q(λ), with Q_d(λ) an (n-1)×(n-1) quadratic matrix polynomial and q(λ) a scalar quadratic polynomial with roots λ₁ and λ₂. This block diagonalization cannot be achieved by a similarity transformation applied directly to Q(λ) unless the eigenvectors corresponding to λ₁ and λ₂ are parallel. We identify conditions under which we can construct a family of 2n×2n elementary similarity transformations that (a) are rank-two modifications of the identity matrix, (b) act on linearizations of Q(λ), (c) preserve the block structure of a large class of block symmetric linearizations of Q(λ), thereby defining new quadratic matrix polynomials Q₁(λ) that have the same eigenvalue s as Q(λ), (d) yield quadratics Q₁(λ) with the property that their eigenvectors associated with λ₁ and λ₂ are parallel and hence can subsequently be deflated by a similarity applied directly to Q₁(λ). This is the first attempt at building elementary transformations that preserve the block structure of widely used linearizations and which have a specific action.     

On squares in Lucas sequences

Let P and Q be non-zero integers. The Lucas sequence {Un(P,Q)} is defined by U₀=0, U₁=1, Un=PUn−1−QUn−2 (n?2). The question of when Un(P,Q) can be a perfect square has generated interest in the literature. We show that for n=2,…,7, Un is a square for infinitely many pairs (P,Q) with gcd(P,Q)=1; further, for n=8,…,12, the only non-degenerate sequences where gcd(P,Q)=1 and Un(P,Q)=□, are given by U₈(1,−4)=²¹², U₈(4,−17)=⁶²⁰², and U₁₂(1,−1)=¹²².     

A Characterization of L-orthogonal Polynomials from?Three Term Recurrence Relations

We consider the sequence of polynomials {Q _n } satisfying the L-orthogonality ?[z ^?n+m Q _n (z)]=0, 0??m??n?1, with respect to a linear functional ? for which the moments ?[t ⁿ ]=?? _n are all complex. Under certain restriction on the moment functional these polynomials also satisfy a three term recurrence relation. We consider three special classes of such moment functionals and characterize them in terms of the coefficients of the associated three term recurrence relations. Relations between the polynomials {Q _n } associated with two of these special classes of moment functionals are also given. Examples are provided to justify this characterization.     

A Lagrangian relaxation approach to the edge-weighted clique problem

The b-clique polytope CPⁿ_b is the convex hull of the node and edge incidence vectors of all subcliques of size at most b of a complete graph on n nodes. Including the Boolean quadric polytope QPⁿ=CPⁿ_n as a special case and being closely related to the quadratic knapsack polytope, it has received considerable attention in the literature. In particular, the max-cut problem is equivalent with optimizing a linear function over CPⁿ_n. The problem of optimizing linear functions over CPⁿ_b has so far been approached via heuristic combinatorial algorithms and cutting-plane methods.We study the structure of CPⁿ_b in further detail and present a new computational approach to the linear optimization problem based on the idea of integrating cutting planes into a Lagrangian relaxation of an integer programming problem that Balas and Christofides had suggested for the traveling salesman problem. In particular, we show that the separation problem for tree inequalities becomes polynomial in our Lagrangian framework. Finally, computational results are presented.     

Intersecting all edges of convex polytopes by planes

A characterization theorem is given for 3-dimensional convex polytopes Q having the following property: There exists a polytope P, isomorphic to Q, all edges of which can be cut by a pair of planes that miss all its vertices. The result yields an affirmative solution of a conjecture of B. Grünbaum.     

Intriguing Sets of Points of Q(2n, 2) \Q +(2n ? 1, 2)

Intriguing sets of vertices have been studied for several classes of strongly regular graphs. In the present paper, we study intriguing sets for the graphs Γ _n , n ≥ 2, which are defined as follows. Suppose Q(2n, 2), n?≥ 2, is a nonsingular parabolic quadric of PG(2n, 2) and Q ⁺(2n ? 1, 2) is a nonsingular hyperbolic quadric obtained by intersecting Q(2n, 2) with a suitable nontangent hyperplane. Then the collinearity relation of Q(2n, 2) defines a strongly regular graph Γ _n on the set Q(2n, 2) \ Q ⁺(2n ? 1, 2). We describe some classes of intriguing sets of Γ _n and classify all intriguing sets of Γ₂ and Γ₃.