Majors of Functions

We investigate the minor order of functions, focusing on upper covers and common upper bounds of pairs of functions. We show that two functions of arities m and n have a common upper bound if and only if they have a common lower bound, and if a common upper bound exists, then there is one of arity m + n ? 1. Moreover, we determine the possible essential arities of upper covers of functions.     

Upper bounds on the length of a shortest closed geodesic and quantitative Hurewicz theorem

In this paper we present two upper bounds on the length of a shortest closed geodesic on compact Riemannian manifolds. The first upper bound depends on an upper bound on sectional curvature and an upper bound on the volume of the manifold. The second upper bound will be given in terms of a lower bound on sectional curvature, an upper bound on the diameter and a lower bound on the volume.The related questions that will also be studied are the following: given a contractible k-dimensional sphere in M ⁿ , how “fast” can this sphere be contracted to a point, if π _i (M ⁿ )={0} for 1≤i<k. That is, what is the maximal length of the trajectory described by a point of a sphere under an “optimal” homotopy? Also, what is the “size” of the smallest non-contractible k-dimensional sphere in a (k-1)-connected manifold M ⁿ providing that M ⁿ is not k-connected?     

Some refined bounds for the perturbation of the orthogonal projection and the generalized inverse

In this paper, we consider the perturbation of the orthogonal projection and the generalized inverse for an n × n matrix A and present some perturbation bounds for the orthogonal projections on the rang spaces of A and A^?, respectively. A combined bound for the orthogonal projection on the rang spaces of A and A^? is also given. The proposed bounds are sharper than the existing ones. From the combined bounds of the orthogonal projection on the rang spaces of A and A^?, we derived new perturbation bounds for the generalized inverse, which always improve the existing ones. The combined perturbation bound for the orthogonal projection and the generalized inverse is also given. Some numerical examples are given to show the advantage of the new bounds.     

The Webster Scalar Curvature and Sharp Upper and Lower Bounds for the First Positive Eigenvalue of the Kohn-Laplacian on Real Hypersurfaces

Let(M, θ) be a compact strictly pseudoconvex pseudohermitian manifold which is CR embedded into a complex space. In an earlier paper, Lin and the authors gave several sharp upper bounds for the first positive eigenvalue λ_1 of the Kohn-Laplacian □_b on(M, θ). In the present paper, we give a sharp upper bound for λ_1, generalizing and extending some previous results. As a corollary, we obtain a Reilly-type estimate when M is embedded into the standard sphere. In another direction, using a Lichnerowicz-type estimate by Chanillo, Chiu, and Yang and an explicit formula for the Webster scalar curvature, we give a lower bound for λ_1 when the pseudohermitian structure θ is volume-normalized.     

Subgroup normality degrees of finite groups I

In this paper, we introduce the probability that a subgroup H of a finite group G can be normal in G, the subgroup normality degree of H in G, as the ratio of the number of all pairs \({(h, g)\in H\times G}\) such that \({h^g\in H}\) by |H||G|. We give some upper and lower bounds for this probability and obtain the upper bound \({\frac{8}{15}}\) for nontrivial subgroups of finite simple groups. In addition, we obtain explicit formulas for subgroup normality degrees of some particular classes of finite groups.     

On the optimality and sharpness of Laguerre’s lower bound on the smallest eigenvalue of a symmetric positive definite matrix

Lower bounds on the smallest eigenvalue of a symmetric positive definite matrix A ∈ R ^m×m play an important role in condition number estimation and in iterative methods for singular value computation. In particular, the bounds based on Tr(A ^?1) and Tr(A ^?2) have attracted attention recently, because they can be computed in O(m) operations when A is tridiagonal. In this paper, we focus on these bounds and investigate their properties in detail. First, we consider the problem of finding the optimal bound that can be computed solely from Tr(A ^?1) and Tr(A ^?2) and show that the so called Laguerre’s lower bound is the optimal one in terms of sharpness. Next, we study the gap between the Laguerre bound and the smallest eigenvalue. We characterize the situation in which the gap becomes largest in terms of the eigenvalue distribution of A and show that the gap becomes smallest when {Tr(A ^?1)}²/Tr(A ^?2) approaches 1 or m. These results will be useful, for example, in designing efficient shift strategies for singular value computation algorithms.     

