Combinatorial families enumerated by quasi-polynomials

We say that the sequence (an) is quasi-polynomial in n if there exist polynomials P₀,…,Ps−1 and an integer n₀ such that, for all n?n₀, an=Pi(n) where . We present several families of combinatorial objects with the following properties: Each family of objects depends on two or more parameters, and the number of isomorphism types of objects is quasi-polynomial in one of the parameters whenever the values of the remaining parameters are fixed to arbitrary constants. For each family we are able to translate the problem of counting isomorphism types of objects into the problem of counting integer points in a union of parametrized rational polytopes. The families of objects to which this approach is applicable include combinatorial designs, linear and unrestricted codes, and dissections of regular polygons.     

Partitions weighted by the parity of the crank

The ‘crank’ is a partition statistic which originally arose to give combinatorial interpretations for Ramanujan's famous partition congruences. In this paper, we establish an asymptotic formula and a family of Ramanujan type congruences satisfied by the number of partitions of n with even crank Me(n) minus the number of partitions of n with odd crank Mo(n). We also discuss the combinatorial implications of q-series identities involving Me(n)−Mo(n). Finally, we determine the exact values of Me(n)−Mo(n) in the case of partitions into distinct parts. These values are at most two, and zero for infinitely many n.     

Solving necklace constraint problems

Some constraint problems have a combinatorial structure where the constraints allow the sequence of variables to be rotated (necklaces), if not also the domain values to be permuted (unlabelled necklaces), without getting an essentially different solution. We bring together the fields of combinatorial enumeration, where efficient algorithms have been designed for (special cases of) some of these combinatorial objects, and constraint programming, where the requisite symmetry breaking has at best been done statically so far. We design the first search procedure and identify the first symmetry-breaking constraints for the general case of unlabelled necklaces. Further, we compare dynamic and static symmetry breaking on real-life scheduling problems featuring (unlabelled) necklaces.     

The primitive Boolean matrices with the second largest scrambling index by Boolean rank

The scrambling index of an n × n primitive Boolean matrix A is the smallest positive integer k such that A ^k (A ^T) ^k = J, where A ^T denotes the transpose of A and J denotes the n×n all ones matrix. For an m×n Boolean matrix M, its Boolean rank b(M) is the smallest positive integer b such that M = AB for some m × b Boolean matrix A and b×n Boolean matrix B. In 2009, M. Akelbek, S. Fital, and J. Shen gave an upper bound on the scrambling index of an n×n primitive matrix M in terms of its Boolean rank b(M), and they also characterized all primitive matrices that achieve the upper bound. In this paper, we characterize primitive Boolean matrices that achieve the second largest scrambling index in terms of their Boolean rank.     

Bijective linear maps on semimodules spanned by Boolean matrices of fixed rank

Let M_m,n(B) be the semimodule of all m×n Boolean matrices where B is the Boolean algebra with two elements. Let k be a positive integer such that 2?k?min(m,n). Let B(m,n,k) denote the subsemimodule of M_m,n(B) spanned by the set of all rank k matrices. We show that if T is a bijective linear mapping on B(m,n,k), then there exist permutation matrices P and Q such that T(A)=PAQ for all A∈B(m,n,k) or m=n and T(A)=PA^tQ for all A∈B(m,n,k). This result follows from a more general theorem we prove concerning the structure of linear mappings on B(m,n,k) that preserve both the weight of each matrix and rank one matrices of weight k². Here the weight of a Boolean matrix is the number of its nonzero entries.     

Boolean formulae, hypergraphs and combinatorial topology

With a view toward studying the homotopy type of spaces of Boolean formulae, we introduce a simplicial complex, called the theta complex, associated to any hypergraph, which is the Alexander dual of the more well-known independence complex. In particular, the set of satisfiable formulae in k-conjunctive normal form with ?n variables has the homotopy type of Θ(Cube(n,n−k)), where Cube(n,n−k) is a hypergraph associated to the (n−k)-skeleton of an n-cube. We make partial progress in calculating the homotopy type of theta for these cubical hypergraphs, and we also give calculations and examples for other hypergraphs as well. Indeed studying the theta complex of hypergraphs is an interesting problem in its own right.     

