Estimates for sums of moduli of blocks in trigonometric Fourier series

We consider the following two problems. Problem 1: what conditions on a sequence of finite subsets A _k ? ? and a sequence of functions λ _k : A _k → ? provide the existence of a number C such that any function f ∈ L ₁ satisfies the inequality ‖U _A,Λ(f)‖ _p ≤ C‖f‖₁ and what is the exact constant in this inequality? Here, \(U_{\mathcal{A},\Lambda } \left( f \right)\left( x \right) = \sum\nolimits_{k = 1}^\infty {\left| {\sum\nolimits_{m \in A_k } {\lambda _k \left( m \right)c_m \left( f \right)e^{imx} } } \right|}\) and c _m (f) are Fourier coefficients of the function f ∈ L ₁. Problem 2: what conditions on a sequence of finite subsets A _k ? ? guarantee that the function \(\sum\nolimits_{k = 1}^\infty {\left| {\sum\nolimits_{m \in A_k } {c_m \left( h \right)e^{imx} } } \right|}\) belongs to L _p for every function h of bounded variation?     

Note on a conjecture for the sum of signless Laplacian eigenvalues

For a simple graph G on n vertices and an integer k with 1 ? k ? n, denote by \(\mathcal{S}^+_k\) (G) the sum of k largest signless Laplacian eigenvalues of G. It was conjectured that \(\mathcal{S}^+_k(G)\leqslant{e}(G)+(^{k+1}_{\;\;2})\) (G) ? e(G) + (k+1 2), where e(G) is the number of edges of G. This conjecture has been proved to be true for all graphs when k ∈ {1, 2, n ? 1, n}, and for trees, unicyclic graphs, bicyclic graphs and regular graphs (for all k). In this note, this conjecture is proved to be true for all graphs when k = n ? 2, and for some new classes of graphs.     

Universal Cycle Packings and Coverings for <Emphasis Type="Italic">k</Emphasis>-Subsets of an <Emphasis Type="Italic">n</Emphasis>-Set

A cyclic sequence of elements of [n] is an (n, k)-Ucycle packing (respectively, (n, k)-Ucycle covering) if every k-subset of [n] appears in this sequence at most once (resp. at least once) as a subsequence of consecutive terms. Let \(p_{n,k}\) be the length of a longest (n, k)-Ucycle packing and \(c_{n,k}\) the length of a shortest (n, k)-Ucycle covering. We show that, for a fixed \(k,p_{n,k}={n\atopwithdelims ()k}-O(n^{\lfloor k/2\rfloor })\). Moreover, when k is not fixed, we prove that if \(k=k(n)\le n^{\alpha }\), where \(0<\alpha <1/3\), then \(p_{n,k}={n\atopwithdelims ()k}-o({n\atopwithdelims ()k}^\beta )\) and \(c_{n,k}={n\atopwithdelims ()k}+o({n\atopwithdelims ()k}^\beta )\), for some \(\beta <1\). Finally, we show that if \(k=o(n)\), then \(p_{n,k}={n\atopwithdelims ()k}(1-o(1))\).     

On the phase transitions of (<Emphasis Type="Italic">k</Emphasis>, <Emphasis Type="Italic">q</Emphasis>)-SAT

Call a sequence of k Boolean variables or their negations a k-tuple. For a set V of n Boolean variables, let T _k (V) denote the set of all 2 ^k n ^k possible k-tuples on V. Randomly generate a set C of k-tuples by including every k-tuple in T _k (V) independently with probability p, and let Q be a given set of q “bad” tuple assignments. An instance I = (C,Q) is called satisfiable if there exists an assignment that does not set any of the k-tuples in C to a bad tuple assignment in Q. Suppose that θ, q > 0 are fixed and ε = ε(n) > 0 be such that εlnn/lnlnn→∞. Let k ≥ (1 + θ) log₂ n and let \({p_0} = \frac{{\ln 2}}{{q{n^{k - 1}}}}\). We prove that

