Selections of bounded variation under the excess restrictions

Let X be a metric space with metric d, c(X) denote the family of all nonempty compact subsets of X and, given F,G∈c(X), let e(F,G)=supx∈Finfy∈Gd(x,y) be the Hausdorff excess of F over G. The excess variation of a multifunction , which generalizes the ordinary variation V of single-valued functions, is defined by where the supremum is taken over all partitions of the interval [a,b]. The main result of the paper is the following selection theorem: If,V₊(F,[a,b])<∞,t₀∈[a,b]andx₀∈F(t₀), then there exists a single-valued functionof bounded variation such thatf(t)∈F(t)for allt∈[a,b],f(t₀)=x₀,V(f,[a,t₀))?V₊(F,[a,t₀))andV(f,[t₀,b])?V₊(F,[t₀,b]). We exhibit examples showing that the conclusions in this theorem are sharp, and that it produces new selections of bounded variation as compared with [V.V. Chistyakov, Selections of bounded variation, J. Appl. Anal. 10 (1) (2004) 1-82]. In contrast to this, a multifunction F satisfying e(F(s),F(t))?C(t−s) for some constant C?0 and all s,t∈[a,b] with s?t (Lipschitz continuity with respect to e(⋅,⋅)) admits a Lipschitz selection with a Lipschitz constant not exceeding C if t₀=a and may have only discontinuous selections of bounded variation if a<t₀?b. The same situation holds for continuous selections of when it is excess continuous in the sense that e(F(s),F(t))→0 as s→t−0 for all t∈(a,b] and e(F(t),F(s))→0 as s→t+0 for all t∈[a,b) simultaneously.     

Coefficients of multivalent symmetric functions of bounded boundary rotation

In this paper the sharp coefficient estimate problem for the classesC _p(β, m) andV _p(k,m) of multivalent close-to-convex functions of order β and multivalent functions of bounded boundary rotation of at mostkπ, whose functions are given bym-fold symmetric gap series, have been discussed respectively for β≥1?p/m>0 andk≥2(m/p). Moreover, it is shown that every function inV _p(k,m) arep-valent close-to-convex; hencep-valent; ifk<2 (1+m/p).     

Counting truth assignments of formulas of bounded tree-width or clique-width

We study algorithms for ?SAT and its generalized version ?GENSAT, the problem of computing the number of satisfying assignments of a set of propositional clauses Σ. For this purpose we consider the clauses given by their incidence graph, a signed bipartite graph SI(Σ), and its derived graphs I(Σ) and P(Σ).It is well known, that, given a graph of tree-width k, a k-tree decomposition can be found in polynomial time. Very recently Oum and Seymour have shown that, given a graph of clique-width k, a (2^3k+2-1)-parse tree witnessing clique-width can be found in polynomial time.In this paper we present an algorithm for ?GENSAT for formulas of bounded tree-width k which runs in time 4^k(n+n²·log₂(n)), where n is the size of the input. The main ingredient of the algorithm is a splitting formula for the number of satisfying assignments for a set of clauses Σ where the incidence graph I(Σ) is a union of two graphs G₁ and G₂ with a shared induced subgraph H of size at most k. We also present analogue improvements for algorithms for formulas of bounded clique-width which are given together with their derivation.This considerably improves results for ?SAT, and hence also for SAT, previously obtained by Courcelle et al. [On the fixed parameter complexity of graph enumeration problems definable in monadic second order logic, Discrete Appl. Math. 108 (1-2) (2001) 23-52].     

Structure of cubic mapping graphs for the ring of Gaussian integers modulo n