The number of 2-sat functions

Our aim in this paper is to address the following question: of the 2^{2 n} Boolean functions onn variables, how many are expressible as 2-SAT formulae? In other words, we wish to count the number of different instances of 2-SAT, counting two instances as equivalent if they have the same set of satisfying assignments. Viewed geometrically, we are asking for the number of subsets of then-dimensional discrete cube that are unions of (n-2)-dimensional subcubes.There is a trivial upper bound of 2^4(n/2), the number of 2-SAT formulae. There is also an obvious lower bound of 2^(n/2), corresponding to the monotone 2-SAT formulae. Our main result is that, rather surprisingly, this lower bound gives the correct speed: the number of 2-SAT functions is 2^(1+0(1)) n ^{2 2}.     

Bounds and constructions of <Emphasis Type="Italic">t</Emphasis>-spontaneous emission error designs

The combinatorial aspects of quantum codes were demonstrated in the study of decay processes of certain quantum systems used in the newly emerging field of quantum computing. Among them, the configuration of t-spontaneous emission error design (t-SEED) was proposed to correct errors caused by quantum jumps. The number of designs (dimension) in a t-SEED corresponds to the number of orthogonal basis states in a quantum jump code. In this paper the upper and lower bounds on the dimensions of 3-\((v,\,4;\,m)\) SEEDs are studied and the necessary and sufficient conditions for 3-SEEDs attaining the upper bounds are described. Several new combinatorial constructions are presented for general t-SEEDs and lots of t-SEEDs of new parameters with \(t\ge 3\) are shown to exist.     

Estimating linear functionals of a sparse family of Poisson means

Assume that we observe a sample of size n composed of p-dimensional signals, each signal having independent entries drawn from a scaled Poisson distribution with an unknown intensity. We are interested in estimating the sum of the n unknown intensity vectors, under the assumption that most of them coincide with a given “background” signal. The number s of p-dimensional signals different from the background signal plays the role of sparsity and the goal is to leverage this sparsity assumption in order to improve the quality of estimation as compared to the naive estimator that computes the sum of the observed signals. We first introduce the group hard thresholding estimator and analyze its mean squared error measured by the squared Euclidean norm. We establish a nonasymptotic upper bound showing that the risk is at most of the order of \(\sigma ^2(sp+s^2\sqrt{p}\log ^{3/2}(np))\). We then establish lower bounds on the minimax risk over a properly defined class of collections of s-sparse signals. These lower bounds match with the upper bound, up to logarithmic terms, when the dimension p is fixed or of larger order than \(s^2\). In the case where the dimension p increases but remains of smaller order than \(s^2\), our results show a gap between the lower and the upper bounds, which can be up to order \(\sqrt{p}\).     

On reliability analysis of consecutive k-out-of-n systems with arbitrarily dependent components

In this paper, we consider the linear and circular consecutive k-out-of-n systems consisting of arbitrarily dependent components. Under the condition that at least n?r+1 components (r ≤ n) of the system are working at time t, we study the reliability properties of the residual lifetime of such systems. Also, we present some stochastic ordering properties of residual lifetime of consecutive k-out-of-n systems. In the following, we investigate the inactivity time of the component with lifetime T_r:n at the system level for the consecutive k-out-of-n systems under the condition that the system is not working at time t > 0, and obtain some stochastic properties of this conditional random variable.     

Sums and differences of four <Emphasis Type="Italic">k</Emphasis>th powers

We prove an upper bound for the number of representations of a positive integer N as the sum of four kth powers of integers of size at most B, using a new version of the determinant method developed by Heath-Brown, along with recent results by Salberger on the density of integral points on affine surfaces. More generally we consider representations by any integral diagonal form. The upper bound has the form \({O_{N}(B^{c/\sqrt{k}})}\), whereas earlier versions of the determinant method would produce an exponent for B of order k ^?1/3 (uniformly in N) in this case. Furthermore, we prove that the number of representations of a positive integer N as a sum of four kth powers of non-negative integers is at most \({O_{\varepsilon}(N^{1/k+2/k^{3/2}+\varepsilon})}\) for k ≥ 3, improving upon bounds by Wisdom.     

