Search

A digraph is called irregular if its distinct vertices have distinct degree pairs. An irregular digraph is called minimal (maximal) if the removal of any arc (addition of any new arc) results in a non-irregular digraph. It is easily seen that the minimum sizes among irregular n-vertex whether digraphs or oriented graphs are the same and are asymptotic to (√2/3) n3/2; maximum sizes, however, are asymptotic to n² and n²/2, respectively. Let s stand for the sum of initial positive integers, s = 1, 3, 6, ... . An oriented graph Hs and a digraph Fs, both large (in terms of the size), minimal irregular, and on any such s vertices, s ≥ 21, are constructed in [Large minimal irregular digraphs, Opuscula Math. 23 (2003) 21-24], co-authored by Z. D-H. and three more of the present co-authors (Z.M., J.M., Z.S.). In the present paper we nearly complete these constructions. Namely, a large minimal irregular digraph Fn, respectively oriented graph Hn, are constructed for any of remaining orders n, n > 21, and of size asymptotic to n², respectively to n²/2. Also a digraph Φn and an oriented graph Gn, both small maximal irregular of any order n ≥ 6, are constructed. The asymptotic value of the size of Gn is at least (√2/3) n3/2 and is just the least if n = s → ∞, but otherwise the value is at most four times larger and is just the largest if n = s -1 → ∞. On the other hand, the size of Φn is of the asymptotic order Θ(n3/2). [ABSTRACT FROM AUTHOR]

A symmetrized lattice of 2 n points in terms of an irrational real number α is considered in the unit square, as in the theorem of Davenport. If α is a quadratic irrational, the square of the L 2 discrepancy is found to be c ( α ) log ⁡ n + O ( log ⁡ log ⁡ n ) for a computable positive constant c ( α ) . For the golden ratio φ , the value c ( φ ) log ⁡ n yields the smallest L 2 discrepancy of any sequence of explicitly constructed finite point sets in the unit square. If the partial quotients a k of α grow at most polynomially fast, the L 2 discrepancy is found in terms of a k up to an explicitly bounded error term. It is also shown that certain generalized Dedekind sums can be approximated using the same methods. For a special generalized Dedekind sum with arguments a , b an asymptotic formula in terms of the partial quotients of a b is proved. [ABSTRACT FROM AUTHOR]

This research is the development from Siddiqui's research on edge irregularity strength of subdivision of star. Siddiqui [3] had determined the total edge irregularity strength of sub-division of starS mfor 1≤m≤8 andn≥3. However, the total edge of irregularity strength for star subdivisionS mform≥9 andn≥3 are still in an open problem and also the total edge irregularity strength of subdivision of star by insertingmivertices on different to every edge of a starSnyet to be determined.In this paper, it will be proven that the total edge irregularity strength of subdivision of starS mform≥9 andn≥3 and the total edge irregularity strength of subdivision of starSnm1, m2, ⋯ ,mnformi≥1,mi

Revisiting and extending a recent result of M. Huxley, we estimate the Lp($\mathbb{T}$d) and Weak–Lp($\mathbb{T}$d) norms of the discrepancy between the volume and the number of integer points in translated domains. [ABSTRACT FROM AUTHOR]

We obtain sharp estimates for the sampling constants in Bernstein spaces when the density of the sampling set is near the critical value. [ABSTRACT FROM AUTHOR]

For a simple graph G, a vertex labeling ø:V(G)→{1,2,...,k} is called k -labeling. The weight of an edge xy in G, denoted by wø(xy), is the sum of the labels of end vertices x and y, i.e. wø(xy)=ø(x)+ø(y). A vertex k -labeling is defined to be an edge irregular k -labeling of the graph G if for every two different edges e and f there is Wø(e) ≠ Wø(ƒ). The minimum k for which the graph G has an edge irregular k -labeling is called the edge irregularity strength of G, denoted by es(G). In this paper, we estimate the bounds of the edge irregularity strength and determine the exact value for several families of graphs. [ABSTRACT FROM AUTHOR]

