Search

This paper elaborates on a sieving technique that has first been applied in 2018 for improving bounds on deterministic integer factorization. We will generalize the sieve in order to obtain a polynomial-time reduction from integer factorization to a specific instance of the multiple choice subset-sum problem. As an application, we will improve upon special purpose factorization algorithms for integers composed of divisors with small difference. In particular, we will refine the runtime complexity of Fermat's factorization algorithm by a large subexponential factor. Our first procedure is deterministic, rigorous, easy to implement and has negligible space complexity. Our second procedure is heuristically faster than the first, but has non-negligible space complexity. [ABSTRACT FROM AUTHOR]

We give a new general approach for designing exact exponential-time algorithms for subset problems. In a subset problem the input implicitly describes a family of sets over a universe of size n and the task is to determine whether the family contains at least one set. A typical example of a subset problem is Weighted d-SAT. Here, the input is a CNF-formula with clauses of size at most d, and an integer W. The universe is the set of variables and the variables have integer weights. The family contains all the subsets S of variables such that the total weight of the variables in S does not exceed W and setting the variables in S to 1 and the remaining variables to 0 satisfies the formula. Our approach is based on "monotone local search," where the goal is to extend a partial solution to a solution by adding as few elements as possible. More formally, in the extension problem, we are also given as input a subset X of the universe and an integer k. The task is to determine whether one can add at most k elements to X to obtain a set in the (implicitly defined) family. Our main result is that a cknO(1) time algorithm for the extension problem immediately yields a randomized algorithm for finding a solution of any size with running time O((2 - 1/c)n). In many cases, the extension problem can be reduced to simply finding a solution of size at most k. Furthermore, efficient algorithms for finding small solutions have been extensively studied in the field of parameterized algorithms. Directly applying these algorithms, our theorem yields in one stroke significant improvements over the best known exponential-time algorithms for several well-studied problems, including d-HITTING SET, FEEDBACK VERTEX SET, NODE UNIQE LABEL COVER, and WEIGHTED d-SAT. Our results demonstrate an interesting and very concrete connection between parameterized algorithms and exact exponential-time algorithms. We also show how to derandomize our algorithms at the cost of a subexponential multiplicative factor in the running time. Our derandomization is based on an efficient construction of a new pseudo-random object that might be of independent interest. Finally, we extend our methods to establish new combinatorial upper bounds and develop enumeration algorithms. [ABSTRACT FROM AUTHOR]

The following problem has been known since the 80's. Let Γ be an Abelian group of order m (denoted |Γ| = m), and let t and mi, 1 ≤ i ≤ t, be positive integers such ∑i=1t mi = m -- 1. Determine when Γ* = Γ \ {0}, the set of non-zero elements of Γ, can be partitioned into disjoint subsets Si, 1 ≤ i ≤ t, such that |Si| = mi and ... s = 0 for every i 2 [1; t]. It is easy to check that mi ≥ 2 (for every i ∈ [1, t]) and |I(Γ)| ≠= 1 are necessary conditions for the existence of such partitions, where I(Γ) is the set of involutions of Γ. It was proved that the condition mi ≥ 2 is sufficient if and only if |I(Γ)} ∈ {0, 3} (see Zeng, (2015)). For other groups (i.e., for which |I(Γ)} ≠ 3 and |I(Γ)| > 1), only the case of any group Γ with Γ ≅ = (ℤ2)n for some positive integer n has been analyzed completely so far, and it was shown independently by several authors that mi ≥ 3 is sufficient in this case. Moreover, recently Cichacz and Tuza (2021) proved that, if |Γ| is large enough and |I(Γ)| > 1, then mi ≥ 4 is sufficient. In this paper we generalize this result for every Abelian group of order 2n. Namely, we show that the condition mi ≥ 3 is sufficient for Γ such that |I(Γ)} > 1 and |Γ| = 2n, for every positive integer n. We also present some applications of this result to graph magic- and anti-magic-type labelings. [ABSTRACT FROM AUTHOR]