New upper bounds for parent-identifying codes and traceability codes

In the last two decades, parent-identifying codes and traceability codes are introduced to prevent copyrighted digital data from unauthorized use. They have important applications in the scenarios like digital fingerprinting and broadcast encryption schemes. A major open problem in this research area is to determine the upper bounds for the cardinalities of these codes. In this paper we will focus on this theme. Consider a code of length N which is defined over an alphabet of size q. Let \(M_{IPPC}(N,q,t)\) and \(M_{TA}(N,q,t)\) denote the maximal cardinalities of t-parent-identifying codes and t-traceability codes, respectively, where t is known as the strength of the codes. We show \(M_{IPPC}(N,q,t)\le rq^{\lceil N/(v-1)\rceil }+(v-1-r)q^{\lfloor N/(v-1)\rfloor }\), where \(v=\lfloor (t/2+1)^2\rfloor \), \(0\le r\le v-2\) and \(N\equiv r \mod (v-1)\). This new bound improves two previously known bounds of Blackburn, and Alon and Stav. On the other hand, \(M_{TA}(N,q,t)\) is still not known for almost all t. In 2010, Blackburn, Etzion and Ng asked whether \(M_{TA}(N,q,t)\le cq^{\lceil N/t^2\rceil }\) or not, where c is a constant depending only on N, and they have shown the only known validity of this bound for \(t=2\). By using some complicated combinatorial counting arguments, we prove this bound for \(t=3\). This is the first non-trivial upper bound in the literature for traceability codes with strength three.     

On a novel eccentricity-based invariant of a graph

In this paper,for the purpose of measuring the non-self-centrality extent of non-selfcentered graphs,a novel eccentricity-based invariant,named as non-self-centrality number(NSC number for short),of a graph G is defined as follows:N(G)=∑v_i,v_j∈V(G)|e_i-e_j| where the summation goes over all the unordered pairs of vertices in G and e_i is the eccentricity of vertex v_i in G,whereas the invariant will be called third Zagreb eccentricity index if the summation only goes over the adjacent vertex pairs of graph G.In this paper,we determine the lower and upper bounds on N(G) and characterize the corresponding graphs at which the lower and upper bounds are attained.Finally we propose some attractive research topics for this new invariant of graphs.     

Vertex-edge domination in graphs

In this paper we study graph parameters related to vertex-edge domination, where a vertex dominates the edges incident to it as well as the edges adjacent to these incident edges. First, we present new relationships relating the ve-domination to some other domination parameters, answering in the affirmative four open questions posed in the 2007 PhD thesis by Lewis. Then we provide an upper bound for the independent ve-domination number in terms of the ve-domination number for every nontrivial connected K_1,k-free graph, with k ≥ 3, and we show that the independent ve-domination number is bounded above by the domination number for every nontrivial tree. Finally, we establish an upper bound on the ve-domination number for connected C₅-free graphs, improving a recent bound given for trees.     

Nordhaus–Gaddum Results for the Induced Path Number of a Graph When Neither the Graph Nor Its Complement Contains Isolates

The induced path number \(\rho (G)\) of a graph G is defined as the minimum number of subsets into which the vertex set of G can be partitioned so that each subset induces a path. A product Nordhaus–Gaddum-type result is a bound on the product of a parameter of a graph and its complement. Hattingh et al. (Util Math 94:275–285, 2014) showed that if G is a graph of order n, then \(\lceil \frac{n}{4} \rceil \le \rho (G) \rho (\overline{G}) \le n \lceil \frac{n}{2} \rceil \), where these bounds are best possible. It was also noted that the upper bound is achieved when either G or \(\overline{G}\) is a graph consisting of n isolated vertices. In this paper, we determine best possible upper and lower bounds for \(\rho (G) \rho (\overline{G})\) when either both G and \(\overline{G}\) are connected or neither G nor \(\overline{G}\) has isolated vertices.     

