Harmonic Analysis on SO (n, ℂ)/SO (n−1, ℂ), n≥3

In this article we compute the Plancherel measure for SO(n, ℂ)/SO(n − 1, ℂ) following the approach of Van den Ban. This result is required in order to calculate the explicit decomposition of the oscillator representation wn for the dual pair G = SL(2, ℂ) × SO(n, ℂ) and to prove that every wn(G)-invariant Hilbert subspace of the space of tempered distributions decomposes multiplicity free.     

Homology of balanced complexes via the Fourier transform

Let G ₀,…,G _k be finite abelian groups, and let G ₀∗⋯∗G _k be the join of the 0-dimensional complexes G _i . We give a characterization of the integral k-coboundaries of subcomplexes of G ₀∗⋯∗G _k in terms of the Fourier transform on the group G ₀×⋯×G _k . This provides a short proof of an extension of a recent result of Musiker and Reiner on a topological interpretation of the cyclotomic polynomial.     

The smallest degree sum that yields potentially Kr,r-graphic sequences

We consider a variation of a classical Turán-type extremal problem as follows: Determine the smallest even integer σ(K_r,r,n) such that every n-term graphic sequence π = (d₁,d₂,...,d_n) with term sum σ(π) = d₁ + d₂ + ... + d_n ≥ σ(K_r,r,n) is potentially K_r,r-graphic, where K_r,r is an r × r complete bipartite graph, i.e. π has a realization G containing K_r,r as its subgraph. In this paper, the values σ(K_r,r,n) for even r and n ≥ 4r² - r - 6 and for odd r and n ≥ 4r² + 3r - 8 are determined.     

On Optimal Orientations of Cartesian Products of Trees

. Let d(D) (resp., d(G)) denote the diameter and r(D) (resp., r(G)) the radius of a digraph D (resp., graph G). Let G×H denote the cartesian product of two graphs G and H. An orientation D of G is said to be (r, d)-invariant if r(D)=r(G) and d(D)=d(G). Let {T _i }, i=1,…,n, where n≥2, be a family of trees. In this paper, we show that the graph ∏ _{i =1} ⁿ T _i admits an (r, d)-invariant orientation provided that d(T ₁)≥d(T ₂)≥4 for n=2, and d(T ₁)≥5 and d(T ₂)≥4 for n≥3. Received: July 30, 1997 Final version received: April 20, 1998     

Two tractable subclasses of minimal unsatisfiable formulas

The minimal unsatisfiability problem is considered of the prepositional formulas in CNF which in the case of variablesx ₁,⋯,x _n consist ofn +k clauses including it,x ₁ V ⋯ Vx _n and ⌉x ₁ V ⋯ V ⌉x _n It is shown that whenk ⩽4 the minimal unsatisfiability problem can be solved in polynomial time. Project supported by the National Natural Science Foundation of China (Grant No. 19771045) and Nationl High-Tech R&D Project (863) (Grant No. 863-306-ET06-01-2).     

On thek dimensional Piatetski-Shapiro prime number theorem

Thek-dimensional Piatetski-Shapiro prime number problem fork⩾3 is studied. Let π(x ₁ c ₁,⋯,c _k ) denote the number of primesp withp⩽x, , where 1<c ₁<⋯<c _k are fixed constants. It is proved that π(x;c ₁,⋯,c _k ) has an asymptotic formula ifc ₁ ⁻¹ +⋯+c _k ⁻¹ >k−k/(4k ²+2). Project supported by the National Natural Science Foundation of China (Grant No. 19801021) and the Natural Science Foundation of Shandong Province (Grant No.Q98A02110).     

Tracking and invariance problems for some classes of discrete delay systems

Consider the system with perturbation g _k ∈ ℝ ⁿ and output z _k = Cx _k . Here, A _k ,A _k ^(s) ∈ ℝ ^{n × n} , B _k ⁽¹⁾ ∈ ℝ ^{n × p} , B _k ⁽²⁾ ∈ ℝ ^{n × m} , C ∈ ℝ ^{p × n} . We construct a special Lyapunov-Krasovskii functional in order to synthesize controls u _k ⁽¹⁾ and u _k ⁽²⁾ for which the following properties are satisfied:

Refined enumerations of alternating sign matrices: monotone (<Emphasis Type="Italic">d</Emphasis>,<Emphasis Type="Italic">m</Emphasis>)-trapezoids with prescribed top and bottom row

Monotone triangles are plane integer arrays of triangular shape with certain monotonicity conditions along rows and diagonals. Their significance is mainly due to the fact that they correspond to n×n alternating sign matrices when prescribing (1,2,…,n) as bottom row of the array. We define monotone (d,m)-trapezoids as monotone triangles with m rows where the d−1 top rows are removed. (These objects are also equivalent to certain partial alternating sign matrices.) It is known that the number of monotone triangles with bottom row (k ₁,…,k _n ) is given by a polynomial α(n;k ₁,…,k _n ) in the k _i ’s. The main purpose of this paper is to show that the number of monotone (d,m)-trapezoids with prescribed top and bottom row appears as a coefficient in the expansion of a specialisation of α(n;k ₁,…,k _n ) with respect to a certain polynomial basis. This settles a generalisation of a recent conjecture of Romik et al. (Adv. Math. 222:2004–2035, 2009). Among other things, the result is used to express the number of monotone triangles with bottom row (1,2,…,i−1,i+1,…,j−1,j+1,…,n) (which is, by the standard bijection, also the number of n×n alternating sign matrices with given top two rows) in terms of the number of n×n alternating sign matrices with prescribed top and bottom row, and, by a formula of Stroganov for the latter numbers, to provide an explicit formula for the first numbers. (A formula of this type was first derived by Karklinsky and Romik using the relation of alternating sign matrices to the six-vertex model.)     

On the Construction of Permutation Arrays via Mappings from Binary Vectors to Permutations

An (n, d, k)-mapping f is a mapping from binary vectors of length n to permutations of length n + k such that for all x, y {0,1}ⁿ, d_H (f(x), f(y)) ≥ d_H (x, y) + d, if d_H (x, y) ≤ (n + k) − d and d_H (f(x), f(y)) = n + k, if d_H (x, y) > (n + k) − d. In this paper, we construct an (n,3,2)-mapping for any positive integer n ≥ 6. An (n, r)-permutation array is a permutation array of length n and any two permutations of which have Hamming distance at least r. Let P(n, r) denote the maximum size of an (n, r)-permutation array and A(n, r) denote the same setting for binary codes. Applying (n,3,2)-mappings to the design of permutation array, we can construct an efficient permutation array (easy to encode and decode) with better code rate than previous results [Chang (2005). IEEE Trans inf theory 51:359–365, Chang et al. (2003). IEEE Trans Inf Theory 49:1054–1059; Huang et al. (submitted)]. More precisely, we obtain that, for n ≥ 8, P(n, r) ≥ A(n − 2, r − 3) > A(n − 1,r − 2) = A(n, r − 1) when n is even and P(n, r) ≥ A(n − 2, r − 3) = A(n − 1, r − 2) > A(n, r − 1) when n is odd. This improves the best bound A(n − 1,r − 2) so far [Huang et al. (submitted)] for n ≥ 8. The work was supported in part by the National Science Council of Taiwan under contract NSC-93-2213-E-009-117     

Structures and Chromaticity of Extremal 3-Colourable Sparse Graphs

 Assume that G is a 3-colourable connected graph with e(G) = 2v(G) −k, where k≥ 4. It has been shown that s ₃(G) ≥ 2 ^{k −3}, where s _r (G) = P(G,r)/r! for any positive integer r and P(G, λ) is the chromatic polynomial of G. In this paper, we prove that if G is 2-connected and s ₃(G) < 2 ^{k −2}, then G contains at most v(G) −k triangles; and the upper bound is attained only if G is a graph obtained by replacing each edge in the k-cycle C _k by a 2-tree. By using this result, we settle the problem of determining if W(n, s) is χ-unique, where W(n, s) is the graph obtained from the wheel W _n by deleting all but s consecutive spokes. Received: January 29, 1999 Final version received: April 8, 2000     