Multi-objective optimization problems (MOPs) aim to obtain a set of Pareto-optimal solutions, and as the number of objectives increases, the quantity of these optimal solutions grows exponentially. However, a plethora of optimal solutions can impose significant decision stress on decision-makers. Subset selection, as the extension of a model, can extract a representative set of solutions, thereby alleviating the decision-makers' choice pressure. In addition, extending a model undoubtedly incurs additional time costs. To cope with the foregoing issues, a fast subset selection method named ranking-based subset selection (RBSS) is proposed in this paper. It can efficiently select a small number of optimal solutions within an unbounded external archive and can be directly applied to any multi-objective evolutionary algorithm. This allows it to maintain good distribution and diversity with very little time investment. We employed a ranking-based approach to map the objective space to a ranking space (an integer space) defined by us and then selected the corresponding subset in the ranking space. The well-behaved mathematical properties of the ranking space and the advantages of using integer calculations accelerated the subset selection process. Experimental results indicate that compared to several state-of-the-art subset selection methods, RBSS is capable of selecting a set of representative and diverse solutions across different types of MOPs, while consuming significantly less time. Specifically, for problems where the Pareto front is a two-dimensional manifold and a one-dimensional manifold, the time consumption of RBSS is approximately only 0.028% to 27.5% and 4.6e−4% to 0.15% of that required by other algorithms, respectively. [ABSTRACT FROM AUTHOR]

Let R be a commutative ring with identity, S be a multiplicatively closed subset of R, and let M be an R-module. In this paper, we introduce and investigate some properties of the notion of S-2-absorbing second submodules of M as a generalization of S-second submodules and strongly 2-absorbing second submodules of M. Also, we obtain some results concerning S-2-absorbing submodules of M. [ABSTRACT FROM AUTHOR]

This paper is mainly concerned with sets which do not contain four‐term arithmetic progressions, but are still very rich in three‐term arithmetic progressions, in the sense that all sufficiently large subsets contain at least one such progression. We prove that there exists a positive constant c and a set A⊂픽qn which does not contain a four‐term arithmetic progression, with the property that for every subset A′⊂A with |A′|≥|A|1−c, A′ contains a nontrivial three term arithmetic progression. We derive this from a more general quantitative Roth‐type theorem in random subsets of 픽qn, which improves a result of Kohayakawa–Łuczak–Rödl/Tao–Vu. We also discuss a similar phenomenon over the integers. Finally, we include another application of our methods, showing that for sets in 픽qn or ℤ the property of "having nontrivial three‐term progressions in all large subsets" is almost entirely uncorrelated with the property of "having large additive energy." [ABSTRACT FROM AUTHOR]

We consider a wireless source localization network in which a target node emits localization signals that are used by anchor nodes to estimate the target node position. In addition to target and anchor nodes, there can also exist eavesdropper nodes and jammer nodes which aim to estimate the position of the target node and to degrade the accuracy of localization, respectively. We first propose the problem of eavesdropper selection with the goal of optimally placing a given number of eavesdropper nodes to a subset of possible positions to estimate the target node position as accurately as possible. As the performance metric, the Cramér-Rao lower bound (CRLB) related to the estimation of the target node position by eavesdropper nodes is derived, and its convexity and monotonicity properties are investigated. By relaxing the integer constraints, the eavesdropper selection problem is approximated by a convex optimization problem and algorithms are proposed for eavesdropper selection. Then, the problem of jammer selection is proposed where the aim is to optimally place a given number of jammer nodes to a subset of possible positions for degrading the localization accuracy of the network as much as possible. A CRLB expression from the literature is used as the performance metric, and its concavity and monotonicity properties are derived. Also, a convex optimization problem is derived after relaxation. Finally, the joint eavesdropper and jammer selection problem is proposed with the goal of placing certain numbers of eavesdropper and jammer nodes to a subset of possible positions. [ABSTRACT FROM AUTHOR]

For high-dimensional data with a large number of redundant features, existing feature selection algorithms still have the problem of "curse of dimensionality." In view of this, the paper studies a new two-phase evolutionary feature selection algorithm, called clustering-guided integer brain storm optimization algorithm (IBSO-C). In the first phase, an importance-guided feature clustering method is proposed to group similar features, so that the search space in the second phase can be reduced obviously. The second phase applies oneself to finding optimal feature subset by using an improved integer brain storm optimization. Moreover, a new encoding strategy and a time-varying integer update method for individuals are proposed to improve the search performance of brain storm optimization in the second phase. Since the number of feature clusters is far smaller than the size of original features, IBSO-C can find an optimal feature subset fast. Compared with several existing algorithms on some real-world datasets, experimental results show that IBSO-C can find feature subset with high classification accuracy at less computation cost. [ABSTRACT FROM AUTHOR]