New bounds of permutation codes under Hamming metric and Kendall’s $$\tau $$-metric

Permutation codes are widely studied objects due to their numerous applications in various areas, such as power line communications, block ciphers, and the rank modulation scheme for flash memories. Several kinds of metrics are considered for permutation codes according to their specific applications. This paper concerns some improvements on the bounds of permutation codes under Hamming metric and Kendall’s \(\tau \)-metric respectively, using mainly a graph coloring approach. Specifically, under Hamming metric, we improve the Gilbert–Varshamov bound asymptotically by a factor n, when the minimum Hamming distance d is fixed and the code length n goes to infinity. Under Kendall’s \(\tau \)-metric, we narrow the gap between the known lower bounds and upper bounds. Besides, we also obtain some sporadic results under Kendall’s \(\tau \)-metric for small parameters.     

Analysis of Local Search Landscapes for <Emphasis Type="Italic">k</Emphasis>-SAT Instances

Stochastic local search is a successful technique in diverse areas of combinatorial optimisation and is predominantly applied to hard problems. When dealing with individual instances of hard problems, gathering information about specific properties of instances in a pre-processing phase is helpful for an appropriate parameter adjustment of local search-based procedures. In the present paper, we address parameter estimations in the context of landscapes induced by k-SAT instances: at first, we utilise a sampling method devised by Garnier and Kallel in 2002 for approximations of the number of local maxima in landscapes generated by individual k-SAT instances and a simple neighbourhood relation. The objective function is given by the number of satisfied clauses. The procedure provides good approximations of the actual number of local maxima, with a deviation typically around 10%. Secondly, we provide a method for obtaining upper bounds for the average number of local maxima in k-SAT instances. The method allows us to obtain the upper bound \(2^{n-O(\sqrt{n/k})}\) for the average number of local maxima, if m is in the region of 2 ^k · n/k.     

Reliability Bounds for Multicriteria Systems

This paper deals with general structure functions, where arbitrary degrees of performance between perfect functioning and complete failure are allowed for each component and the n-component system itself. We make the assumption that the n-component system can be modelled as a structure function given by a mapping φ:L ⁿ →L ^k ₀, L and L₀ being two linearly ordered sets, so that the performance of the system is evaluated according to k single criteria. Global concepts of minimal path and minimal cut are discussed for these multicriteria systems; general reliability bounds based on them are deduced and compared with those given in previous papers.     

<Emphasis Type="Italic">k</Emphasis>-means Requires Exponentially Many Iterations Even in the Plane

The k-means algorithm is a well-known method for partitioning n points that lie in the d-dimensional space into k clusters. Its main features are simplicity and speed in practice. Theoretically, however, the best known upper bound on its running time (i.e., n ^O(kd)) is, in general, exponential in the number of points (when kd=Ω(n/log?n)). Recently Arthur and Vassilvitskii (Proceedings of the 22nd Annual Symposium on Computational Geometry, pp. 144–153, 2006) showed a super-polynomial worst-case analysis, improving the best known lower bound from Ω(n) to \(2^{\varOmega (\sqrt{n})}\) with a construction in \(d=\varOmega (\sqrt{n})\) dimensions. In Arthur and Vassilvitskii (Proceedings of the 22nd Annual Symposium on Computational Geometry, pp. 144–153, 2006), they also conjectured the existence of super-polynomial lower bounds for any d≥2.Our contribution is twofold: we prove this conjecture and we improve the lower bound, by presenting a simple construction in the plane that leads to the exponential lower bound 2^Ω(n).     

A Note on the Effectiveness of a Pool

A measure of ineffectiveness I of a pool of independent service facilities is defined and it isshown to be rather insensitive to changes in the service-time distribution for queues with aPoisson input, assuming equal mean service rates of the servers. This result reduces considerationto the simple case of exponentially distributed service times and in this case (i) I can be computedusing well-known formulae and (ii) it is possible to construct a simple upper bound for I.