Let ? _n [i] be the ring of Gaussian integers modulo n. We construct for ?n[i] a cubic mapping graph Γ(n) whose vertex set is all the elements of ?n[i] and for which there is a directed edge from a ∈ ?n[i] to b ∈ ?n[i] if b = a ³. This article investigates in detail the structure of Γ(n). We give suffcient and necessary conditions for the existence of cycles with length t. The number of t-cycles in Γ₁(n) is obtained and we also examine when a vertex lies on a t-cycle of Γ₂(n), where Γ₁(n) is induced by all the units of ?n[i] while Γ₂(n) is induced by all the zero-divisors of ?n[i]. In addition, formulas on the heights of components and vertices in Γ(n) are presented.     

Selection principle for pointwise bounded sequences of functions

For a number ? > 0 and a real function f on an interval [a, b], denote by N(?, f, [a, b]) the least upper bound of the set of indices n for which there is a family of disjoint intervals [a _i , b _i ], i = 1, …, n, on [a, b] such that |f(a _i ) ? f(b _i )| > ? for any i = 1, …, n (sup Ø = 0). The following theorem is proved: if {f _j } is a pointwise bounded sequence of real functions on the interval [a, b] such that n(?) ≡ lim sup _j→∞ N(?, f _j , [a, b]) < ∞ for any ? > 0, then the sequence {f _j } contains a subsequence which converges, everywhere on [a, b], to some function f such that N(?, f, [a, b]) ≤ n(?) for any ? > 0. It is proved that the main condition in this theorem related to the upper limit is necessary for any uniformly convergent sequence {f _j } and is “almost” necessary for any everywhere convergent sequence of measurable functions, and many pointwise selection principles generalizing Helly’s classical theorem are consequences of our theorem. Examples are presented which illustrate the sharpness of the theorem.     

Rearrangements of bounded variation sequences

Letbv be the set of all bounded variation sequences. In the present paper we deduce from a theorem of Mears a necessary and sufficient condition for the rearrangement (a _p(k)) to be of bounded variation whenevera _k)∈bv; interestingly it coincides with Pleasants’ criterion for convergence-preserving.     

Degree conditions and degree bounded trees

We give sufficient conditions for a graph to have degree bounded trees. Let G be a connected graph and A a vertex subset of G. We denote by σ_k(A) the minimum value of the degree sum in G of any k independent vertices in A and by w(G−A) the number of components in the induced subgraph G−A. Our main results are the following: (i) If σ_k(A)≥|V(G)|−1, then G contains a tree T with maximum degree at most k and A⊆V(T). (ii) If σ_k−w(G−A)(A)≥|A|−1, then G contains a spanning tree T such that d_T(x)≤k for every x∈A. These are generalizations of the result by Win [S. Win, Existenz von Gerüsten mit Vorgeschriebenem Maximalgrad in Graphen, Abh. Math. Sem. Univ. Hamburg 43 (1975) 263-267] and the degree conditions are sharp.     

Colouring graphs with bounded generalized colouring number

Given a graph G and a positive integer p, χ_p(G) is the minimum number of colours needed to colour the vertices of G so that for any i≤p, any subgraph H of G of tree-depth i gets at least i colours. This paper proves an upper bound for χ_p(G) in terms of the k-colouring number of G for k=2^p−2. Conversely, for each integer k, we also prove an upper bound for in terms of χ_k+2(G). As a consequence, for a class K of graphs, the following two statements are equivalent:

(a)

For every positive integer p, χ_p(G) is bounded by a constant for all G∈K.

(b)

For every positive integer k, is bounded by a constant for all G∈K.

It was proved by Nešet?il and Ossona de Mendez that (a) is equivalent to the following:

(c)

For every positive integer q, ∇_q(G) (the greatest reduced average density of G with rank q) is bounded by a constant for all G∈K.

Therefore (b) and (c) are also equivalent. We shall give a direct proof of this equivalence, by introducing ∇_q−(1/2)(G) and by showing that there is a function F_k such that . This gives an alternate proof of the equivalence of (a) and (c).     

Homomorphisms and composition operators on algebras of analytic functions of bounded type