We study the problem of minimizing a convex function on a nonempty, finite subset of the integer lattice when the function cannot be evaluated at noninteger points. We propose a new underestimator that does not require access to (sub)gradients of the objective; such information is unavailable when the objective is a blackbox function. Rather, our underestimator uses secant linear functions that interpolate the objective function at previously evaluated points. These linear mappings are shown to underestimate the objective in disconnected portions of the domain. Therefore, the union of these conditional cuts provides a nonconvex underestimator of the objective. We propose an algorithm that alternates between updating the underestimator and evaluating the objective function. We prove that the algorithm converges to a global minimum of the objective function on the feasible set. We present two approaches for representing the underestimator and compare their computational effectiveness. We also compare implementations of our algorithm with existing methods for minimizing functions on a subset of the integer lattice. We discuss the difficulty of this problem class and provide insights into why a computational proof of optimality is challenging even for moderate problem sizes. [ABSTRACT FROM AUTHOR]

Sparse mathematical modelling plays an increasingly important role in chemometrics due to its interpretability and prediction power. While many sparse techniques used in chemometrics rely on L 1 penalization to create sparser models, Mixed Integer Optimization (MIO) achieves sparsity by imposing constraints directly in the model. In this paper, we develop an intuitive and flexible robust sparse regression framework using MIO. We use constraints and penalization to achieve sparsity and robustness respectively. We test and compare results with those obtained using other techniques generating sparser models such as LASSO and sparse PLS. We also use PLS as a baseline to compare predictive performance. We use a LIBS data set of certified reference materials (CRM) of various mineral ores to illustrate the framework using different objective functions. The MIO framework proposed improves accuracy, sparsity and robustness vs. LASSO and SPLS. MIO achieves an average R 2 higher than other methods on average by at least 10.6%. Robust MIO approach also improves interpretability. It also uses 4.3 variables on average while LASSO and SPLS use 16.1 and 805.8 respectively. We also illustrate how interpretability can help build better models through examples derived from the data sets used. When adding noise to the signal, MIO achieves an R 2 of 0.69 on average when all models have negative R 2 values. The MIO framework proposed is versatile and could be used in other chemometrics applications. Image 1 • Novel mixed integer calibration method. • Best Subset Selection. • Benchmark with existing methods. • Tests on mineral ore. [ABSTRACT FROM AUTHOR]

In this paper, we investigate a specific optimization problem that arises in the context of Balance Optimization Subset Selection (BOSS), which is an optimization framework for causal inference. Most BOSS problems can be formulated as mixed integer linear programs. By relaxing the integrality constraints so that fractional contributions of control units are permitted, a linear program (LP) is obtained. Properties of this LP and its dual are investigated and a sensitivity analysis is conducted to characterize how the objective value changes as the covariate values are perturbed. [ABSTRACT FROM AUTHOR]

Given integers 2≤t≤k+1≤n, let gk(t,n) be the minimum N such that every red/blue coloring of the k-subsets of {1,...,N} yields either a (k+1)-set containing t red k-subsets, or an n-set with all of its k-subsets blue. Erdős and Hajnal proved in 1972 that for fixed 2≤t≤k, there are positive constants c1 and c2 such that ..., where twrt-1 is a tower of 2's of height t-2. They conjectured that the tower growth rate in the upper bound is correct. Despite decades of work on closely related and special cases of this problem by many researchers, there have been no improvements of the lower bound for 2

For a given set $S\subset \mathbb{N}$ , $R_{S}(n)$ is the number of solutions of the equation $n=s+s^{\prime },s. Suppose that $m$ and $r$ are integers with $m>r\geq 0$ and that $A$ and $B$ are sets with $A\cup B=\mathbb{N}$ and $A\cap B=\{r+mk:k\in \mathbb{N}\}$. We prove that if $R_{A}(n)=R_{B}(n)$ for all positive integers $n$ , then there exists an integer $l\geq 1$ such that $r=2^{2l}-1$ and $m=2^{2l+1}-1$. This solves a problem of Chen and Lev ['Integer sets with identical representation functions', Integers 16 (2016), A36] under the condition $m>r$. [ABSTRACT FROM AUTHOR]

Abstract The paper proposes a homomorphic encryption scheme with public key size based on summation integer of sparse subset. The full-homomorphic encryption scheme that applies the batch processing technology to the integer can homomorphically process and encrypt a plaintext vector in a ciphertext to improve the efficiency of the original scheme, yet its size of the public key is O ̃ (λ 8). In an effort to reduce the size of public key for this scheme, we combine quadric form of public key elements and ciphertext compression to present SomeWhat homomorphic public key scheme, which reduces the security of public key scheme into the approximate integer GCD problem, thereby converting the homomorphic encryption scheme into full homomorphic encryption scheme. For the proposed homomorphic encryption scheme with public key size based on summation integer of sparse subset, the public key size for improve scheme is O ̃ (λ 5.5) , a smaller size. Lastly, the scheme is proved to be semantically secure. [ABSTRACT FROM AUTHOR]