LetXbe an input measurement andYthe output reading of a calibrated instrument, withY(X) as the calibration curve. SolvingX(Y) projects an instrumental reading back onto the scale of measurements as an object of pivotal interest. The arrays of instrumental readings are projected in this manner in practice, yielding arrays of calibrated measurements, typically subject to errors of calibration. The effects of calibration errors on the properties of calibrated measurements are examined here under linear calibration. Irregularities arise as induced dependencies, inflated variances, non-standard distributions, inconsistent sample means, the underestimation of measurement variance, and other unintended consequences. On the other hand, conventional properties are seen to remain largely in place in the use of selected regression diagnostics and in one-way comparative experiments using calibrated data. [ABSTRACT FROM AUTHOR]

In this paper we prove that surfaces of general type with irregularity $q\geq 3$ are rationally cohomologically rigidified, and so are minimal surfaces $S$ with $q(S)= 2$ unless ${ K}_{S}^{2} = 8\chi ({ \mathcal{O} }_{S} )$. Here a surface $S$ is said to be rationally cohomologically rigidified if its automorphism group $\mathrm{Aut} (S)$ acts faithfully on the cohomology ring ${H}^{\ast } (S, \mathbb{Q} )$. As examples we give a complete classification of surfaces isogenous to a product with $q(S)= 2$ that are not rationally cohomologically rigidified. [ABSTRACT FROM AUTHOR]

The foldover is a useful technique in the construction of two-level factorial designs for follow-up experiments. To search an optimal foldover plans is an important issue. In this paper, for a set of asymmetric fractional factorials such as the original designs, a lower bound for centredL2-discrepancy of combined designs under a general foldover plan is obtained, which can be used as a benchmark for searching optimal foldover plans. All of our results are the extended ones of Ouet al.[Lower bounds of various discrepancies on combined designs, Metrika 74 (2011), pp. 109–119] for symmetric designs to asymmetric designs. Moreover, it also provides a theoretical justification for optimal foldover plans in terms of uniformity criterion. [ABSTRACT FROM AUTHOR]

Many construction methods for (nearly) uniform designs have been proposed under the centered $$L_2$$-discrepancy, and most of them are only suitable for constructing designs with small size. This paper proposes a new method, called mixture method (MM), to construct nearly symmetrical/asymmetrical uniform designs with large number of runs and/or large number of factors. The new method has the 'better than given' property, i.e., the resulting design is better than existing designs in the sense of the pre-decided criterion. Moreover, the computational speed of MM is faster than most existing methods. [ABSTRACT FROM AUTHOR]

Let S be a minimal complex surface of general type with irregularity q ≥ 2 and let C ⊂ S be an irreducible curve of geometric genus g. Assume that C is Albanese defective, that is, that the image of C via the Albanese map does not generate the Albanese variety Alb(S); we obtain a linear upper bound in terms of K2S and g for the canonical degree KSC of C. As a corollary, we obtain a bound for the canonical degree of curves with g ≤ q−1, thereby generalizing and sharpening the main result of Lu [‘On surfaces of general type with maximal Albanese dimension’, J. reine angew. Math. 641 (2010) 163–175.]. [ABSTRACT FROM PUBLISHER]

Abstract: We investigate the limit behavior of the average -discrepancy for if the number of sample points tends to infinity. We adopt a recent result of Steinerberger and give asymptotic expressions for several types of discrepancy functions studied in the literature. This also leads to a new proof for the average -star discrepancy. Our methods are probabilistic in nature. Furthermore, we employ symmetrization techniques to obtain estimates for arbitrary . [Copyright &y& Elsevier]

Abstract: In this paper, we introduce eight power indices that admit a probabilistic interpretation for voting rules with abstention or with three levels of approval in the input, briefly (3, 2) games. We analyze the analogies and discrepancies between standard known indices for simple games and the proposed extensions for this more general context. A remarkable difference is that for (3, 2) games the proposed extensions of the Banzhaf index, Coleman index to prevent action and Coleman index to initiate action become non-proportional notions, contrarily to what succeeds for simple games. We conclude the work by providing procedures based on generating functions for weighted (3, 2) games, and extensible to (j,k) games, to efficiently compute them. [Copyright &y& Elsevier]

This note provides a theoretical justification of optimal foldover plans in terms of uniformity. A new lower bound of the centered L-discrepancy values of combined designs is obtained, which can be used as a benchmark for searching optimal foldover plans. Our numerical results show that this lower bound is sharper than existing results when more factors reverse the signs in the initial design. [ABSTRACT FROM AUTHOR]