Let U and V be convex and balanced open subsets of the Banach spaces X and Y, respectively. In this paper we study the following question: given two Fréchet algebras of holomorphic functions of bounded type on U and V, respectively, that are algebra isomorphic, can we deduce that X and Y (or X^* and Y^*) are isomorphic? We prove that if X^* or Y^* has the approximation property and H_wu(U) and H_wu(V) are topologically algebra isomorphic, then X^* and Y^* are isomorphic (the converse being true when U and V are the whole space). We get analogous results for H_b(U) and H_b(V), giving conditions under which an algebra isomorphism between H_b(X) and H_b(Y) is equivalent to an isomorphism between X^* and Y^*. We also obtain characterizations of different algebra homomorphisms as composition operators, study the structure of the spectrum of the algebras under consideration and show the existence of homomorphisms on H_b(X) with pathological behaviors.     

Global well-posedness for the density-dependent incompressible magnetohydrodynamic flows in bounded domains

In this paper, we study the three-dimensional incompressible magnetohydrodynamic equations in a smooth bounded domains, in which the viscosity of the fluid and the magnetic diffusivity are concerned with density. The existence of global strong solutions is established in vacuum cases, provided the assumption that(|| ?μ(ρ0)|| Lp +|| ?ν(ρ0) ||Lq + ||b0|| L3+ ||ρ0|| L∞)(p, q 3) is small enough, there is not any smallness condition on the velocity.     

Covering the vertices of a graph with cycles of bounded length

Let c_k(G) be the minimum number of elementary cycles of length at most k necessary to cover the vertices of a given graph G. In this work, we bound c_k(G) by a function of the order of G and its independence number.     

On almost good triples of vertices in edge regular graphs

Consider a connected edge regular graph Γ with parameters (v, k, λ) and put b ₁ = k?λ?1. A triple (u, w, z) of vertices is called (almost) good whenever d(u, w) = d(u, z) = 2 and µ(u, w)+µ(u, z) ≤ 2k ? 4b ₁ + 3 (and µ(u, w) + µ(u, z) = 2k ? 4b ₁ + 4). If k = 3b ₁ + γ with γ ≥ ?2, a triple (u, w, z) is almost good, and Δ = [u] ∩ [w] ∩ [z] then: either |Δ| ≤ 2; or Δ is a 3-clique and Γ is a Clebsch graph; or Δ is a 3-clique, k = 16, b ₁ = 6, and v = 31; or Δ is a 4-clique and Γ is a Schläfli graph.     

On the law of the iterated logarithm for trigonometric series with bounded gaps

Let (n _k ) _k??1 be an increasing sequence of positive integers. Bobkov and G?tze proved that if the distribution of $$\label{distr}\frac{\cos 2\pi n_1 x + \cdots +\cos 2 \pi n_N x}{\sqrt{N}}\qquad\quad\quad\quad (1)$$ converges to a Gaussian distribution, then the value of the variance is bounded from above by 1/2 ? lim sup k/(2n _k ). In particular it is impossible that for a sequence (n _k ) _k??1 with bounded gaps (i.e. n _k+1 ? n _k ?? c for some constant c) the distribution of (1) converges to a Gaussian distribution with variance ?? ²?=?1/2 or larger. In this paper we show that the situation is considerably different in the case of the law of the iterated logarithm. We prove the existence of an increasing sequence of positive integers satisfying $$n_{k+1} - n_k \leq 2$$ such that $$\limsup_{N \to \infty}\frac{\sum_{k=1}^N \cos 2 \pi n_k x}{\sqrt{2N \log \log N}} = +\infty \quad {a.e.}$$      

Resource augmented semi-online bounded space bin packing