We say that a set of the form [ a , b ] : = { c ∈ ℤ : a ≤ c ≤ b } for some a , b ∈ ℤ is an interval. For a nonempty finite subset A of ℤ and n ∈ ℕ , Vsevolod Lev proved in [Optimal representations by sumsets and subset sums, J. Number Theory62(1) (1997) 127–143] some results about the existence of long intervals contained in the n -fold iterated sumset of A. Furthermore, in the same paper, he proposed a conjecture [Optimal representations by sumsets and subset sums, J. Number Theory62(1) (1997) 127–143, Conjecture 1], see also [V. Lev, Consecutive integers in high-multiplicity sumsets, Acta Math. Hungar.129(3) (2010) 245–253, Conjecture 1]. Lev proved some particular cases of his conjecture, and he showed that these few cases have important applications. In this paper, we prove his conjecture. [ABSTRACT FROM AUTHOR]

Let $K$ be a number field with a ring of integers ${\mathcal{O}}$. We follow Ferraguti and Micheli [‘On the Mertens–Cèsaro theorem for number fields’, Bull. Aust. Math. Soc. 93 (2) (2016), 199–210] to define a density for subsets of ${\mathcal{O}}$ and use it to find the density of the set of $j$ -wise relatively $r$ -prime $m$ -tuples of algebraic integers. This provides a generalisation and analogue for several results on natural densities of integers and ideals of algebraic integers. [ABSTRACT FROM AUTHOR]

We introduce large families of subsets arising from Woods problem and study their cardinalities. Estimates of character sums over the subsets are given. We study the pesudorandom properties of the subsets and show that their well-distribution measures are very high. [ABSTRACT FROM AUTHOR]

The main purpose of this paper is to introduce and examine the concepts of deferred statistical convergence of order β and strong r-deferred Cesáro summability of order β for sequences of fuzzy numbers and give some relations between deferred statistical convergence sequences of order β and strongly r-deferred Cesáro summable sequences of order β, where β ∈ (0, 1] and p ∈ ℝ +. Mathematics Subject Classification: 40A05, 40C05, 46A45, 03E72. [ABSTRACT FROM AUTHOR]

For integers n ≥ k ≥ 2 let m ( n , k ) denote the maximum size of a family of subsets of an n -set without k pairwise disjoint members. In an important classical paper Kleitman determined m ( n , k ) for n ≡ 0 or −1 (mod k ). We present a simple short proof of this result and prove the uniqueness of the optimal families as well. [ABSTRACT FROM AUTHOR]

Suppose D is a suitably admissible compact subset of . . .k having a smooth boundary with possible zones of zero curvature. Let R(T, θ, x) = N(T, θ, x)−Tkvol(D), where N(T, θ, x) is the number of integral lattice points contained in an x-translation of Tθ(D), with T > 0 a dilation parameter and θ ∈ SO(k). Then R(T, θ,x) can be regarded as a function with parameter T on the space E*+ (k), where E*+ (k) is the quotient of the direct Euclidean group by the subgroup of integral translations and E*+ (k) has a normalized invariant measure which is the product of normalized measures on SO(k) and the k-torus. We derive an integral estimate, valid for almost all (θ, x) ∈ E*+ (k), one consequence of which in two dimensions is that for almost all (θ, x) ∈ E*+ (k) (2), a counterpart of the Hardy circle estimate (1/T ) ∫ T1|R(t, θ, x) dt| « T1/4 + ε is valid with an improved estimate. We conclude with an account of hyperbolic versions for which, drawing on previous work of Hill and Parnovski, we give counterparts in all dimensions for both the compact and non-compact finite volume cases. [ABSTRACT FROM AUTHOR]

The β-transformation of the unit interval is defined byTβ(x) ≔ βx (mod 1). Its eventually periodic points are a subset of [0, 1] intersected with the field extension. If β > 1 is an algebraic integer of degreed> 1, thenis a-vector space isomorphic to; therefore, the intersection of [0, 1] withis isomorphic to a domain in. The transformation from this domain which is conjugate to the β-transformation is called the companion map, given its connection to the companion matrix of β's minimal polynomial. The companion map and the proposed notation provide a natural setting to reformulate a classic result concerning the set of periodic points of the β-transformation fornumbers. It also allows to visualize orbits in ad-dimensional space. Finally, we refer connections with arithmetic codings and symbolic representations of hyperbolic toral automorphisms. [ABSTRACT FROM PUBLISHER]

