Cycle Lemma, Parking Functions and Related Multigraphs

For positive integers a and b, an ${(a, \overline{b})}$ -parking function of length n is a sequence (p ₁, . . . , p _n ) of nonnegative integers whose weakly increasing order q ₁ ≤ . . . ≤ q _n satisfies the condition q _i  < a + (i ? 1)b. In this paper, we give a new proof of the enumeration formula for ${(a, \overline{b})}$ -parking functions by using of the cycle lemma for words, which leads to some enumerative results for the ${(a, \overline{b})}$ -parking functions with some restrictions such as symmetric property and periodic property. Based on a bijection between ${(a, \overline{b})}$ -parking functions and rooted forests, we enumerate combinatorially the ${(a, \overline{b})}$ -parking functions with identical initial terms and symmetric ${(a, \overline{b})}$ -parking functions with respect to the middle term. Moreover, we derive the critical group of a multigraph that is closely related to ${(a, \overline{b})}$ -parking functions.     

Smallest Set-Transversals of k-Partitions

We asymptotically solve an open problem raised independently by Sterboul (Colloq Math Soc J Bolyai 3:1387–1404, 1973), Arocha et al. (J Graph Theory 16:319–326, 1992) and Voloshin (Australas J Combin 11:25–45, 1995). For integers n ≥ k ≥ 2, let f(n, k) denote the minimum cardinality of a family ${\mathcal H}$ of k-element sets over an n-element underlying set X such that every partition ${X_1\cup\cdots\cup X_k=X}$ into k nonempty classes completely partitions some ${H\in\mathcal H}$ ;  that is, ${|H\cap X_i|=1}$ holds for all 1 ≤ i ≤ k. This very natural function—whose defining property for k = 2 just means that ${\mathcal H}$ is a connected graph—turns out to be related to several extensively studied areas in combinatorics and graph theory. We prove general estimates from which ${ f(n,k) = (1+o(1))\, \tfrac{2}{n}\,{n\choose k}}$ follows for every fixed k, and also for all k = o(n ^1/3), as n → ∞. Further, we disprove a conjecture of Arocha et al. (1992). The exact determination of f(n,k) for all n and k appears to be far beyond reach to our present knowledge, since e.g. the equality ${f(n,n-2)={n-2\choose 2}-{\rm ex}(n,\{C_3,C_4\})}$ holds, where the last term is the Turán number for graphs of girth 5.     

Circuits of Each Length in Tournaments

A tournament is a directed graph whose underlying graph is a complete graph. A circuit is an alternating sequence of vertices and arcs of the form v ₁, a ₁, v ₂, a ₂, v ₃, . . . , v _n-1, a _n-1, v _n in which vertex v _n  = v ₁, arc a _i  = v _i v _i+1 for i = 1, 2, . . . , n?1, and \({a_i \neq a_j}\) if \({i \neq j}\) . In this paper, we shall show that every tournament T _n in a subclass of tournaments has a circuit of each length k for \({3 \leqslant k \leqslant \theta(T_n)}\) , where \({\theta(T_n) = \frac{n(n-1)}{2}-3}\) if n is odd and \({\theta(T_n) = \frac{n(n-1)}{2}-\frac{n}{2}}\) otherwise. Note that a graph having θ(G) > n can be used as a host graph on embedding cycles with lengths larger than n to it if congestions are allowed only on vertices.     

On multiplicative congruences

Let ${\varepsilon}$ be a fixed positive quantity, m be a large integer, x _j denote integer variables. We prove that for any positive integers N ₁, N ₂, N ₃ with ${N_1N_2N_3 > m^{1+\varepsilon}, }$ the set $$\{x_1x_2x_3 \quad ({\rm mod}\,m): \quad x_j\in [1,N_j]\}$$ contains almost all the residue classes modulo m (i.e., its cardinality is equal to m + o(m)). We further show that if m is cubefree, then for any positive integers N ₁, N ₂, N ₃, N ₄ with ${ N_1N_2N_3N_4 > m^{1+\varepsilon}, }$ the set $$\{x_1x_2x_3x_4 \quad ({\rm mod}\,m): \quad x_j\in [1,N_j]\}$$ also contains almost all the residue classes modulo m. Let p be a large prime parameter and let ${p > N > p^{63/76+\varepsilon}.}$ We prove that for any nonzero integer constant k and any integer ${\lambda\not\equiv 0 \,\, ({\rm mod}\,p)}$ the congruence $$p_1p_2(p_3+k)\equiv \lambda \quad ({\rm mod}\, p) $$ admits (1 + o(1))π(N)³/p solutions in prime numbers p ₁, p ₂, p ₃ ≤ N.     

A Hardy type inequality for W m,1(0, 1) functions