We study on-line bounded space bin-packing in the resource augmentation model of competitive analysis. In this model, the on-line bounded space packing algorithm has to pack a list L of items with sizes in (0, 1], into a minimum number of bins of size b, b≥1. A bounded space algorithm has the property that it only has a constant number of active bins available to accept items at any point during processing. The performance of the algorithm is measured by comparing the produced packing with an optimal offline packing of the list L into bins of size 1. The competitive ratio then becomes a function of the on-line bin size b. Csirik and Woeginger studied this problem in [J. Csirik, G.J. Woeginger, Resource augmentation for online bounded space bin packing, Journal of Algorithms 44(2) (2002) 308-320] and proved that no on-line bounded space algorithm can perform better than a certain bound ρ(b) in the worst case. We relax the on-line condition by allowing a complete repacking within the active bins, and show that the same lower bound holds for this problem as well, and repacking may only allow one to obtain the exact best possible competitive ratio of ρ(b) having a constant number of active bins, instead of achieving this bound in the limit. We design a polynomial time on-line algorithm that uses three active bins and achieves the exact best possible competitive ratio ρ(b) for the given problem.     

Taylor series and divisibility

LetA be an augmentedK-algebra; defineT:A →A ?k _kA byT(a)=1?a ?a?1,a ∈A. We prove, under some conditions, thatg is in the subalgebraK[f] ofA generated byf if and only ifT(g) is in the principal ideal generated byT(f) inA?k _kA. WhenA=K[[X]],T(f) is a multiple ofT(X) if and only iff belongs to the ringL obtained by localizingK[X] at (X).     

On the length of optimal TSP circuits in sets of bounded diameter

Let V be a set of n points in R^k. Let d(V) denote the diameter of V, and l(V) denote the length of the shortest circuit which passes through all the points of V. (Such a circuit is an “optimal TSP circuit”.) l^k(n) are the extremal values of l(V) defined by l^k(n)=max{l(V)|V∈V_n^k}, where V_n^k={V|V?R^k,|V|=n, d(V)=1}. A set V∈V_n^k is “longest” if l(V)=l^k(n). In this paper, first some geometrical properties of longest sets in R² are studied which are used to obtain l²(n) for small n′s, and then asymptotic bounds on l^k(n) are derived. Let δ(V) denote the minimal distance between a pair of points in V, and let: δ^k(n)=max{δ(V)|V∈V_n^k}. It is easily observed that $\text{δ}{}^{\mathrm{k}}\text{(n)=O(n}{}^{\mathrm{<mtext>?1</mtext><mtext>k</mtext>}}\text{)}$. Hence, $\text{c}{}_{\mathrm{k}}\text{=}\text{lim sup}{}_{\mathrm{n\to \infty }}\text{δ}{}^{\mathrm{k}}\text{(n)n}{}^{\mathrm{<mtext>1</mtext><mtext>k</mtext>}}$ exists. It is shown that for all $\text{n, c}{}_{\mathrm{k}}\text{n}{}^{\mathrm{<mtext>?1</mtext><mtext>k</mtext>}}\text{≤δ}{}^{\mathrm{k}}\text{(n)}$, and hence, for all $\text{n, l}{}^{\mathrm{k}}\text{(n)≥ c}{}_{\mathrm{k}}\text{n}{}^{\mathrm{<mtext>1?1</mtext><mtext>k</mtext>}}$. For k=2, this implies that $\text{l}{}^2\text{(n)≥(}\text{π}{}^2\text{12}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>4</mtext>}}\text{n}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$, which generalizes an observation of Fejes-Toth that $\text{lim}{}_{\mathrm{n\to \infty }}\text{l}{}^2\text{(n)n}{}^{\mathrm{<mtext>?1</mtext><mtext>2</mtext>}}\text{≥(}\text{π}{}^2\text{12}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>4</mtext>}}$. It is also shown that $\text{l}{}^{\mathrm{k}}\text{(n) ≤ [}\text{(3?√3)k}\text{(k?1)}\text{]nδ}{}^{\mathrm{k}}\text{(n) + o(n}{}^{\mathrm{<mtext>1?</mtext><mtext>1</mtext><mtext>k</mtext>}}\text{) ≤ [}\text{(3?√3)k}\text{(k?1)}\text{]n}{}^{\mathrm{<mtext>1?</mtext><mtext>1</mtext><mtext>k</mtext>}}\text{+ o(n}{}^{\mathrm{<mtext>1?</mtext><mtext>1</mtext><mtext>k</mtext>}}\text{)}$. The above upper bound is used to improve related results on longest sets in k-dimensional unit cubes obtained by Few (Mathematika2 (1955), 141–144) for almost all k′s. For k=2, Few's technique is used to show that $\text{l}{}^2\text{(n)≤(}\text{πn}\text{2}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{+ O(1)}$.     

