Equi-distribution over descent classes of the hyperoctahedral group

A classical result of MacMahon shows that the length function and the major index are equi-distributed over the symmetric group. Foata and Schützenberger gave a remarkable refinement and proved that these parameters are equi-distributed over inverse descent classes, implying bivariate equi-distribution identities. Type B analogues of these results, refinements and consequences are given in this paper.     

Counting irreducible polynomials with prescribed coefficients over a finite field

We continue our study on counting irreducible polynomials over a finite field with prescribed coefficients. We set up a general combinatorial framework using generating functions with coefficients from a group algebra which is generated by equivalence classes of polynomials with prescribed coefficients. Simplified expressions are derived for some special cases. Our results extend some earlier results.     

Counting polynomials over finite fields with prescribed leading coefficients and linear factors

We count the number of polynomials over finite fields with prescribed leading coefficients and a given number of linear factors. This is equivalent to counting codewords in Reed-Solomon codes which are at a certain distance from a received word. We first apply the generating function approach, which is recently developed by the author and collaborators, to derive expressions for the number of monic polynomials with prescribed leading coefficients and linear factors. We then apply Li and Wan's sieve formula to simplify the expressions in some special cases. Our results extend and improve some recent results by Li and Wan, and Zhou, Wang and Wang.     

A polyominoes-permutations injection and tree-like convex polyominoes

Plane polyominoes are edge-connected sets of cells on the orthogonal lattice Z², considered identical if their cell sets are equal up to an integral translation. We introduce a novel injection from the set of polyominoes with n cells to the set of permutations of [n], and classify the families of convex polyominoes and tree-like convex polyominoes as classes of permutations that avoid some sets of forbidden patterns. By analyzing the structure of the respective permutations of the family of tree-like convex polyominoes, we are able to find the generating function of the sequence that enumerates this family, conclude that this sequence satisfies the linear recurrence an=6an−1−14an−2+16an−3−9an−4+2an−5, and compute the closed-form formula an=²n+2−(n³−n²+10n+4)/2.     

Nonnegative matrices with prescribed spectrum and elementary divisors

In this paper we give new sufficient conditions for the existence and construction of nonnegative matrices with prescribed elementary divisors, which drastically improve and contain some of the previous known conditions. We also show how to perturb complex eigenvalues of a nonnegative matrix while keeping its nonnegativity. These results allow us, under certain conditions, to easily decide if a given list is realizable with prescribed elementary divisors.     

Killing graphs with prescribed mean curvature and Riemannian submersions

It is proved the existence and uniqueness of graphs with prescribed mean curvature in Riemannian submersions fibered by flow lines of a vertical Killing vector field.     

Products of two involutions with prescribed eigenvalues and some applications

Let F be a field. In [Djokovic, Product of two involutions, Arch. Math. 18 (1967) 582-584] it was proved that a matrix A∈F^n×n can be written as A=BC, for some involutions B,C∈F^n×n, if and only if A is similar to A^-1. In this paper we describe the possible eigenvalues of the matrices B and C.As a consequence, in case charF≠2, we describe the possible similarity classes of (P₁₁⊕P₂₂)P^-1, when the nonsingular matrix P=[P_ij]∈F^n×n, i,j∈{1,2} and P₁₁∈F^s×s, varies.When F is an algebraically closed field and charF≠2, we also describe the possible similarity classes of [A_ij]∈F^n×n, i,j∈{1,2}, when A₁₁ and A₂₂ are square zero matrices and A₁₂ and A₂₁ vary.     

Posets with large dimension and relatively few critical pairs

The dimension of a poset (partially ordered set)P=(X, P) is the minimum number of linear extensions ofP whose intersection isP. It is also the minimum number of extensions ofP needed to reverse all critical pairs. Since any critical pair is reversed by some extension, the dimensiont never exceeds the number of critical pairsm. This paper analyzes the relationship betweent andm, when 3tmt+2, in terms of induced subposet containment. Ifmt+1 then the poset must containS _t , the standard example of at-dimensional poset. The analysis form=t+2 leads to dimension products and David Kelly's concept of a split. Whent=3 andm=5, the poset must contain eitherS ₃, or the 6-point poset called a chevron, or the chevron's dual. Whent4 andm=t+2, the poset must containS _t , or the dimension product of the Kelly split of a chevron andS _t–3, or the dual of this product.     