In this paper, we consider functions ${u\in W^{m,1}(0,1)}$ where m ≥ 2 and u(0) = Du(0) = · · · = D ^m-1 u(0) = 0. Although it is not true in general that ${\frac{D^ju(x)}{x^{m-j}} \in L^1(0,1)}$ for ${j\in \{0,1,\ldots,m-1\}}$ , we prove that ${\frac{D^ju(x)}{x^{m-j-k}} \in W^{k,1}(0,1)}$ if k ≥ 1 and 1 ≤ j + k ≤ m, with j, k integers. Furthermore, we have the following Hardy type inequality, $$\left\|{D^k\left({\frac{D^ju(x)}{x^{m-j-k}}}\right)}\right\|_{L^1(0,1)} \leq \frac {(k-1)!}{(m-j-1)!} \|{D^mu}\|_{L^1(0,1)},$$ where the constant is optimal.     

The Frobenius Complex

Motivated by the classical Frobenius problem, we introduce the Frobenius poset on the integers ${\mathbb Z}$ , that is, for a sub-semigroup ?? of the non-negative integers ( ${\mathbb N}$ , +), we define the order by n ??_?? m if ${{m-n \in \Lambda}}$ . When ?? is generated by two relatively prime integers a and b, we show that the order complex of an interval in the Frobenius poset is either contractible or homotopy equivalent to a sphere. We also show that when ?? is generated by the integers {a, a?+?d, a?+?2d, . . . , a?+?(a?1)d}, the order complex is homotopy equivalent to a wedge of spheres.     

Bases of trigonometric polynomials consisting of shifts of Dirichlet kernels

The system of shifts of Dirichlet kernel on \(\frac{{2k\pi }} {{2n + 1}} \) , k = 0, ± 1, …, ± n, and the system of such shifts of conjugate Dirichlet kernels with \(\frac{1} {2} \) are orthogonal bases in the space of trigonometric polynomials of degree n. The system of shifts of the kernels \(\Sigma _{k = m}^n \) cos kx and \(\Sigma _{k = m}^n \) sin kx on \(\frac{{2k\pi }} {{n - m + 1}} \) , k = 0, 1, …, n?m, is an orthogonal basis in the space of trigonometric polynomials with the components from m ? 1 to n. There is no orthogonal basis of shifts of any function in this space for 0 < m < n.     

On All Fractional （a,b, k）-Critical Graphs

Let a,b,k,r be nonnegative integers with 1≤a≤b and r≥2.LetG be a graph of order n with n(a+b)(r(a+b)-2)+ak/a.In this paper,we first show a characterization for all fractional(a,b,k)-critical graphs.Then using the result,we prove that G is all fractional(a,b,k)-critical if δ(G)≥(r-1)b2/a+k and |NG(x1)∪NG(x2)∪···∪NG(xr)|≥bn+ak/a+b for any independent subset {x1,x2,...,xr} in G.Furthermore,it is shown that the lower bound on the condition|NG(x1)∪NG(x2)∪···∪NG(xr)|≥bn+ak/a+b is best possible in some sense,and it is an extension of Lu's previous result.     

Smoothness of convolution powers of orbital measures on the symmetric space SU(n)/SO(n)

We prove that if ${\mu _{a}\,{=}\,m_{K}*\delta _{a}*m_{K}}$ is the K-bi-invariant measure supported on the double coset ${KaK\subseteq SU(n)}$ , for K = SO(n), then ${\mu _{a}^{k}}$ is absolutely continuous with respect to the Haar measure on SU(n) for all a not in the normalizer of K if and only if k ≥ n. The measure, μ _a , supported on the minimal dimension double coset has the property that ${\mu _{a}^{n-1}}$ is singular to the Haar measure.     

Iterates of increasing sequences of positive integers

It is proved that for fixed integers ${K \ge 2, D \ge 2, {\rm if} (D - 1) \mid K}$ , then there exists a unique increasing sequence (a(n)) _{n ≥ K} of positive integers such that $$\underset{K {\rm times}}{\underbrace{a ( a ( \dots a(a}}(n)) \dots)) = Dn$$ otherwise, there are uncountably many increasing sequences of positive integers (a(n)) satisfying this iterated functional equation. This generalizes recent results of Propp and Allouche–Rampersad–Shallit.     

On periodic decomposition of entire functions of several variables

Consider the difference equation on \({{\mathbb{C}}^n}\) : \({\Delta_{c_1}\Delta_{c_2}\cdots \Delta_{c_m}f(z)=0}\) , where \({c_1,c_2, \ldots, c_m \in \mathbb{C}^n\backslash \{0\}}\) and \({\Delta_{c_k}f(z)=f(z+c_k)-f(z)}\) . In this paper, we assume that c ₁, . . . , c _m are pairwise linearly independent over \({\mathbb{R}}\) , except for the case m = 2. Firstly, we establish a general representation of its entire solutions. Secondly, under the condition L ≤ n, we give a necessary and sufficient conditions for entire solutions to have representations as a sum of c _k -periodic entire functions. Here L is the maximum integer such that \({c_{k_1},c_{k_2}, \ldots,c_{k_L}}\) are pairwise linearly independent over \({\mathbb{C}}\) for some k ₁,k ₂, . . . ,k _L . Finally, we show that every entire solution has a representation as a sum of c _k -periodic meromorphic functions.     

