On sums of binomial coefficients and their applications

In this paper we study recurrences concerning the combinatorial sum and the alternate sum , where m>0, n?0 and r are integers. For example, we show that if n?m-1 then

     

On the signed edge domination number of graphs

Let be the signed edge domination number of G. In 2006, Xu conjectured that: for any 2-connected graph G of order n(n≥2), . In this article we show that this conjecture is not true. More precisely, we show that for any positive integer m, there exists an m-connected graph G such that . Also for every two natural numbers m and n, we determine , where K_m,n is the complete bipartite graph with part sizes m and n.     

Embeddings of homology equivalent manifolds with boundary

We prove a theorem on equivariant maps implying the following two corollaries:(1) Let N and M be compact orientable n-manifolds with boundaries such that M⊂N, the inclusion M→N induces an isomorphism in integral cohomology, both M and N have (n−d−1)-dimensional spines and . Then the restriction-induced map Embm(N)→Embm(M) is bijective. Here Embm(X) is the set of embeddings X→Rm up to isotopy (in the PL or smooth category).(2) For a 3-manifold N with boundary whose integral homology groups are trivial and such that N?D³ (or for its special 2-spine N) there exists an equivariant map , although N does not embed into R³.The second corollary completes the answer to the following question: for which pairs (m,n) for each n-polyhedron N the existence of an equivariant map implies embeddability of N into Rm? An answer was known for each pair (m,n) except (3,3) and (3,2).     

Covering numbers of different points in Dvoretzky covering

Consider the Dvoretzky random covering on the circle T with a decreasing length sequence {?n}_n?1 such that . We study, for a given β?0, the set Fβ of points which are asymptotically covered by a number βLn of the first n randomly placed intervals where . Three typical situations arise, delimited by two “phase transitions”, according to is zero, positive-finite or infinite, where . More precisely, if ?n tends to zero rapidly enough so that then, with probability one, dimHFβ=1 for all β?0; if ?n is moderate so that then, with probability one, we have for and Fβ=∅ for where and is the interval consisting of β's such that ; eventually, if ?n is so slow that then, with probability one, F₁=T. This solves a problem raised by L. Carleson in a rather satisfactory fashion.Analogous results are obtained for the Poisson covering of the line, which is studied as a tool.     

Quadratic addition rules for quantum integers

For every positive integer n, the quantum integer [n]_q is the polynomial [n]_q=1+q+q²+?+q^n-1. A quadratic addition rule for quantum integers consists of sequences of polynomials , , and such that for all m and n. This paper gives a complete classification of quadratic addition rules, and also considers sequences of polynomials that satisfy the associated functional equation .     

Set partitions and moments of random variables

It is well known that the sequence of Bell numbers (Bn)_n?0 (Bn being the number of partitions of the set [n]) is the sequence of moments of a mean 1 Poisson random variable τ (a fact expressed in the Dobiński formula), and the shifted sequence (Bn+1)_n?0 is the sequence of moments of 1+τ. In this paper, we generalize these results by showing that both and (where is the number of m-partitions of [n], as they are defined in the paper) are moment sequences of certain random variables. Moreover, such sequences also are sequences of falling factorial moments of related random variables. Similar results are obtained when is replaced by the number of ordered m-partitions of [n]. In all cases, the respective random variables are constructed from sequences of independent standard Poisson processes.     

Simple arguments on consecutive power residues

By some extremely simple arguments, we point out the following:

(i)

If n is the least positive kth power non-residue modulo a positive integer m, then the greatest number of consecutive kth power residues mod m is smaller than m/n.

(ii)

Let OK be the ring of algebraic integers in a quadratic field with d∈{−1,−2,−3,−7,−11}. Then, for any irreducible π∈OK and positive integer k not relatively prime to , there exists a kth power non-residue ω∈OK modulo π such that .

     

The orientable genus of some joins of complete graphs with large edgeless graphs

In an earlier paper the authors showed that with one exception the nonorientable genus of the graph with m≥n−1, the join of a complete graph with a large edgeless graph, is the same as the nonorientable genus of the spanning subgraph . The orientable genus problem for with m≥n−1 seems to be more difficult, but in this paper we find the orientable genus of some of these graphs. In particular, we determine the genus of when n is even and m≥n, the genus of when n=2^p+2 for p≥3 and m≥n−1, and the genus of when n=2^p+1 for p≥3 and m≥n+1. In all of these cases the genus is the same as the genus of K_m,n, namely ⌈(m−2)(n−2)/4⌉.     