This paper is concerned with invariance (F1,F2)-scrambled sets under iterations. The main results are an extension of the compound invariance of Li-Yorke chaos and distributional chaos. New definitions of (F1,F2)-scrambled sets in non-autonomous discrete systems are given. For a positive integer k, the properties P(k) and Q(k) of Furstenberg families are introduced. It is shown that, for any positive integer k, for any s ∈ [0,1], Furstenberg family M(s) has properties P(k) and Q(k), where M(s) denotes the family of all infinite subsets of Z+ whose upper density is not less than s. Then, the following conclusion is obtained. D is an (M(s),M(t))-scrambled set of (X,f1,∞) if and only if D is an (M(s),M(t))-scrambled set of (X,f1,∞[m]). [ABSTRACT FROM AUTHOR]

A space X is star-C-Hurewicz if for each sequence (Un : n ∈ N) of open covers of X there exists a sequence (Kn : n ∈ N) of countably compact subsets of X such that for each x ∈ X, x ∈ St(Kn, Unn) for all but finitely many n. In this paper, we investigate the relationship between star-C-Hurewicz spaces and related spaces, and study topological properties of star-C-Hurewicz spaces. [ABSTRACT FROM AUTHOR]

We study the relation between a space X satisfying certain generalized metric properties (for example, open ( G ), point-countable base, Collins–Roscoe property, semi-stratifiable, k -semistratifiable, semi-metrizable, scattered, point-countable cs -network, every compact set is metrizable) and its n -fold symmetric product F n ( X ) satisfying the same properties. We also show that if X is an M 1 -space then F ( X ) is an M 1 -space, where F ( X ) is the hyperspace of finite subsets of X . A space X is a paracompact p -space if and only if its 2-fold symmetric product F 2 ( X ) is a paracompact p -space. A Tychonoff space X is a Lindelöf Σ-space if and only if its 2-fold symmetric product F 2 ( X ) is a Lindelöf Σ-space. [ABSTRACT FROM AUTHOR]

Let ${\mathcal{A}}$ be a unital torsion-free algebra over a unital commutative ring ${\mathcal{R}}$. To characterise Lie $n$-higher derivations on ${\mathcal{A}}$, we give an identity which enables us to transfer problems related to Lie $n$-higher derivations into the same problems concerning Lie $n$-derivations. We prove that: (1) if every Lie $n$-derivation on ${\mathcal{A}}$ is standard, then so is every Lie $n$-higher derivation on ${\mathcal{A}}$; (2) if every linear mapping Lie $n$-derivable at several points is a Lie $n$-derivation, then so is every sequence $\{d_{m}\}$ of linear mappings Lie $n$-higher derivable at these points; (3) if every linear mapping Lie $n$-derivable at several points is a sum of a derivation and a linear mapping vanishing on all $(n-1)$th commutators of these points, then every sequence $\{d_{m}\}$ of linear mappings Lie $n$-higher derivable at these points is a sum of a higher derivation and a sequence of linear mappings vanishing on all $(n-1)$th commutators of these points. We also give several applications of these results. [ABSTRACT FROM AUTHOR]

In this paper, we derive a best possible k -wise extension to the well-known Snevily theorem on set systems (Snevily, 2003) which strengthens the well-known theorem by Füredi and Sudakov (2004). We also provide a conjecture which gives a common generalization to all existing non-modular L -intersection theorems. [ABSTRACT FROM AUTHOR]

The k -restricted arc connectivity of digraphs is a common generalization of the arc connectivity and the restricted arc connectivity. An arc subset S of a strong digraph D is a k -restricted arc cut if D − S has a strong component D ′ with order at least k such that D − V ( D ′ ) contains a connected subdigraph with order at least k . The k -restricted arc connectivity λ k ( D ) of a digraph D is the minimum cardinality over all k -restricted arc cuts of D . Let D be a strong digraph with order n ≥ 6 and minimum degree δ ( D ) . In this paper, we first show that λ 3 ( D ) exists if δ ( D ) ≥ 3 and, furthermore, λ 3 ( D ) ≤ ξ 3 ( D ) if δ ( D ) ≥ 4 , where ξ 3 ( D ) is the minimum 3-degree of D . Next, we prove that λ 3 ( D ) = ξ 3 ( D ) if δ ( D ) ≥ n + 3 2 . Finally, we give examples showing that these results are best possible in some sense. [ABSTRACT FROM AUTHOR]

We determine the order of the tower height for the partition size in a version of Szemerédi's regularity lemma. This addresses a question of Gowers. [ABSTRACT FROM AUTHOR]

In 1940 Fisher famously showed that if there exists a non-trivial ( v,k,λ)-design, then λ( v-1)⩾ k( k-1). Subsequently Bose gave an elegant alternative proof of Fisher's result. Here, we show that the idea behind Bose's proof can be generalised to obtain new bounds on the number of blocks in ( v,k,λ)-coverings and -packings with λ( v-1)< k( k-1). [ABSTRACT FROM AUTHOR]