Complexity results for reconstructing binary images with disjoint components from horizontal and vertical projections

The problem of reconstructing a special class of binary images from their horizontal and vertical projections is considered. We present a general framework for analyzing the worst case complexity of this task if the image consists of more than one pairwise disjoint component. Applying the presented technique we analyze the complexity of reconstructing canonical hv-convex binary images. We also present parameterized complexity results on general and so-called glued hv-convex images. Moreover, we study how our results are related to the reconstruction of permutation matrices from four projections.     

Vertex-disjoint directed cycles of prescribed length in tournaments with given minimum out-degree and in-degree

In a recent paper, Bessy, Sereni and the author (see [3]) have proved that for r≥1, a tournament with minimum out-degree and in-degree both greater than or equal to 2r−1 contains at least r vertex-disjoint directed triangles. In this paper, we generalize this result; more precisely, we prove that for given integers q≥3 and r≥1, a tournament with minimum out-degree and in-degree both greater than or equal to (q−1)r−1 contains at least r vertex-disjoint directed cycles of length q. We will use an auxiliary result established in [3], concerning a union of sets contained in another union of sets. We finish by giving a lower bound on the maximum number of vertex-disjoint directed cycles of length q when only the minimum out-degree is supposed to be greater than or equal to (q−1)r−1.     

Infinite families of crossing‐critical graphs with prescribed average degree and crossing number

?iráň constructed infinite families of k‐crossing‐critical graphs for every k?3 and Kochol constructed such families of simple graphs for every k?2. Richter and Thomassen argued that, for any given k?1 and r?6, there are only finitely many simple k‐crossing‐critical graphs with minimum degree r. Salazar observed that the same argument implies such a conclusion for simple k‐crossing‐critical graphs of prescribed average degree r>6. He established the existence of infinite families of simple k‐crossing‐critical graphs with any prescribed rational average degree r∈[4, 6) for infinitely many k and asked about their existence for r∈(3, 4). The question was partially settled by Pinontoan and Richter, who answered it positively for $r\in(3\frac{1}{2},4)$. The present contribution uses two new constructions of crossing‐critical simple graphs along with the one developed by Pinontoan and Richter to unify these results and to answer Salazar's question by the following statement: there exist infinite families of simple k‐crossing‐critical graphs with any prescribed average degree r∈(3, 6), for any k greater than some lower bound N_r. Moreover, a universal lower bound N_I on k applies for rational numbers in any closed interval I?(3, 6). © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 139–162, 2010     

关于具分形边界连通区域上的谱渐近及弱Weyl-Berry猜想

本文研究了连通分形鼓上的谱渐近，对满足“切口”条件的连通分形鼓以及一类自然连通的分形鼓，分别证明了弱Weyl－Berry猜想是成立的.     

Explicitly given pairs of dual frames with compactly supported generators and applications to irregular B-splines

We consider systems of functions appearing by letting a class of modulations act on a countable collection of functions. These systems correspond to shift-invariant systems, considered on the Fourier side. We provide sufficient conditions for the system to be a frame, as well as an explicit construction of a class of frames and associated duals. We use the result to construct frames based on B-splines with knot sequences satisfying a natural condition, as well as explicitly given duals.     

K4‐free graphs with no odd hole: Even pairs and the circular chromatic number

An odd hole in a graph is an induced cycle of odd length at least five. In this article we show that every imperfect K₄‐free graph with no odd hole either is one of two basic graphs, or has an even pair or a clique cutset. We use this result to show that every K₄‐free graph with no odd hole has circular chromatic number strictly smaller than 4. We also exhibit a sequence {H_n} of such graphs with lim_n→∞χ_c(H_n)=4. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 303–322, 2010     

Existence and exponential stability in Lr‐spaces of stationary Navier–Stokes flows with prescribed flux in infinite cylindrical domains

We prove existence, uniqueness and exponential stability of stationary Navier–Stokes flows with prescribed flux in an unbounded cylinder of ?ⁿ,n?3, with several exits to infinity provided the total flux and external force are sufficiently small. The proofs are based on analytic semigroup theory, perturbation theory and L^r ? L^q‐estimates of a perturbation of the Stokes operator in L^q‐spaces. Copyright © 2006 John Wiley & Sons, Ltd.