A method of constructing Krall's polynomials

We propose a method of constructing orthogonal polynomials P_n(x) (Krall's polynomials) that are eigenfunctions of higher-order differential operators. Using this method we show that recurrence coefficients of Krall's polynomials P_n(x) are rational functions of n. Let P_n^(a,b;M)(x) be polynomials obtained from the Jacobi polynomials P_n^(a,b)(x) by the following procedure. We add an arbitrary concentrated mass M at the endpoint of the orthogonality interval with respect to the weight function of the ordinary Jacobi polynomials. We find necessary conditions for the parameters a,b in order for the polynomials P_n^(a,b;M)(x) to obey a higher-order differential equation. The main result of the paper is the following. Let a be a positive integer and b⩾−1/2 an arbitrary real parameter. Then the polynomials P_n^(a,b;M)(x) are Krall's polynomials satisfying a differential equation of order 2a+4.     

Positive Quaternion Kähler Manifolds with fourth Betti number equal to one

Positive Quaternion Kähler Manifolds are Riemannian manifolds with holonomy contained in Sp(n)Sp(1) and with positive scalar curvature. Conjecturally, they are symmetric spaces. In this article we are mainly concerned with Positive Quaternion Kähler Manifolds M satisfying b₄(M)=1. Generalising a result of Galicki and Salamon we prove that M4n in this case is homothetic to a quaternionic projective space if 2≠n?6.     

Recurrence relations based on minimization

This paper investigates solutions of the general recurrence M(0) = g(0), M(n + 1) = g(n + 1) + min_0?k?n(αM(k) + βM(n ? k)) for various choices of α, β, and g(n). In a large number of cases it is possible to prove that M(n) is a convex function whose values can be computed much more efficiently than would be suggested by the defining recurrence. The asymptotic behavior of M(n) can be deduced using combinatorial methods in conjunction with analytic techniques. In some cases there are strong connections between M(n) and the function H(x) defined by $\text{H(x) = 1}\text{for}\text{x < 1, H(x) = H(}\text{(x ? 1)}\text{α}\text{) + H(}\text{(x ? 1)}\text{β}\text{)}\text{for}\text{x ? 1}$. Special cases of these recurrences lead to a surprising number of interesting problems involving both discrete and continuous mathematics.     

The isomorphism classes of the generalized Petersen graphs

In earlier work involving cycles in Generalized Petersen Graphs, we noticed some unexpected instances of P(m,k)≅P(m,l). In this article, all such instances are characterized. A formula is presented for the number of isomorphism classes of P(m,k).     

Density condensation of Boolean formulas

The following problem is considered: given a Boolean formula f, generate another formula g such that: (i) If f is unsatisfiable then g is also unsatisfiable. (ii) If f is satisfiable then g is also satisfiable and furthermore g is “easier” than f. For the measure of this easiness, we use the density of a formula f which is defined as (the number of satisfying assignments)/2ⁿ, where n is the number of Boolean variables of f. In this paper, we mainly consider the case that the input formula f is given as a 3-CNF formula and the output formula g may be any formula using Boolean AND, OR and negation. Two different approaches to this problem are presented: one is to obtain g by reducing the number of variables and the other by increasing the number of variables, both of which are based on existing SAT algorithms. Our performance evaluation shows that, a little surprisingly, better SAT algorithms do not always give us better density-condensation algorithms.     

On the number of distinct multinomial coefficients

We study M(n), the number of distinct values taken by multinomial coefficients with upper entry n, and some closely related sequences. We show that both pP(n)/M(n) and M(n)/p(n) tend to zero as n goes to infinity, where pP(n) is the number of partitions of n into primes and p(n) is the total number of partitions of n. To use methods from commutative algebra, we encode partitions and multinomial coefficients as monomials.     

Maximum nullity of outerplanar graphs and the path cover number

Let G=(V,E) be a graph with V={1,2,…,n}. Define S(G) as the set of all n×n real-valued symmetric matrices A=[a_ij] with a_ij≠0,i≠j if and only if ij∈E. By M(G) we denote the largest possible nullity of any matrix A∈S(G). The path cover number of a graph G, denoted P(G), is the minimum number of vertex disjoint paths occurring as induced subgraphs of G which cover all the vertices of G.There has been some success with relating the path cover number of a graph to its maximum nullity. Johnson and Duarte [5], have shown that for a tree T,M(T)=P(T). Barioli et al. [2], show that for a unicyclic graph G,M(G)=P(G) or M(G)=P(G)-1. Notice that both families of graphs are outerplanar. We show that for any outerplanar graph G,M(G)?P(G). Further we show that for any partial 2-path G,M(G)=P(G).     

The parity of the number of quasigroups

Let I(n) be the number of isomorphism classes of quasigroups of order n. Despite prior enumerations showing that I(n) is odd for 1≤n≤11, we find that I(12) is even. We also give a method for finding the parity of I(n), which we use to show that I(n) is odd for n∈{13,14,15,16,17,19,21}.     

A bound on the scrambling index of a primitive matrix using Boolean rank

The scrambling index of an n×n primitive matrix A is the smallest positive integer k such that A^k(A^t)^k=J, where A^t denotes the transpose of A and J denotes the n×n all ones matrix. For an m×n Boolean matrix M, its Boolean rank b(M) is the smallest positive integer b such that M=AB for some m×b Boolean matrix A and b×n Boolean matrix B. In this paper, we give an upper bound on the scrambling index of an n×n primitive matrix M in terms of its Boolean rank b(M). Furthermore we characterize all primitive matrices that achieve the upper bound.     

The determinants of certain matrices arising from the Boolean lattice

Let B be the Boolean lattice on an n-set with B=?B_i the rank decomposition. Let M(n,i) be the incidence matrix between B_i and B_n−i. We obtain a recursive formula for the determinant of the matrix M(n,i).     

On the polynomial of a path

Let A(P_n) be the adjacency matrix of the path on n vertices. Suppose that r(λ) is a polynomial of degree less than n, and consider the matrix M = r(A>/(P_n)). We determine all polynomials for which M is the adjacency matrix of a graph.     

Hua operators and Poisson transform for bounded symmetric domains

Let Ω be a bounded symmetric domain of non-tube type in Cn with rank r and S its Shilov boundary. We consider the Poisson transform Psf(z) for a hyperfunction f on S defined by the Poisson kernel Ps(z,u)=s(h(z,z)^n/r/²|h(z,u)^n/r|), (z,u)×Ω×S, s∈C. For all s satisfying certain non-integral condition we find a necessary and sufficient condition for the functions in the image of the Poisson transform in terms of Hua operators. When Ω is the type I matrix domain in Mn,m(C) (n?m), we prove that an eigenvalue equation for the second order Mn,n-valued Hua operator characterizes the image.     

Monomorphisms and epimorphisms in pro-categories

A morphism of a category which is simultaneously an epimorphism and a monomorphism is called a bimorphism. We give characterizations of monomorphisms (respectively, epimorphisms) in pro-category pro-C, provided C has direct sums (respectively, pushouts).Let E(C) (respectively, M(C)) be the subcategory of C whose morphisms are epimorphisms (respectively, monomorphisms) of C. We give conditions in some categories C for an object X of pro-C to be isomorphic to an object of pro-E(C) (respectively, pro-M(C)).A related class of objects of pro-C consists of X such that there is an epimorphism X→P∈Ob(C) (respectively, a monomorphism P∈Ob(C)→X). Characterizing those objects involves conditions analogous (respectively, dual) to the Mittag-Leffler property. One should expect that the object belonging to both classes ought to be stable. It is so in the case of pro-groups. The natural environment to discuss those questions are balanced categories with epimorphic images. The last part of the paper deals with that question in pro-homotopy.     

Some inverse results for Hill's equation

We consider Hill's equation y″+(λ−q)y=0 where q∈L¹[0,π]. We show that if l_n—the length of the n-th instability interval—is of order O(n^−(k+2)) then the real Fourier coefficients a_n^k,b_n^k of q^(k)—k-th derivative of q—are of order O(n⁻²), which implies that q^(k) is absolutely continuous almost everywhere for k=0,1,2,….