In this paper, the concepts of α-strongly deferred Cesàro mean and α-strongly Cesàro submethod for double sequences are defined and studied by using deferred double natural density of the subset of natural numbers. Also, we consider the case β(n) = λ(n) - λ(n - 1); (m) = γ(m) - γ(m - 1) for α-strongly deferred Cesàro mean Dαβ,γ wher λ:= {λ(n)}∞n=1 and γ = {λ(m)}∞n=1 are strictly increasing sequences of positive integers with λ(0) = 0 and γ(0) = 0. Finally, we obtain some inclusion results between α-strongly Cesàro submethod and α-strongly deferred Cesàro mean Dαβ,γ of the double sequences. [ABSTRACT FROM AUTHOR]

Let A be a non-trivial abelian group. A connected simple graph G = (V,E) is A-antimagic if there exists an edge labeling f: E(G) → A \ {0} such that the induced vertex labeling f+: V(G) → A, defined by f+ (v) = ΣuvϵE(G) f (uv), is injective. The integer-antimagic spectrum of a graph G is the set IAM(G) = {k | G is ℤk-antimagic and k ≥ 2}. In this article, we provide a constructive proof for a join graph GVK1 obtained from a given graph G with a special edge labeling. In particular, we determine the integer-antimagic spectra of fan and wheel graphs. The integer-antimagic spectrum of gear graph is also determined. [ABSTRACT FROM AUTHOR]

Let Sn be the symmetric group of all permutations of n letters. We show that the number of distinct Wilf classes of subsets of exactly seven four-letter patterns is 15392, and that the number of distinct Wilf classes of subsets of exactly six four-letter patterns is 8438. [ABSTRACT FROM AUTHOR]

In this paper, we prove that for any positive integer k and for any simple graph G of order at least 3 k , if d ( x ) + d ( y ) ≥ 4 k for every pair of vertices x and y of distance 2 in G , then with one exception, G contains k disjoint cycles. This generalizes a former result of Corrádi and Hajnal (1963). [ABSTRACT FROM AUTHOR]

Large sets of disjoint group-divisible designs with block size three and type 2 n 4 1 (denoted by L S ( 2 n 4 1 ) ) were first studied by Schellenberg and Stinson and motivated by their connection with perfect threshold schemes. It has been shown that the necessary condition n ≡ 0 ( m o d 3 ) for the existence of an L S ( 2 n 4 1 ) is sufficient with five possible exceptions n ∈ { 12 , 30 , 36 , 48 , 144 } . These five undetermined L S ( 2 n 4 1 ) s are shown to exist in this paper. [ABSTRACT FROM AUTHOR]

Let k be a positive integer, and let G be a graph of order n ≥ 3 k and S be a set of k vertices of G . In this paper, we prove that if σ 2 ( G ) ≥ n + k − 1 + Δ ( G [ S ] ) , then G can be partitioned into k vertex-disjoint cycles C 1 , … , C k − 1 , C k such that | V ( C i ) ∩ S | = 1 for 1 ≤ i ≤ k , and | V ( C i ) | = 3 for 1 ≤ i ≤ k − 1 − Δ ( G [ S ] ) and | V ( C i ) | ≤ 4 for k − Δ ( G [ S ] ) ≤ i ≤ k − 1 , where σ 2 ( G ) denotes the minimum degree sum of two non-adjacent vertices in G and Δ ( G [ S ] ) denotes the maximum degree of the subgraph of G induced by S . This is a common generalization of the results obtained by Dong (2010) and Chiba et al. (2010), respectively. In order to show the main theorem, we further give other related results concerning the degree conditions for the existence of k vertex-disjoint cycles in which each cycle contains a vertex in a specified vertex subset. [ABSTRACT FROM AUTHOR]

If E is a subset of the integers then the n -th characteristic ideal of E is the fractional ideal of Z consisting of 0 and the leading coefficients of the polynomials in Q [ x ] of degree no more than n which are integer valued on E . For p a prime the characteristic sequence of Int ( E , Z ) is the sequence α E ( n ) of negatives of the p -adic valuations of these ideals. The asymptotic limit lim n → ∞ ⁡ α E , p ( n ) n of this sequence, called the valuative capacity of E , gives information about the geometry of E . We compute these valuative capacities for the sets E of sums of ℓ ≥ 2 integers to the power of d , by observing the p -adic closure of these sets. [ABSTRACT FROM AUTHOR]