Abstract: Discrepancy measures how uniformly distributed a point set is with respect to a given set of ranges. Depending on the ranges, several variants arise, including star discrepancy, box discrepancy, and discrepancy of halfspaces. These problems are solvable in time , where is the dimension of the underlying space. As such a dependency on becomes intractable for high-dimensional data, we ask whether it can be moderated. We answer this question negatively by proving that the canonical decision problems are W[1]-hard with respect to the dimension, implying that no -time algorithm is possible for any function unless FPT=W[1]. We also discover the W[1]-hardness of other well known problems, such as determining the largest empty box that contains the origin and is inside the unit cube. This is shown to be hard even to approximate within a factor of . [Copyright &y& Elsevier]

We improve the upper bound for the lattice point discrepancy of large spheres under conjectural properties of the real L-functions. In connection with this we give some new unconditional estimates for exponential and character sums of independent interest. [ABSTRACT FROM AUTHOR]

Abstract: Parvan [A.S. Parvan, Critique of multinomial coefficients method for evaluating Tsallis and Rényi entropies, Physica A 389 (2010) 5645] has recently presented some calculations in order to demonstrate the incorrectness of the results obtained from the generalized multinomial coefficients (GMC) presented in Oikonomou (2007) . According to Parvan, the aforementioned approach of studying maximum entropy probability distributions is erroneous. In this comment I demonstrate that Parvan’s arguments do not hold true and that the obtained results from GMC do not present either mathematical or physical discrepancies. [ABSTRACT FROM AUTHOR]

Abstract: The linear discrepancy of a poset is the least such that there is a linear extension of such that if and are incomparable, then , whereas the weak discrepancy is the least such that there is a weak extension of such that if and are incomparable, then . This paper resolves a question of Tanenbaum, Trenk, and Fishburn on characterizing when the weak and linear discrepancy of a poset are equal. Although it is shown that determining whether a poset has equal weak and linear discrepancy is -complete, this paper provides a complete characterization of the minimal posets with equal weak and linear discrepancy. Further, these minimal posets can be completely described as a family of interval orders. [Copyright &y& Elsevier]

Abstract: Let be the sum-of-digits function of in base . Newman (1969) has shown the surprising phenomenon that for all (with some ). Motivated by investigations of distribution properties of Niederreiter–Halton sequences we study for and , where is the -weighted sum-of-digits function of in base 2. We completely classify all and for which Newman-type results hold, thereby generalising the result of Newman and results given by Drmota and Stoll (2008) . We point out consequences of our results for the distribution of Niederreiter–Halton sequences (). [ABSTRACT FROM AUTHOR]

We bound the hereditary discrepancy of a hypergraph H in two colors in terms of its hereditary discrepancy in c colors. We show that herdisc(H, 2) ≤ herdisc(H, c), where K is some absolute constant. This bound is sharp apart from the absolute constant. [ABSTRACT FROM AUTHOR]