Perfectness and imperfectness of unit disk graphs on triangular lattice points

Given a finite set of 2-dimensional points P⊆R² and a positive real d, a unit disk graph, denoted by (P,d), is an undirected graph with vertex set P such that two vertices are adjacent if and only if the Euclidean distance between the pair is less than or equal to d. Given a pair of non-negative integers m and n, P(m,n) denotes a subset of 2-dimensional triangular lattice points defined by where . Let T_m,n(d) be a unit disk graph defined on a vertex set P(m,n) and a positive real d. Let be the kth power of T_m,n(1).In this paper, we show necessary and sufficient conditions that [ is perfect] and/or [ is perfect], respectively. These conditions imply polynomial time approximation algorithms for multicoloring (T_m,n(d),w) and .     

Arithmetical properties of wendt's determinant

Wendt's determinant of order n is the circulant determinant W_n whose (i,j)-th entry is the binomial coefficient , for 1?i,j?n, where n is a positive integer. We establish some congruence relations satisfied by these rational integers. Thus, if p is a prime number and k a positive integer, then and . If q is another prime, distinct from p, and h any positive integer, then . Furthermore, if p is odd, then . In particular, if p?5, then . Also, if m and n are relatively prime positive integers, then W_mW_n divides W_mn.     

Classification of quasifinite modules over the Lie algebras of Weyl type

For a nondegenerate additive subgroup Γ of the n-dimensional vector space over an algebraically closed field of characteristic zero, there is an associative algebra and a Lie algebra of Weyl type spanned by all differential operators uD₁^m₁?D_n^m_n for (the group algebra), and m₁,…,m_n?0, where D₁,…,D_n are degree operators. In this paper, it is proved that an irreducible quasifinite -module is either a highest or lowest weight module or else a module of the intermediate series; furthermore, a classification of uniformly bounded -modules is completely given. It is also proved that an irreducible quasifinite -module is a module of the intermediate series and a complete classification of quasifinite -modules is also given, if Γ is not isomorphic to .     

Continued fractions, special values of the double sine function, and Stark units over real quadratic fields

Let F be a real quadratic field and m an integral ideal of F. Two Stark units, εm,1 and εm,2, are conjectured to exist corresponding to the two different embeddings of F into R. We define new ray class invariants and associated to each class C₊ of the narrow ray class group modulo m and dependent separately on the two different embeddings of F into R. These invariants are defined as a product of special values of the double sine function in a compact and canonical form using a continued fraction approach due to Zagier and Hayes. We prove that both Stark units εm,1 and εm,2, assuming they exist, can be expressed simultaneously and symmetrically in terms of and , thus giving a canonical expression for every existent Stark unit over F as a product of double sine function values. We prove that Stark units do exist as predicted in certain special cases.     

High-dimensional asymptotic expansions for the distributions of canonical correlations

This paper examines asymptotic distributions of the canonical correlations between and with q≤p, based on a sample of size of N=n+1. The asymptotic distributions of the canonical correlations have been studied extensively when the dimensions q and p are fixed and the sample size N tends toward infinity. However, these approximations worsen when q or p is large in comparison to N. To overcome this weakness, this paper first derives asymptotic distributions of the canonical correlations under a high-dimensional framework such that q is fixed, m=n−p→∞ and c=p/n→c₀∈[0,1), assuming that and have a joint (q+p)-variate normal distribution. An extended Fisher’s z-transformation is proposed. Then, the asymptotic distributions are improved further by deriving their asymptotic expansions. Numerical simulations revealed that our approximations are more accurate than the classical approximations for a large range of p,q, and n and the population canonical correlations.     

Large monochromatic components in colorings of complete 3-uniform hypergraphs

Let f(n,r) be the largest integer m with the following property: if the edges of the complete 3-uniform hypergraph are colored with r colors then there is a monochromatic component with at least m vertices. Here we show that and . Both results are sharp under suitable divisibility conditions (namely if n is divisible by 7, or by 6 respectively).     

Quartic, octic residues and Lucas sequences

Let be a prime and a,b∈Z with a²+b²≠p. Suppose p=x²+(a²+b²)y² for some integers x and y. In the paper we develop the calculation technique of quartic Jacobi symbols and use it to determine . As applications we obtain the congruences for modulo p and the criteria for (if ), where {Un} is the Lucas sequence given by U₀=0, U₁=1 and Un+1=bUn+k²Un−1(n?1). We also pose many conjectures concerning , or .