We first study the relationship between the k-Fibonacci numbers and the elements of a subset of ℚ 2. Later, and since generally studies that are made on the Fibonacci sequences consider that these numbers are integers, in this article, we study the possibility that the index of the k-Fibonacci number is fractional; concretely, 2n+1/2 . In this way, the k-Fibonacci numbers that we obtain are complex. And in our desire to find integer sequences, we consider the sequences obtained from the moduli of these numbers. In this process, we obtain several integer sequences, some of which are indexed in The Online Enciplopedy of Integer Sequences (OEIS). [ABSTRACT FROM AUTHOR]

The classical theorem of Schnirelmann states that the primes are an additive basis for the integers. In this paper, we consider the analogous multiplicative setting of the cyclic group (ℤ/qℤ)x and prove a similar result. For all suitably large primes q we define Pη to be the set of primes less than ηq, viewed naturally as a subset of (ℤ/qℤ)x. Considering the k-fold product set P(kη = {p1p1 ... pk : pi ∈ Pη}, we show that, for η » q-1/4+ε, there exists a constant k depending only on ε such that P(kη = (ℤ/qℤ)x. Erdős conjectured that, for η = 1, the value k = 2 should sufiice: although we have not been able to prove this conjecture, we do establish that P(2)1 has density at least 1/64 v(1 + o(1)). We also formulate a similar theorem in almost-primes, improving on existing results. [ABSTRACT FROM AUTHOR]

For each non-negative integer k ≤ 6 we give a complete description of the tournaments which are (≤ k)-reconstructible up to duality and of those which are (≤ k)-hereditarily-reconstructible up to duality. We recall that a tournament T is (≤ k)-reconstructible up to duality (resp. (≤ k)-hereditarily-reconstructible up to duality) if for every tournament T' on the same finite set V of vertices, T' is isomorphic to T or to its dual T ', (resp. the tournament T'[X] induced on every subset X of V is isomorphic to T [X] or to its dual) provided that the induced tournament T'[K] is isomorphic to T [K] or to its dual for every subset K of V of size at most k. [ABSTRACT FROM AUTHOR]

Let G = (V,E) be a graph, k is a positive integer and let S = (U,X) be a semigraph. A subset D ⊆ V is called a k-strong(weak) dominating set of the graph G if every vertex v ϵ V - D is strongly(weakly) dominated by at least k vertices of D. The k-strong(weak)domination number γsk(γwk) is the minimum cardinality of k-strong!weak) dominating set of G. A subset D ⊆ U is called k-strong(weak) adjacent dominating set of semigraph S if every vertex u ∊ U -D is strongly(weakly) adjacent dominated by at least k vertices of D. The minimum cardinality of a k- strong adjacent dominating set, a k- weak adjacent dominating set are respectively denoted as γs,ak(S) and γw,ak(S). In this paper, we determine γsk and γWk for standard graphs. Also, we establish bounds on the above domination parameters for graphs and semigraphs. We prove that the k-strong(weak) domination problem is NP-complete for general graphs. [ABSTRACT FROM AUTHOR]

Let A ⊆ Z be a finite nonempty set. Given a subset of the set A, the sum of all elements of the subset is called the subset sum. The set of all subset sums of A is denoted by S0(A) and the set of all nontrivial subset sums of A is denoted by S(A). For a finite sequence A of integers, the subsequence sums S0(A) and S(A) are defined in a similar way. The direct problem for these sumsets is to find a lower bound for |S0(A)| (respectively |S(A)|) in terms of |A|. The inverse problem for these sumsets is to determine the structure of A for which |S0(A)| (respectively |S(A)|) is minimal. We solve both the direct and inverse problems for subset sums of a set A. Our results generalize the results of Nathanson on subset sums. Moreover, we also solve the direct problemfor the subsequence sums using Balandraud's approach used for the sequence of residue classes modulo a prime. [ABSTRACT FROM AUTHOR]

Let n , p , r be positive integers with n ≥ p ≥ r . A rank- r ‾ subset of n by p matrices (with entries in a field) is a subset in which every matrix has rank less than or equal to r . A classical theorem of Flanders states that the dimension of a rank- r ‾ linear subspace must be less than or equal to nr , and it characterizes the spaces with the critical dimension nr . Linear subspaces with dimension close to the critical one were later studied by Atkinson, Lloyd and Beasley over fields with large cardinality; their results were recently extended to all fields [18] . Using a new method, we obtain a classification of rank- r ‾ affine subspaces with large dimension, over all fields. This classification is then used to double the range of (large) dimensions for which the structure of rank- r ‾ linear subspaces is known for all fields. [ABSTRACT FROM AUTHOR]