The Smallest Degree Sum That Yields Potentially Kr＋1 - K3-Graphic Sequences

Let a（Kr,＋1 - K3,n） be the smallest even integer such that each n-term graphic sequence п= （d1,d2,…dn） with term sum σ（п） = d1 ＋ d2 ＋…＋ dn 〉 σ（Kr＋1 -K3,n） has a realization containing Kr＋1 - K3 as a subgraph, where Kr＋1 -K3 is a graph obtained from a complete graph Kr＋1 by deleting three edges which form a triangle. In this paper, we determine the value σ（Kr＋1 - K3,n） for r ≥ 3 and n ≥ 3r＋ 5.     

The Erdös-Jacobson-Lehel conjecture on potentiallyP k-graphic sequence is true

A variation in the classical Turan extrernal problem is studied. A simple graphG of ordern is said to have propertyPk if it contains a clique of sizek+1 as its subgraph. Ann-term nonincreasing nonnegative integer sequence π=(d₁, d₂,⋯, d₂) is said to be graphic if it is the degree sequence of a simple graphG of ordern and such a graphG is referred to as a realization of π. A graphic sequence π is said to be potentiallyP _k-graphic if it has a realizationG having propertyP _k . The problem: determine the smallest positive even number σ(k, n) such that everyn-term graphic sequence π=(d₁, d₂,…, d₂) without zero terms and with degree sum σ(π)=(d ₁+d ₂+ …+d ₂) at least σ(k,n) is potentially P_k-graphic has been proved positive. Project supported by the National Natural Science Foundation of China (Grant No. 19671077) and the Doctoral Program Foundation of National Education Department of China.     

Gauge-Invariant Characterization of Yang–Mills–Higgs Equations

Let C → M be the bundle of connections of a principal G-bundle P → M over a pseudo-Riemannian manifold (M,g) of signature (n⁺, n⁻) and let E → M be the associated bundle with P under a linear representation of G on a finite-dimensional vector space. For an arbitrary Lie group G, the O(n⁺, n⁻) × G-invariant quadratic Lagrangians on J¹(C × _M E) are characterized. In particular, for a simple Lie group the Yang–Mills and Yang–Mills–Higgs Lagrangians are characterized, up to an scalar factor, to be the only O(n⁺, n⁻) × G-invariant quadratic Lagrangians. These results are also analyzed on several examples of interest in gauge theory. Submitted: May 19, 2005; Accepted: April 25, 2006     

A generalization of Meshulam’s theorem on subsets of finite abelian groups with no 3-term arithmetic progression

Let r ₁, …, r _s be non-zero integers satisfying r ₁ + ⋯ + r _s = 0. Let G be a finite abelian group with k _i |k _i-1(2 ≤ i ≤ n), and suppose that (r _i , k ₁) = 1(1 ≤ i ≤ s). Let denote the maximal cardinality of a set which contains no non-trivial solution of r ₁ x ₁ + ⋯ + r _s x _s = 0 with . We prove that . We also apply this result to study problems in finite projective spaces.      

Rates of uniform convergence for empirical processes of strictly stationary β-mixing sequences indexed by an unbounded class of functions

Assume that {Xn} is a strictly stationary β-mixing random sequence with the β-mixing coefficient βk = O(k-r), 0 < r ≤1. Yu (1994) obtained convergence rates of empirical processes of strictly stationary β-mixing random sequence indexed by bounded classes of functions. Here, a new truncation method is proposed and used to study the convergence for empirical processes of strictly stationary β-mixing sequences indexed by an unbounded class of functions. The research results show that if the envelope of the index class of functions is in Lp, p > 2 or p > 4, uniform convergence rates of empirical processes of strictly stationary β-mixing random sequence over the index classes can reach O((nr/(l+r)/logn)-1/2) or O((nr/(1+r)/ log n)-3/4) and that the Central Limit Theorem does not always hold for the empirical processes.``     

