On the truncated assignment polytope

We investigate the convex polytope Ω_m,n(r) which is the convex hull of the m × nr-subpermutation matrices. The faces of Ω_m,n(r) are characterized, and formulae are obtained to compute their dimensions. The faces of Ω_m,n(r) are themselves convex polytopes, and we determine their facets.     

On the structure of the monotone asymmetric travelling salesman polytope I: hypohamiltonian facets

The monotone asymmetric travelling salesman polytope P?ⁿ_T is defined to be the convex hull of the incidence vectors of all hamiltonian circuits and all subsets of these in a complete diagraph of order n. We prove that certain hypohamiltonian diagraphs G=(V,E), i.e. diagraphs which are not hamiltonian but such that G–υ is hamiltonian for all υ?V, induce facets x(E)?n–1 of P?ⁿ_T. This result indicates that P?ⁿ_T has very complicated facets and that it is very unlikely that an explicit complete characterization of P?ⁿ_T can ever be given.     

Computing Hereditary Convex Structures

Color red and blue the n vertices of a convex polytope \(\mathcal{P}\) in ?³. Can we compute the convex hull of each color class in o(nlog?n) time? What if we have more than two colors? What if the colors are random? Consider an arbitrary query halfspace and call the vertices of \(\mathcal{P}\) inside it blue: can the convex hull of the blue points be computed in time linear in their number? More generally, can we quickly compute the blue hull without looking at the whole polytope? This paper considers several instances of hereditary computation and provides new results for them. In particular, we resolve an eight-year old open problem by showing how to split a convex polytope in linear expected time.     

Similarity classes of3 × 3 matrices over a discrete valuation ring