Identities for Bernoulli polynomials and Bernoulli numbers

We prove that if m and \({\nu}\) are integers with \({0 \leq \nu \leq m}\) and x is a real number, then

1. $$\sum_{k=0 \atop k+m \, \, odd}^{m-1} {m \choose k}{k+m \choose \nu} B_{k+m-\nu}(x) = \frac{1}{2} \sum_{j=0}^m (-1)^{j+m} {m \choose j}{j+m-1 \choose \nu} (j+m) x^{j+m-\nu-1},$$ where B _n (x) denotes the Bernoulli polynomial of degree n. An application of (1) leads to new identities for Bernoulli numbers B _n . Among others, we obtain
2. $$\sum_{k=0 \atop k+m \, \, odd}^{m -1} {m \choose k}{k+m \choose \nu} {k+m-\nu \choose j}B_{k+m-\nu-j} =0 \quad{(0 \leq j \leq m-2-\nu)}. $$ This formula extends two results obtained by Kaneko and Chen-Sun, who proved (2) for the special cases j = 1, \({\nu=0}\) and j = 3, \({\nu=0}\) , respectively.

     

A method of convergence acceleration of some continued fractions II

Most of the methods for convergence acceleration of continued fractions K(a _m /b _m ) are based on the use of modified approximants S _m (ω _m ) in place of the classical ones S _m (0), where ω _m are close to the tails f ^(m) of the continued fraction. Recently (Nowak, Numer Algorithms 41(3):297–317, 2006), the author proposed an iterative method producing tail approximations whose asymptotic expansion accuracies are being improved in each step. This method can be successfully applied to a convergent continued fraction K(a _m /b _m ), where $a_m = \alpha_{-2} m^2 + \alpha_{-1} m + \ldots$ , b _m ?=?β _???1 m?+?β ₀?+?... (α _???2?≠?0, $|\beta_{-1}|^2+|\beta_{0}|^2\neq 0$ , i.e. $\deg a_m=2$ , $\deg b_m\in\{0,1\}$ ). The purpose of this paper is to extend this idea to the class of two-variant continued fractions K (a _n /b _n ?+?a _n ′/b _n ′) with a _n , a _n ′, b _n , b _n ′ being rational in n and $\deg a_n=\deg a_n'$ , $\deg b_n=\deg b_n'$ . We give examples involving continued fraction expansions of some elementary and special mathematical functions.     

Compact Hankel Operators on Generalized Bergman Spaces of the Polydisc

Let ${\vartheta}$ be a measure on the polydisc ${\mathbb{D}^n}$ which is the product of n regular Borel probability measures so that ${\vartheta([r,1)^n\times\mathbb{T}^n) >0 }$ for all 0 < r < 1. The Bergman space ${A^2_{\vartheta}}$ consists of all holomorphic functions that are square integrable with respect to ${\vartheta}$ . In one dimension, it is well known that if f is continuous on the closed disc ${\overline{\mathbb{D}}}$ , then the Hankel operator H _f is compact on ${A^2_\vartheta}$ . In this paper we show that for n ≥ 2 and f a continuous function on ${{\overline{\mathbb{D}}}^n}$ , H _f is compact on ${A^2_\vartheta}$ if and only if there is a decomposition f = h + g, where h belongs to ${A^2_\vartheta}$ and ${\lim_{z\to\partial\mathbb{D}^n}g(z)=0}$ .     

Fractional Type Integral Operators on Variable Hardy Spaces

Given certain n × n invertible matrices A ₁, . . . , A _m and 0 ≦ α < n, we obtain the \({H^{p(.)}(\mathbb{R}^n) \to L^{q(.)}(\mathbb{R}^n)}\) boundedness of the integral operator with kernel \({k(x, y) = |x - A_1y|^{-\alpha_1} . . . |x - A_my|^{-\alpha_m}}\) , where α ₁ +  . . . + α _m = n ? α and p(.), q(.) are exponent functions satisfying log-Hölder continuity conditions locally and at infinity related by \({\frac{1}{q(.)} = \frac{1}{p(.)} - \frac{\alpha}{n}}\) . We also obtain the \({H^{p(.)}(\mathbb{R}^n) \to H^{q(.)}(\mathbb{R}^n)}\) boundedness of the Riesz potential operator.     

Globally generated vector bundles and the Weak Lefschetz property