On the distinguished character of the function spaces of holomorphic mappings of bounded type

Given two complex normed spaces E and F, F complete, and a balanced open subset U of E, we prove that the space $\text{H}$_(b(U, F) of the holomorphic mappings f: U → F of bounded type, endowed with its natural topology τ_b, is a distinguished quasi-normable Fréchet space, which is not a Schwartz space unless dim E < ∞ and dim F < ∞.     

Identification of the unknown diffusion coefficient in a linear parabolic equation by the semigroup approach

In this article, we study the semigroup approach for the mathematical analysis of the inverse coefficient problems of identifying the unknown coefficient k(x) in the linear parabolic equation ut(x,t)=(k(x)uxx(x,t)), with Dirichlet boundary conditions u(0,t)=ψ₀, u(1,t)=ψ₁. Main goal of this study is to investigate the distinguishability of the input-output mappings Φ[⋅]:K→C¹[0,T], Ψ[⋅]:K→C¹[0,T] via semigroup theory. In this paper, we show that if the null space of the semigroup T(t) consists of only zero function, then the input-output mappings Φ[⋅] and Ψ[⋅] have the distinguishability property. Moreover, the values k(0) and k(1) of the unknown diffusion coefficient k(x) at x=0 and x=1, respectively, can be determined explicitly by making use of measured output data (boundary observations) f(t):=k(0)ux(0,t) or/and h(t):=k(1)ux(1,t). In addition to these, the values k^′(0) and k^′(1) of the unknown coefficient k(x) at x=0 and x=1, respectively, are also determined via the input data. Furthermore, it is shown that measured output dataf(t) and h(t) can be determined analytically, by an integral representation. Hence the input-output mappings Φ[⋅]:K→C¹[0,T], Ψ[⋅]:K→C¹[0,T] are given explicitly in terms of the semigroup. Finally by using all these results, we construct the local representations of the unknown coefficient k(x) at the end points x=0 and x=1.     

Polynomials generalizing binomial coefficients and their application to the study of Fermat's last theorem

We study properties of the polynomials φ_k(X) which appear in the formal development Π_{k ? 0}ⁿ (a + bX^k)^rk = Σ_{k ≥ 0}φ_k(X) a^{r ? k}b^k, where r_k ∈ $\text{l}$ and r = Σr_k. this permits us to obtain the coefficients of all cyclotomic polynomials. Then we use these properties to expand the cyclotomic numbers G_r(ξ) = Π_{k = 1}^{p ? 1} (a + bξ^k)^kr, where p is a prime, ξ is a primitive pth root of 1, a, b ∈ $\text{l}$ and 1 ≤ r ≤ p ? 3, modulo powers of ξ ? 1 (until (ξ ? 1)^{2(p ? 1) ? r}). This gives more information than the usual logarithmic derivative. Suppose that $\text{p ? ab(a + b)}$. Let $\text{m = ?}\text{b}\text{a}$. We prove that G_r(ξ) ≡ c^p mod p(ξ ? 1)² for some c ∈ $\text{l}$, if and only if Σ_{k = 1}^{p ? 1}k^{p ? 2 ? r}m^k ≡ 0 (mod p). We hope to show in this work that this result is useful in the study of the first case of Fermat's last theorem.