Let Q be a complete discrete valuation ring. Let Π be a prime element in Q. Write P = ΠQ. For n = 1,2,…, letQ_n be the factor ring Q | Pⁿ. Let G = G1₃(Q_n. Denote by M?_n the G-module of 3 × 3 matrices over Q_n modulo scalar matrices. Canonical forms are found for every element in M?_n, and it is shown that there exist five sets of similarity classes. Some results about the general case of NxN matrices over Q also are proved.     

Characterizing filters by convergence (with respect to filters) in Banach spaces

Let X be a topological space and let F be a filter on N, recall that a sequence (xn)_n∈N in X is said to be F-convergent to the point x∈X, if for each neighborhood U of x, {n∈N:xn∈U}∈F. By using F-convergence in ?₁ and in Banach spaces, we characterize the P-filters, the P-filters⁺, the weak P-filters, the Q-filters, the Q-filters⁺, the weak Q-filters, the selective filters and the selective⁺ filters.     

The higher derived functors of the primitive element functor of quasitoric manifolds

Let P be an n-dimensional, q?1 neighborly simple convex polytope and let M2n(λ) be the corresponding quasitoric manifold. The manifold depends on a particular map of lattices λ:Zm→Zn where m is the number of facets of P. In this note we use ESP-sequences in the sense of Larry Smith to show that the higher derived functors of the primitive element functor are independent of λ. Coupling this with results that appear in Bousfield (1970) [3] we are able to enrich the library of nice homology coalgebras by showing that certain families of quasitoric manifolds are nice, at least rationally, from Bousfield?s perspective.     

Simultaneous triangularization of a pair of matrices whose commutator has rank two

Let A,B be n×n matrices with entries in an algebraically closed field F of characteristic zero, and let C=AB?BA. It is shown that if C has rank two and AⁱB^jC^k is nilpotent for 0?i, j?n?1, 1?k?2, then A, B are simultaneously triangularizable over F. An example is given to show that this result is in some sense best possible.     

Some rationally looking faces of Ω n having irrational minimum permanents

Let Ω _n denote the convex polytope consisting of all n × n doubly stochasiic matrices. We determine the minimum permanents which may or may not be rational and the permanent-minimizing matrices over some rationally looking faces of Ω _n We also discuss the barycentricity of the (0, l)-matrices with which we consider the permanent-minimization problem.     

Some inverse problems involving conditional expectations

Let (Ω, F, P) be a probability space, let H be a sub-σ-algebra of F, and let Y be positive and H-measurable with E[Y] = 1. We discuss the structure of the convex set CE(Y; H) = {X ∈ pF: Y = E[X|H]} of random variables whose conditional expectation given H is the prescribed Y. Several characterizations of extreme points of CE(Y; H) are obtained. A necessary and sufficient condition is given in order that CE(Y; H) be the closed, convex hull of its extreme points. For the case of finite F we explicitly calculate the extreme points of CE(Y; H), identify pairs of adjacent extreme points, and characterize extreme points of CE(Y; H) ? CE(Z; G), where G is a second sub-σ-algebra of F and Z ∈ pG. When H = σ(Y) and appropriate topological hypotheses hold, extreme points of CE(Y; H) are shown to be in explicit one-to-one correspondence with certain left inverses of Y. Finally, it is shown how the same approach can be applied to the problem of extremal random measures on $\text{R}$₊ with a prescribed compensator, to deduce that the number of extreme points is zero or one.     

Continuation of separately analytic functions defined on part of the domain boundary

Let D ? ? ⁿ be a domain with smooth boundary ?D, let E??D be a subset of positive Lebesgue measure mes(E) > 0, and let F ? G be a nonpluripolar compact set in a strongly pseudoconvex domain D ? ? ^m . We prove that, under an additional condition, each function separately analytic on the set X = (D × F) ∪ (E × G) has a holomorphic contination to the domain $\rlap{--} X = \{ (z,w) \in D \times G:\omega _{in}^ * (z,E,D) + \omega ^ * (w,F,D) < 1\} $ , where ω* is the P-measure and ω*_in is the interior P-measure.     

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.     

Arrangements in unitary and orthogonal geometry over finite fields

Let V be an n-dimensional vector space over F_q. Let Φ be a Hermitian form with respect to an automorphism σ with σ² = 1. If σ = 1 assume that q is odd. Let $\text{A}$ be the arrangement of hyperplanes of V which are non-isotropic with respect to Φ, and let L be the intersection lattice of $\text{A}$. We prove that the characteristic polynomial of L has n ? v roots 1, q,…, q^{n ? v? 1} where v is the Witt index of Φ.     

The convex hull of degree sequences of signed graphs

As shown in [D. Hoffman, H. Jordon, Signed graph factors and degree sequences, J. Graph Theory 52 (2006) 27-36], the degree sequences of signed graphs can be characterized by a system of linear inequalities. The set of all n-tuples satisfying this system of linear inequalities is a polytope P_n. In this paper, we show that P_n is the convex hull of the set of degree sequences of signed graphs of order n. We also determine many properties of P_n, including a characterization of its vertices. The convex hull of imbalance sequences of digraphs is also investigated using the characterization given in [D. Mubayi, T.G. Will, D.B. West, Realizing degree imbalances of directed graphs, Discrete Math. 239 (2001) 147-153].     

The cut cone III: On the role of triangle facets

The cut polytopeP _n is the convex hull of the incidence vectors of the cuts (i.e. complete bipartite subgraphs) of the complete graph onn nodes. A well known class of facets ofP _n arises from the triangle inequalities:x _ij +x _ik +x _jk ≤ 2 andx _ij -x _ik -x _jk ≤ 0 for 1 ≤i,j, k ≤n. Hence, the metric polytope M_n, defined as the solution set of the triangle inequalities, is a relaxation ofP _n . We consider several properties of geometric type for P_n, in particular, concerning its position withinM _n . Strengthening the known fact ([3]) thatP _n has diameter 1, we show that any set ofk cuts,k ≤ log₂ n, satisfying some additional assumption, determines a simplicial face ofM _n and thus, also, ofP _n . In particular, the collection of low dimension faces ofP _n is contained in that ofM _n . Among a large subclass of the facets ofP _n , the triangle facets are the closest ones to the barycentrum of P_n and we conjecture that this result holds in general. The lattice generated by all even cuts (corresponding to bipartitions of the nodes into sets of even cardinality) is characterized and some additional questions on the links between general facets ofP _n and its triangle facets are mentioned.     

The number of polynomial functions which permute the matrices over a finite field

Let F = GF(q) denote the finite field of order q, and let F_n×n denote the algebra of n × n matrices over F. A function f:F_n×n → F_n×n is called a scalar polynomial function if there exists a polynomial f(x) ?F[x] which represents f when considered as a matrix function under substitution. In this paper a formula is obtained for the number of permutations of F_n×n which are scalar polynomial functions.     

A model of the coNP-complete non-Hamilton tour decision problem for directed graphs

A truncated permutation matrix polytope is defined as the convex hull of a proper subset of n-permutations represented as 0/1 matrices. We present a linear system that models the coNP-complete non-Hamilton tour decision problem based upon constructing the convex hull of a set of truncated permutation matrix polytopes. Define polytope P^n–1 as the convex hull of all n-1 by n-1 permutation matrices. Each extreme point of P^n–1 is placed in correspondence (a bijection) with each Hamilton tour of a complete directed graph on n vertices. Given any n vertex graph G_n, a polynomial sized linear system F⁽ⁿ⁾ is constructed for which the image of its solution set, under an orthogonal projection, is the convex hull of the complete set of extrema of a subset of truncated permutation matrix polytopes, where each extreme point is in correspondence with each Hamilton tour not in G_n. The non-Hamilton tour decision problem is modeled by F⁽ⁿ⁾ such that G_n is non-Hamiltonian if and only if, under an orthogonal projection, the image of the solution set of F⁽ⁿ⁾ is P^n–1. The decision problem Is the projection of the solution set of F⁽ⁿ⁾=P^n–1? is therefore coNP-complete, and this particular model of the non-Hamilton tour problem appears to be new.Dedicated to the 250+ families in Kelowna BC, who lost their homes due to forest fires in 2003.I visited Ted at his home in Kelowna during this time - his family opened their home to evacuees and we shared happy and sad times with many wonderful people.     

Partial linear characterizations of the asymmetric travelling salesman polytope

We consider the linear programming formulation of the asymmetric travelling salesman problem. Several new inequalities are stated which yield a sharper characterization in terms of linear inequalities of the travelling salesman polytope, i.e., the convex hull of tours. In fact, some of the new inequalities as well as some of the well-known subtour elimination constraints are indeed facets of the travelling salesman polytope, i.e., belong to the class of inequalities that uniquely characterize the convex hull of tours to an-city problem.     

On quasigroups rich in associative triples

Let G be a group and $\text{G(1)}$ a quasigroup on the same underlying set. Let dist($\text{G, G(1)}$) denote the number of pairs (x, y) ?G² such that $\text{xy ≠ x 1 y}$. For a finite quasigroup Q, n = card(Q), let t = dist(Q) = min dist(G, Q), where G runs through all groups with the same underlying set, and s = s(Q) the number of non-associative triples. Then 4tn?2t²?24t?s?4tn. If 1 ? s < 3n²/32, then 3tn < s holds as well. Let n ? 168 be an even integer and let σ = min s(Q), where Q runs through all non-associative quasigroups of order n. Then σ = 16n?64.     

Volume approximation of smooth convex bodies by three-polytopes of restricted number of edges

For a given convex body K in \Bbb R³{\Bbb R}^3 with C ² boundary, let P ^c _n be the circumscribed polytope of minimal volume with at most n edges, and let P ⁱ _n be the inscribed polytope of maximal volume with at most n edges. Besides presenting an asymptotic formula for the volume difference as n tends to infinity in both cases, we prove that the typical faces of P ^c _n and P ⁱ _n are asymptotically regular triangles and squares, respectively, in a suitable sense.