$$\mathop {\lim }\limits_{n \to \infty } P\left[ {I is satisfiable} \right] = \left\{ {\begin{array}{*{20}c} {1,} & {p \leqslant (1 - \varepsilon )p_0 ,} \\ {0,} & {p \geqslant (1 + \varepsilon )p_0 .} \\ \end{array} } \right.$$

     

Boundary value problems for complete quasi-parabolic differential equations of odd order with variable domains of operators

We prove the well-posed solvability in the strong sense of the boundary value Problems

$$\begin{gathered} ( - 1)\frac{{_m d^{2m + 1} u}}{{dt^{2m + 1} }} + \sum\limits_{k = 0}^{m - 1} {\frac{{d^{k + 1} }}{{dt^{k + 1} }}} A_{2k + 1} (t)\frac{{d^k u}}{{dt^k }} + \sum\limits_{k = 1}^m {\frac{{d^k }}{{dt^k }}} A_{2k} (t)\frac{{d^k u}}{{dt^k }} + \lambda _m A_0 (t)u = f, \hfill \\ t \in ]0,t[,\lambda _m \geqslant 1, \hfill \\ {{d^i u} \mathord{\left/ {\vphantom {{d^i u} {dt^i }}} \right. \kern-\nulldelimiterspace} {dt^i }}|_{t = 0} = {{d^j u} \mathord{\left/ {\vphantom {{d^j u} {dt^j }}} \right. \kern-\nulldelimiterspace} {dt^j }}|_{t = T} = 0,i = 0,...,m,j = 0,...,m - 1,m = 0,1,..., \hfill \\ \end{gathered} $$

where the unbounded operators A _s (t), s > 0, in a Hilbert space H have domains D(A _s (t)) depending on t, are subordinate to the powers A ^1?(s?1)/2m (t) of some self-adjoint operators A(t) ≥ 0 in H, are [(s+1)/2] times differentiable with respect to t, and satisfy some inequalities. In the space H, the maximally accretive operators A ₀(t) and the symmetric operators A _s (t), s > 0, are approximated by smooth maximally dissipative operators B(t) in such a way that

$$\begin{gathered} \mathop {lim}\limits_{\varepsilon \to 0} Re(A_0 (t)B_\varepsilon ^{ - 1} (t)(B_\varepsilon ^{ - 1} (t))^ * u,u)_H = Re(A_0 (t)u,u)_H \geqslant c(A(t)u,u)_H \hfill \\ \forall u \in D(A_0 (t)),c > 0, \hfill \\ \end{gathered} $$

, where the smoothing operators are defined by

$$B_\varepsilon ^{ - 1} (t) = (I - \varepsilon B(t))^{ - 1} ,(B_\varepsilon ^{ - 1} (t)) * = (I - \varepsilon B^ * (t))^{ - 1} ,\varepsilon > 0.$$

.

     

On the Exact Maximum Complexity of Minkowski Sums of Polytopes

We present a tight bound on the exact maximum complexity of Minkowski sums of polytopes in ?³. In particular, we prove that the maximum number of facets of the Minkowski sum of k polytopes with m ₁,m ₂,…,m _k facets, respectively, is bounded from above by \(\sum_{1\leq i. Given k positive integers m ₁,m ₂,…,m _k , we describe how to construct k polytopes with corresponding number of facets, such that the number of facets of their Minkowski sum is exactly \(\sum_{1\leq i. When k=2, for example, the expression above reduces to 4m ₁ m ₂?9m ₁?9m ₂+26.     

An algorithmic approach to construct crystallizations of 3-manifolds from presentations of fundamental groups

We have defined the weight of the pair (〈S∣R〉,R) for a given presentation 〈S∣R〉 of a group, where the number of generators is equal to the number of relations. We present an algorithm to construct crystallizations of 3-manifolds whose fundamental group has a presentation with two generators and two relations. If the weight of (〈S∣R〉,R) is n, then our algorithm constructs all the n-vertex crystallizations which yield (〈S∣R〉,R). As an application, we have constructed some new crystallizations of 3-manifolds. We have generalized our algorithm for presentations with three generators and a certain class of relations. For m≥3 and m≥n≥k≥2, our generalized algorithm gives a \(2(2m+2n+2k-6+{\delta _{n}^{2}} + {\delta _{k}^{2}})\)-vertex crystallization of the closed connected orientable 3-manifold M〈m,n,k〉 having fundamental group \(\langle x_{1},x_{2},x_{3} \mid {x_{1}^{m}}={x_{2}^{n}}={x_{3}^{k}}=x_{1}x_{2}x_{3} \rangle \). These crystallizations are minimal and unique with respect to the given presentations. If ‘ n=2’ or ‘ k≥3 and m≥4’ then our crystallization of M〈m,n,k〉 is vertex-minimal for all the known cases.     

On the Second Parameter of an (<Emphasis Type="Italic">m</Emphasis>, <Emphasis Type="Italic">p</Emphasis>)-Isometry

A bounded linear operator T on a Banach space X is called an (m, p)-isometry if it satisfies the equation \({\sum_{k=0}^{m}(-1)^{k} {m \choose k}\|T^{k}x\|^{p}=0}\) , for all \({x \in X}\) . In this paper we study the structure which underlies the second parameter of (m, p)-isometric operators. We concentrate on determining when an (m, p)-isometry is a (μ, q)-isometry for some pair (μ, q). We also extend the definition of (m, p)-isometry, to include p = ∞ and study basic properties of these (m, ∞)-isometries.     

Proof of the Erdős matching conjecture in a new range

Let s > k ≧ 2 be integers. It is shown that there is a positive real ε = ε(k) such that for all integers n satisfying (s + 1)k ≦ n < (s + 1)(k + ε) every k-graph on n vertices with no more than s pairwise disjoint edges has at most \(\left( {\begin{array}{*{20}{c}} {\left( {s + 1} \right)k - 1} \\ k \end{array}} \right)\) edges in total. This proves part of an old conjecture of Erd?s.     

Rainbow matchings in bipartite multigraphs

Suppose that k is a non-negative integer and a bipartite multigraph G is the union of

$$\begin{aligned} N=\left\lfloor \frac{k+2}{k+1}n\right\rfloor -(k+1) \end{aligned}$$

matchings \(M_1,\dots ,M_N\), each of size n. We show that G has a rainbow matching of size \(n-k\), i.e. a matching of size \(n-k\) with all edges coming from different \(M_i\)’s. Several choices of the parameter k relate to known results and conjectures.

     

Standard monomials for <Emphasis Type="Italic">q</Emphasis>-uniform families and a conjecture of Babai and Frankl

Let n, k, α be integers, n, α>0, p be a prime and q=p ^α. Consider the complete q-uniform family

$\mathcal{F}\left( {k,q} \right) = \left\{ {K \subseteq \left[ n \right]:\left| K \right| \equiv k(mod q)} \right\}$

We study certain inclusion matrices attached to F(k,q) over the field\(\mathbb{F}_p \). We show that if l≤q?1 and 2l≤n then

$rank_{\mathbb{F}_p } I(\mathcal{F}(k,q),\left( {\begin{array}{*{20}c} {\left[ n \right]} \\ { \leqslant \ell } \\ \end{array} } \right)) \leqslant \left( {\begin{array}{*{20}c} n \\ \ell \\ \end{array} } \right)$

This extends a theorem of Frankl [7] obtained for the case α=1. In the proof we use arguments involving Gröbner bases, standard monomials and reduction. As an application, we solve a problem of Babai and Frankl related to the size of some L-intersecting families modulo q.     

Compound Geometric Distribution of Order <Emphasis Type="Italic">k</Emphasis>

The distribution of the number of trials until the first k consecutive successes in a sequence of Bernoulli trials with success probability p is known as geometric distribution of order k. Let T _k be a random variable that follows a geometric distribution of order k, and Y ₁,Y ₂,… a sequence of independent and identically distributed discrete random variables which are independent of T _k . In the present article we develop some results on the distribution of the compound random variable \(S_{k} =\sum_{t=1}^{T_{k}}Y_{t}\).     

Up-embeddability of graphs with new degree-sum

Let G be a k(k ≤ 2)-edge connected simple graph with minimal degree ≥ 3 and girth \(g,r = \left\lfloor {\frac{{g - 1}}{2}} \right\rfloor \). For any edge uv ∈ E(G), if

$${d_G}\left( u \right) + {d_G}\left( v \right) > \frac{{2v\left( G \right) - 2\left( {k + 1} \right)\left( {g - 2r} \right)}}{{\left( {k + 1} \right)\left( {{2^r} - 1} \right)\left( {g - 2r} \right)}} + 2\left( {g - 2r - 1} \right),$$

then G is up-embeddable. Furthermore, similar results for 3-edge connected simple graphs are also obtained.

     

Sobolev spaces and approximation by affine spanning systems

We develop conditions on a Sobolev function \(\psi \in W^{m,p}({\mathbb{R}}^d)\) such that if \(\widehat{\psi}(0) = 1\) and ψ satisfies the Strang–Fix conditions to order m ? 1, then a scale averaged approximation formula holds for all \(f \in W^{m,p}({\mathbb{R}}^d)\) :

$ f(x) = \lim_{J \to \infty} \frac{1}{J} \sum_{j=1}^{J} \sum_{k \in {{\mathbb{Z}}}^d} c_{j,k}\psi(a_j x - k) \quad {\rm in} W^{m, p}({{\mathbb{R}}}^d).$

The dilations { a _j } are lacunary, for example a _j =  2 ^j , and the coefficients c _j,k are explicit local averages of f, or even pointwise sampled values, when f has some smoothness. For convergence just in \({W^{m - 1,p}({\mathbb{R}}^d)}\) the scale averaging is unnecessary and one has the simpler formula \(f(x) = \lim_{j \to \infty} \sum_{k \in {\mathbb{Z}}^d} c_{j,k}\psi(a_j x - k)\) . The Strang–Fix rates of approximation are recovered. As a corollary of the scale averaged formula, we deduce new density or “spanning” criteria for the small scale affine system \(\{\psi(a_j x - k) : j > 0, k \in {\mathbb{Z}}^d \}\) in \(W^{m,p}({\mathbb{R}}^d)\) . We also span Sobolev space by derivatives and differences of affine systems, and we raise an open problem: does the Gaussian affine system span Sobolev space?

     

The <Emphasis Type="Italic">p</Emphasis>-adic order of some fibonomial coefficients whose entries are powers of <Emphasis Type="Italic">p</Emphasis>

Let (F _n ) _n≥0 be the Fibonacci sequence. For 1 ≤ k ≤ m, the Fibonomial coefficient is defined as

$${\left[ {\begin{array}{*{20}{c}} m \\ k \end{array}} \right]_F} = \frac{{{F_{m - k + 1}} \cdots {F_{m - 1}}{F_m}}}{{{F_1} \cdots {F_k}}}$$

. In 2013, Marques, Sellers and Trojovský proved that if p is a prime number such that p ≡ ±2 (mod 5), then \(p{\left| {\left[ {\begin{array}{*{20}{c}} {{p^{a + 1}}} \\ {{p^a}} \end{array}} \right]} \right._F}\) for all integers a ≥ 1. In 2015, Marques and Trojovský worked on the p-adic order of \({\left[ {\begin{array}{*{20}{c}} {{p^{a + 1}}} \\ {{p^a}} \end{array}} \right]_F}\) for all a ≥ 1 when p ≠ 5. In this paper, we shall provide the exact p-adic order of \({\left[ {\begin{array}{*{20}{c}} {{p^{a + 1}}} \\ {{p^a}} \end{array}} \right]_F}\) for all integers a, b ≥ 1 and for all prime number p.

     

A Rolle Type Theorem for Cyclicity of Zeros of Families of Analytic Functions

Let \({\{ {f_{\lambda ;j}}\} _{\lambda \in V;1 \leqslant j \leqslant k}}\) be families of holomorphic functions in the open unit disk \({\text{D}} \subset {\Bbb C}\) ? ? depending holomorphically on a parameter λ ∈ V ? ? ⁿ . We establish a Rolle type theorem for the generalized multiplicity (called cyclicity) of zeros of the family of univariate holomorphic functions \({\left\{ {\sum\nolimits_{j = 1}^k {{f_{\lambda ;j}}} } \right\}_{\lambda \in V}}\) at 0 ∈ D. As a corollary, we estimate the cyclicity of the family of generalized exponential polynomials, that is, the family of entire functions of the form \(\sum\nolimits_{k = 1}^m {{P_k}(z){e^{{Q_k}(z)}}} \), z ∈ ?, where P _k and Q _k are holomorphic polynomials of degrees p and q, respectively, parameterized by vectors of coefficients of P _k and Q _k .     

A note on the normalizing sequences for sums of linear processes in the case of negative memory

We consider the partial-sum process \( {S}_n(t)={\sum}_{k=0}^{\left\lfloor nt\right\rfloor }{X}_k \) of linear processes \( {X}_n={\sum}_{i=0}^{\infty }{c}_i{\upxi}_{n-i} \) with independent identically distributed innovations {ξ _i } belonging to the domain of attraction of α-stable law (0 < α ≤ 2). If |c _k |?=?k ^?γ?,?k?∈???,?γ?> max(1, 1/α), and \( {\sum}_{k=0}^{\infty}\kern0.5em ck=0 \) (the case of negative memory for the stationary sequence {X _n }), then it is known that the normalizing sequence of S _n (1) can grow as n ^1/α?γ+1 or remain bounded if the signs of the coefficients are constant or alternate, respectively. It is of interest to know whether it is possible, given ? ∈ (0, 1/α ? γ + 1), to change the signs of c _k so that the rate of growth of the normalizing sequence would be n ^? . In this paper, we give the positive answer: we propose a way of choosing the signs and investigate the finite-dimensional convergence of appropriately normalized S _n (t) to linear fractional Lévy motion.     

Divided differences for functions of two variables for irregularly spaced arguments

Divided differences forf (x, y) for completely irregular spacing of points (x _i ,y _i ) are developed here by a natural generalization of Newton's scheme. Existing bivariate schemes either iterate the one-dimensional scheme, thus constraining (x _i ,y _i ) to be at corners of rectangles, or give polynomials Σa _jk x ^j y ^k having more coefficients than interpolation conditions. Here the generalizedn ^th divided difference is defined by (1)\(\left[ {01... n} \right] = \sum\limits_{i = 0}^n {A_i f\left( {x_i , y_i } \right)} \) where (2)\(\sum\limits_{i = 0}^n {A_i x_i^j , y_i^k = 0} \), and 1 for the last or (n+1)^th equation, for every (j, k) wherej+k=0, 1, 2,... in the usual ascending order. The gen. div. diff. [01...n] is symmetric in (x _i ,y _i ), unchanged under translation, 0 forf (x, y) an, ascending binary polynomial as far asn terms, degree-lowering with respect to (X, Y) whenf(x, y) is any polynomialP(X+x, Y+y), and satisfies the 3-term recurrence relation (3) [01...n]=λ{[1...n]?[0...n?1]}, where (4) λ= |1...n|·|01...n?1|/|01...n|·|1...n?1|, the |...i...| denoting determinants inx _i ^j y _i ^k . The generalization of Newton's div. diff. formula is (5)

$$\begin{gathered} f\left( {x, y} \right) = f\left( {x_0 , y_0 } \right) - \frac{{\left| {\alpha 0} \right|}}{{\left| 0 \right|}}\left[ {01} \right] + \frac{{\left| {\alpha 01} \right|}}{{\left| {01} \right|}}\left[ {012} \right] - \frac{{\left| {\alpha 012} \right|}}{{\left| {012} \right|}}\left[ {0123} \right] + \cdots + \hfill \\ + \left( { - 1} \right)^n \frac{{\left| {\alpha 01 \ldots n - 1} \right|}}{{\left| {01 \ldots n - 1} \right|}}\left[ {01 \ldots n} \right] + \left( { - 1} \right)^{n + 1} \frac{{\left| {\alpha 01 \ldots n} \right|}}{{\left| {01 \ldots n} \right|}}\left[ {01 \ldots n} \right], \hfill \\ \end{gathered} $$     

On the application of linear positive operators for approximation of functions

For the linear positive Korovkin operator \(f\left( x \right) \to {t_n}\left( {f;x} \right) = \frac{1}{\pi }\int_{ - \pi }^\pi {f\left( {x + t} \right)E\left( t \right)dt} \), where E(x) is the Egervary–Szász polynomial and the corresponding interpolation mean \({t_{n,N}}\left( {f;x} \right) = \frac{1}{N}\sum\limits_{k = - N}^{N - 1} {{E_n}\left( {x - \frac{{\pi k}}{N}} \right)f\left( {\frac{{\pi k}}{N}} \right)} \), the Jackson-type inequalities \(\left\| {{t_{n,N}}\left( {f;x} \right) - f\left( x \right)} \right\| \leqslant \left( {1 + \pi } \right){\omega _f}\left( {\frac{1}{n}} \right),\left\| {{t_{n,N}}\left( {f;x} \right) - f\left( x \right)} \right\| \leqslant 2{\omega _f}\left( {\frac{\pi }{{n + 1}}} \right)\), where ωf (x) denotes the modulus of continuity, are proved for N > n/2. For ωf (x) ≤ Mx, the inequality \(\left\| {{t_{n,N}}\left( {f;x} \right) - f\left( x \right)} \right\| \leqslant \frac{{\pi M}}{{n + 1}}\). is established. As a consequence, an elementary derivation of an asymptotically sharp estimate of the Kolmogorov width of a compact set of functions satisfying the Lipschitz condition is obtained.     

On a Congruence Involving Generalized Fibonomial Coefficients

Let (F_n)_n≥0 be the Fibonacci sequence. For 1 ≤ k ≤ m, the Fibonomial coefficient is defined as

$${\left[ {\begin{array}{*{20}{c}} n \\ k \end{array}} \right]_F} = \frac{{{F_{n - k + 1}} \cdots {F_{n - 1}}{F_n}}}{{{F_1} \cdots {F_k}}}$$

. In 2013, Marques, Sellers and Trojovský proved that if p is a prime number such that p ≡ ±1 (mod 5), then p?\({\left[ {\begin{array}{*{20}{c}} {{p^{a + 1}}} \\ {{p^a}} \end{array}} \right]_F}\) for all integers a ≥ 1. In 2010, in particular, Kilic generalized the Fibonomial coefficients for

$${\left[ {\begin{array}{*{20}{c}} n \\ k \end{array}} \right]_{F,m}} = \frac{{{F_{\left( {n - k + 1} \right)m}} \cdots {F_{\left( {n - 1} \right)m}}{F_{nm}}}}{{{F_m} \cdots {F_{km}}}}$$

. In this note, we generalize Marques, Sellers and Trojovský result to prove, in particular, that if p ≡ ±1 (mod 5), then \({\left[ {\begin{array}{*{20}{c}} {{p^{a + 1}}} \\ {{p^a}} \end{array}} \right]_{F,m}} \equiv 1\) (mod p), for all a ≥ 0 and m ≥ 1.