Let u ≠ ±1, v² be a fixed integer, let p be a prime number, and let ordp(u) = d|p - 1 be the order of u mod p. This note provides a lower bound #{p ≤ x : ordp(u) = p-1} ≫ x(log x)-1 for the number of primes p ≤ x with a fixed primitive root u mod p for all large numbers x ≥ 1. The current results in the literature have the lower bound #{p ≤ x : ordp(u) = p - 1} ≫ x(log x)-2, and restrictions on the fixed primitive root to a subset of at least three or more integers. [ABSTRACT FROM AUTHOR]

Given positive integers $$n_1,\ldots ,n_p$$ , we say that a submonoid M of $$({\mathbb N},+)$$ is a $$(n_1,\ldots ,n_p)$$ -bracelet if $$a+b+\left\{ n_1,\ldots ,n_p\right\} \subseteq M$$ for every $$a,b\in M\backslash \left\{ 0\right\} $$ . In this note, we explicitly describe the smallest $$\left( n_1,\ldots ,n_p\right) $$ -bracelet that contains a finite subset X of $${\mathbb N}$$ . We also present a recursive method that enables us to construct the whole set $$\mathcal B(n_1,\ldots ,n_p)=\left\{ M|M \quad \text {is a} \quad (n_1,\ldots ,n_p)\text {-bracelet}\right\} $$ . Finally, we study $$(n_1,\ldots ,n_p)$$ -bracelets that cannot be expressed as the intersection of $$(n_1,\ldots , n_p)$$ -bracelets properly containing it. [ABSTRACT FROM AUTHOR]

Let $K$ be a number field with ring of integers ${\mathcal{O}}$. After introducing a suitable notion of density for subsets of ${\mathcal{O}}$, generalising the natural density for subsets of $\mathbb{Z}$, we show that the density of the set of coprime $m$-tuples of algebraic integers is $1/{\it\zeta}_{K}(m)$, where ${\it\zeta}_{K}$ is the Dedekind zeta function of $K$. This generalises a result found independently by Mertens [‘Ueber einige asymptotische Gesetze der Zahlentheorie’, J. reine angew. Math. 77 (1874), 289–338] and Cesàro [‘Question 75 (solution)’, Mathesis 3 (1883), 224–225] concerning the density of coprime pairs of integers in $\mathbb{Z}$. [ABSTRACT FROM PUBLISHER]

In this paper various notions of convexity of real functions with respect to Chebyshev systems defined over arbitrary subsets of the real line are introduced. As an auxiliary notion, a concept of a relevant divided difference and also a related lower Dinghas type derivative are also defined. The main results of the paper offer various characterizations of the convexity notions in terms of the nonnegativity of a generalized divided difference and the corresponding lower Dinghas type derivative. [ABSTRACT FROM AUTHOR]

In this paper, we study $$w$$ -frameproof codes, which are equivalent to $$\{1,w\}$$ -separating hash families. Our main results concern binary codes, which are defined over an alphabet of two symbols. For all $$w \ge 3$$ , and for $$w+1 \le N \le 3w$$ , we show that an $${\mathsf {SHF}}(N; n,2, \{1,w \})$$ exists only if $$n \le N$$ , and an $${\mathsf {SHF}}(N; N,2, \{1,w \})$$ must be a permutation matrix of degree $$N$$ . [ABSTRACT FROM AUTHOR]

For a given set S of n real numbers, there are totally 2 n − 1 different subsets excluding the empty set. The subset sum problem is defined as finding L subsets whose summation of subset elements are the L smallest among all possible subsets. This problem has many applications in operations research and real world. However, the problem is very computationally challenging. In this paper, a novel algorithm is proposed to solve this problem. Firstly, the L smallest k -subsets sum problem, a special case and sub-problem of the subset sum problem, is investigated. Given a positive integer k ( k ≤ n ) , k -subset means the subset of k distinct elements of S . Obviously, there are totally ( n k ) k -subsets. By expressing all these k -subsets with a network, the L smallest k -subsets sum problem is converted to finding L shortest loopless paths in this network. By combining the L shortest paths algorithm and the finite-time convergent recurrent neural network, a new algorithm for the L smallest k -subsets sum problem is developed. Finally, the solution to the subset sum problem is obtained by combining the solutions to these sub-problems. And experimental results show that the proposed algorithm is very effective and efficient. [ABSTRACT FROM AUTHOR]

A recent extension due to Trigub of one of the classical Sz.-Nagy's results on the integrability of the Fourier transform is generalized to several dimensions for functions with bounded Hardy variation. [ABSTRACT FROM AUTHOR]