Sharp bounds for decompositions of graphs into complete r-partite subgraphs

If G is a graph on n vertices and r ≥ 2, we let m_r(G) denote the minimum number of complete multipartite subgraphs, with r or fewer parts, needed to partition the edge set, E(G). In determining m_r(G), we may assume that no two vertices of G have the same neighbor set. For such reducedgraphs G, we prove that m_r(G) ≥ log₂ (n + r − 1)/r. Furthermore, for each k ≥ 0 and r ≥ 2, there is a unique reduced graph G = G(r, k) with m_r(G) = k for which equality holds. We conclude with a short proof of the known eigenvalue bound m_r(G) ≥ max{n₊ (G, n₋(G)/(r − 1)}, and show that equality holds if G = G(r, k). © 1996 John Wiley & Sons, Inc.     

New upper bounds for the Davenport and for the Erdős–Ginzburg–Ziv constants

Let G be a finite abelian group (written additively) of rank r with invariants n ₁, n ₂, . . . , n _r , where n _r is the exponent of G. In this paper, we prove an upper bound for the Davenport constant D(G) of G as follows; D(G) ≤ n _r + n _r-1 + (c(3) − 1)n _r-2 + (c(4) − 1) n _r-3 + · · · + (c(r) − 1)n ₁ + 1, where c(i) is the Alon–Dubiner constant, which depends only on the rank of the group \mathbb Z_nrⁱ{{\mathbb Z}_{n_r}^i}. Also, we shall give an application of Davenport’s constant to smooth numbers related to the Quadratic sieve.     

Product of Uniform Distribution and Stirling Numbers of the First Kind

Let Vk=u1u2……uk, ui＇s be i.i.d - U（0, 1）, the p.d.f of 1 - Vk＋l be the GF of the unsigned Stirling numbers of the first kind s（n, k）. This paper discusses the applications of uniform distribution to combinatorial analysis and Riemann zeta function; several identities of Stifling series are established, and the Euler＇s result for ∑ Hn/n^k-l, k ≥ 3 is given a new probabilistic proof.     

An almost sure invariance principle for trimmed sums of random vectors

Let {X _n ; n ≥ 1} be a sequence of independent and identically distributed random vectors in ℜ ^p with Euclidean norm |·|, and let X _n ^(r) = X _m if |X _m | is the r-th maximum of {|X _k |; k ≤ n}. Define S _n = Σ _k≤n X _k and ^(r) S _n − (X _n ⁽¹⁾ + ... + X _n ^(r)). In this paper a generalized strong invariance principle for the trimmed sums ^(r) S _n is derived.     

On numerical experiments with symmetric semigroups generated by three elements and their generalization

We give a simple explanation of numerical experiments of V. Arnold with two sequences of symmetric numerical semigroups, S(4,6+4k,87−4k) and S(9,3+9k,85−9k) generated by three elements. We present a generalization of these sequences by numerical semigroups S(r₁²,r₁r₂+r₁²k,r₃-r₁²k)\mathsf{S}(r_{1}^{2},r_{1}r_{2}+r_{1}^{2}k,r_{3}-r_{1}^{2}k), k∈ℤ, r ₁,r ₂,r ₃∈ℤ⁺, r ₁≥2 and gcd(r ₁,r ₂)=gcd(r ₁,r ₃)=1, and calculate their universal Frobenius number Φ(r ₁,r ₂,r ₃) for the wide range of k providing semigroups be symmetric. We show that this type of semigroups admit also nonsymmetric representatives. We describe the reduction of the minimal generating sets of these semigroups up to {r₁²,r₃-r₁²k}\{r_{1}^{2},r_{3}-r_{1}^{2}k\} for sporadic values of k and find these values by solving the quadratic Diophantine equation.