Let d be a fixed integer, and let W be any d-dimensional linear subspace of ℝn. There then exists a subset I of the n coordinates {1, 2,…,n} of ℝn of cardinality at least (½ -0(1)n such that for every vector w = (w1,…,wn) ∈ W -we have ∑i∈I |wi| ≤ ∑i∌I|wil. Equivalently, let P be any multiset of n arbitrary vectors in ℝd. Then there exists a subset S of P of size at least (½-0(1))n such that for every vector u ∈ℝd we have ∑x ∈S |(x,u)|∑x,∈P|(x,u)|. A continuous analogue of the former result is also considered. [ABSTRACT FROM AUTHOR]

Abstract: This paper addresses the jobshop and the flowshop scheduling problems with minimum and maximum time lags. To solve this kind of problems, we propose adaptations of Climbing Discrepancy Search (CDS). We study various parameter settings. Computational experiments are provided to evaluate the propositions. [ABSTRACT FROM AUTHOR]

Abstract: We answer the following question: What is the discrepancy of the lexicographically least binary de Bruijn sequence? Here, “discrepancy” refers to the maximum (absolute) difference between the number of ones and the number of zeros in any initial segment of the sequence. We show that the answer is . [Copyright &y& Elsevier]

Abstract: For given integers and any positive integers , distributions of points in the -dimensional unit cube are investigated, where the minimum volume of the convex hull determined by of these points is large. In particular, for fixed integers the existence of a configuration of points in is shown, such that, simultaneously for , the volume of the convex hull of any points among these points is . Moreover, a deterministic algorithm is given achieving this lower bound, provided that . [Copyright &y& Elsevier]

Abstract: Estimating the discrepancy of the set of all arithmetic progressions in the first natural numbers was one of the famous open problems in combinatorial discrepancy theory for a long time, successfully solved by K. Roth (lower bound) and Beck (upper bound). They proved that , where the minimum is taken over all colorings and the maximum over all arithmetic progressions in . Sumsets of arithmetic progressions, , are called -arithmetic progressions and they are important objects in additive combinatorics. We define as the discrepancy of the set . The second author proved that and Přívětivý improved it to for all . Since the probabilistic argument gives for all fixed , the case remained the only case with a large gap between the known upper and lower bounds. We bridge this gap (up to a logarithmic factor) by proving that for all . Indeed we prove the multicolor version of this result. [Copyright &y& Elsevier]

Abstract: We present three cubically convergent methods for choosing the regularization parameters in linear inverse problems. The detailed algorithms are given and the convergence rates are estimated. Our basic tools are Tikhonov regularization and Morozov''s discrepancy principle. We prove that, in comparison with the standard Newton method, the computational costs for our cubically convergent methods are nearly the same, but the number of iteration steps is even less. Numerical experiments for an elliptic boundary value problem illustrate the efficiency of the proposed algorithms. [Copyright &y& Elsevier]

Abstract: We provide a new construction of nonlinear pseudorandom number generators. We use the inversive method over Galois rings. This generalizes to the common setting of Galois rings both the works of Niederreiter et al. over finite fields and Eichenauer-Herrmann et al. over integers modulo a prime power. The main proof technique to bound the discrepancy from above is the local Weil bound on hybrid character sums over Galois rings. The estimates hold for the full period and also for certain parts of the period. Elementary -adic analysis allows us to ensure maximal period length. [Copyright &y& Elsevier]

In this paper, we present a number of examples of commutative Banach algebras with various Arens irregularity properties. These examples illustrate in particular that strong Arens irregularity and extreme non-Arens regularity, the two natural concepts of ``maximal'' Arens irregularity for general Banach algebras as introduced by Dales-Lau and Granirer, respectively, are indeed distinct. Thereby, an open question raised by several authors is answered. We also link these two properties to another natural Arens irregularity property. [ABSTRACT FROM AUTHOR]

Abstract: Recently, Rajan [M.P. Rajan, An efficient discretization scheme for solving the ill-posed problems, Journal of Mathematical Analysis and Applications 313 (2) (2006) 654–677] considered a discretization scheme for solving ill-posed problems and obtained optimal error estimates under an a priori parameter choice strategy with a particular smoothness assumption on the solution. It is shown that the computational information for solving the system is far less than the traditional projection schemes. Neubauer [A. Neubauer, An a posteriori parameter choice for Tikhonov regularization in the presence of modeling error, Applied Numerical Mathematics 4 (1988) 507–519] and Engl and Gfrerer [H.W. Engl, H. Gfrerer, A posteriori parameter choice for general regularization methods for solving ill-posed problems, Applied Numerical Mathematics 4 (1988) 395–417] suggested an a posteriori method for choosing the regularization parameter which does not require any knowledge about the exact solution, respectively under finite dimensional as well as general setting. In this paper, we consider an a posteriori parameter choice for finite dimensional approximation which does not require any information about the smoothness of the exact solution and apply to the discretization scheme considered by Rajan. The computational efficiency of the scheme is illustrated through numerical examples. [Copyright &y& Elsevier]

The role of uniformity measured by the symmetric L2-discrepancy given in Hickernell (1998) has been studied in fractional factorial designs. The issue of lower bounds on the symmetric L2-discrepancy is crucial in the construction of uniform designs. This article reports some new lower bounds on the symmetric L2-discrepancy for symmetric fractional factorials and for a set of asymmetric fractional factorials. It is valuable to use these lower bounds to measure uniformity of given designs. [ABSTRACT FROM AUTHOR]

The Lovász local lemma due to Erdős and Lovász (Infinite and Finite Sets, Colloq. Math. Soc. J. Bolyai 11, 1975, pp. 609-627) is a powerful tool in proving the existence of rare events. We present an extension of this lemma, which works well when the event to be shown to exist is a conjunction of individual events, each of which asserts that a random variable does not deviate much from its mean. As applications, we consider two classes of NP-hard integer programs: minimax and covering integer programs. A key technique, randomized rounding of linear relaxations, was developed by Raghavan and Thompson (Combinatorica, 7 (1987), pp. 365-374) to derive good approximation algorithms for such problems. We use our extension of the local lemma to prove that randomized rounding produces, with nonzero probability, much better feasible solutions than known before, if the constraint matrices of these integer programs are column-sparse (e.g., routing using short paths, problems on hypergraphs with small dimension/degree). This complements certain well-known results from discrepancy theory. We also generalize the method of pessimistic estimators due to Raghavan (J. Comput. System Sci., 37 (1988), pp. 130-143), to obtain constructive (algorithmic) versions of our results for covering integer programs. [ABSTRACT FROM AUTHOR]

Primal-dual interior-point methods (IPMs) have shown their power in solving large classes of optimization problems. However, there is still a discrepancy between the practical behavior of these algorithms and their theoretical worst-case complexity results with respect to the update strategies of the dua-lity gap parameter in the algorithm. Recently, this discrepancy was significantly reduced by Peng, J., Roos, C. and Terlaky, T., 2002, Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms (Princeton, NJ: Princeton University Press) who introduced a new family of self-regular (SR)-proximity functions based IPMs. In this paper, based on a class of SR proximities, we propose an adaptive single-step large-update SR-IPM that is very close to what is used in the McIPM software package. At each step, our algorithm always chooses a large-update of the target value adaptively depending on the position of the current iterate. This adaptive choice of the target value is different from the one what is presented in Peng, J., Roos, C. and Terlaky, T., 2002, Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms (Princeton, NJ: Princeton University Press), where the target μ value is reduced by a fix factor when the iterate is sufficiently well centered. An 𝒪( qn ( q +1)/2 q log( n /ℇ)) worst-case iteration bound of the algorithm is established, where q is the barrier degree of the SR-proximity. For q = log n , our algorithm achieves the so far best complexity for large-update IPMs. Email: salahim@math.mcmaster.ca [ABSTRACT FROM AUTHOR]

The article offers information on the norms and arguments associated with Nemirovski's inequalities. It discusses three different methods that are used to prove inequalities including the probabilistic methods for Banach spaces, deterministic inequalities for norms, and the empirical process. It shows that the approach of Nemirovski yielded a better constant among other inequalities. It also examines the formulation of inequalities, and the inequalities that resulted from these methods.

Especially investigated in recent years, the Gaussian discord can tentatively be quantified by a distance between a given two-mode Gaussian state (GS) and the set of all the zero-discord two-mode GSs. However, as this set consists only of product states, such a distance captures all the correlations (quantum and classical) between modes. Therefore it is merely an upper bound for the geometric discord, no matter which is the employed distance. In this work we choose for this purpose the Hellinger metric that is known to have many beneficial properties recommending it as a good measure of quantum behaviour. In general, this metric is determined by affinity, a relative of the Uhlmann fidelity with which it shares many important features. As a first step of our work, the affinity of a pair of n-mode GSs is written. Then, in the two-mode case, we succeeded in determining exactly the closest Gaussian product state and computed the Gaussian discord accordingly. The obtained general formula is remarkably simple and becomes still friendlier in the significant case of symmetric two-mode GSs. We then analyse in detail two special classes of two-mode GSs of theoretical and experimental interest as well: the squeezed thermal states and the mode-mixed thermal ones. The former are separable under a well-known threshold of squeezing, while the latter are always separable. It is worth stressing that for symmetric states belonging to either of these classes, we find consistency between their geometric Hellinger discord and the originally defined discord in the Gaussian approach. At the same time, the Gaussian Hellinger discord of such a state turns out to be a reliable measure of the total amount of its cross correlations. [ABSTRACT FROM AUTHOR]