Artinian ideals \({I\subset R: =k[x_1,..., x_n]}\) generated by m general forms of given degree have attracted a great deal of attention recently, and one of the main challenging problems is to determine its Hilbert function. The Hilbert function of R/I was conjectured by Fröberg, and it is well known that the Weak Lefschetz property imposes severe constraints on the possible Hilbert functions. In this short note, we will focus our attention on Artinian ideals \({I \subset R}\) generated by m general forms all of the same degree d and we analyze whether the Weak Lefschetz property is satisfied. More precisely, for m = n or n ≤ 4 the Weak Lefschetz property holds, and our goal will be to prove that for any integers n and d, the Weak Lefschetz property also holds provided m falls into the interval \({[\frac{1}{d+1} \alpha_{n,d}, \alpha_{n,d}]}\) where \({\alpha_{n,d}={n+d-1\choose d}}\) .     

Blow-up solutions concentrated along minimal submanifolds for some supercritical elliptic problems on Riemannian manifolds

Let (M, g) and \({(K, \kappa)}\) be two Riemannian manifolds of dimensions m and k, respectively. Let \({\omega \in C^{2} (N), \omega > 0}\) . The warped product \({M \times_\omega K}\) is the (m +  k)-dimensional product manifold \({M \times K}\) furnished with metric \({g + \omega^{2} \kappa}\) . We prove that the supercritical problem $$- \Delta_{g + \omega^{2} \kappa} u + hu = u^{\frac{m+2}{m-2} \pm \varepsilon} ,\quad u > 0,\quad {\rm in}\,\, (M \times_{\omega} K, g + \omega^{2} \kappa)$$ has a solution concentrated along a k-dimensional minimal submanifold \({\Gamma}\) of \({M \times_{\omega } N}\) as the real parameter \({\varepsilon}\) goes to zero, provided the function h and the sectional curvatures along \({\Gamma}\) satisfy a suitable condition.     

Forbidden Configurations and Product Constructions

A simple matrix is a (0,1)-matrix with no repeated columns. For a (0,1)-matrix F, we say that a (0,1)-matrix A has F as a configuration if there is a submatrix of A which is a row and column permutation of F (trace is the set system version of a configuration). Let \({\|A\|}\) denote the number of columns of A. We define \({{\rm forb}(m, F) = {\rm max}\{\|A\| \,:\, A}\) is m-rowed simple matrix and has no configuration F. We extend this to a family \({\mathcal{F} = \{F_1, F_2, \ldots , F_t\}}\) and define \({{\rm forb}(m, \mathcal{F}) = {\rm max}\{\|A\| \,:\, A}\) is m-rowed simple matrix and has no configuration \({F \in \mathcal{F}\}}\) . We consider products of matrices. Given an m ₁ × n ₁ matrix A and an m ₂ × n ₂ matrix B, we define the product A × B as the (m ₁ + m ₂) × n ₁ n ₂ matrix whose columns consist of all possible combinations obtained from placing a column of A on top of a column of B. Let I _k denote the k × k identity matrix, let \({I_k^{c}}\) denote the (0,1)-complement of I _k and let T _k denote the k × k upper triangular (0,1)-matrix with a 1 in position i, j if and only if i ≤ j. We show forb(m, {I ₂ × I ₂, T ₂ × T ₂}) is \({\Theta(m^{3/2})}\) while obtaining a linear bound when forbidding all 2-fold products of all 2 × 2 (0,1)-simple matrices. For two matrices F, P, where P is m-rowed, let \({f(F, P) = {\rm max}_{A} \{\|A\| \,:\,A}\) is m-rowed submatrix of P with no configuration F}. We establish f(I ₂ × I ₂, I _m/2 × I _m/2) is \({\Theta(m^{3/2})}\) whereas f(I ₂ × T ₂, I _m/2 × T _m/2) and f(T ₂ × T ₂, T _m/2 × T _m/2) are both \({\Theta(m)}\) . Additional results are obtained. One of the results requires extensive use of a computer program. We use the results on patterns due to Marcus and Tardos and generalizations due to Klazar and Marcus, Balogh, Bollobás and Morris.     

On additive representation functions of finite sets, I (Variation)

If m ∈ ?, ? _m is the additive group of the modulo m residue classes, $\mathcal{A} \subset \mathbb{Z}_m$ and n ∈ ?, ? _m , then let $R\left( {\mathcal{A},n} \right)$ denote the number of solutions of a+a′ = n with $a,a' \in \mathcal{A}$ . The variation $V(\mathcal{A}) = \mathop {\max }\limits_{n \in \mathbb{Z}_m } |R(\mathcal{A},n + 1) - R(\mathcal{A},n)|$ is estimated in terms of the number of a’s with $a - 1 \notin \mathcal{A}$ , $a \in \mathcal{A}$ .